On Sunday, October 9, 2016 at 4:48:31 PM UTC, Bill Hart wrote:
>
>
>
> On Sunday, 9 October 2016 18:08:29 UTC+2, Dima Pasechnik wrote:
>>
>>
>>
>> On Sunday, October 9, 2016 at 3:35:57 PM UTC, Bill Hart wrote:
>>>
>>> By default, Singular uses 16 bit exponents. But it is perfectly capable
>>> of working with exponents up to 64 bits. That will be slower of course.
>>>
>>> why? I presume arithmetic on 16-bit integers is not faster than on
>> 32-bit, or even 64-bit.
>>
>
> It's the exponent arithmetic, not the coefficients we are talking about.
>
sure - I was thinking about univariate case; in the multivariate case, if
you want fast arithmetic on exponents of monomials given as integer vectors
in year 2016, you probably would want to use GPU
> The exponents are packed, with four 16 bit field in a 64 bit word. This is
> *much* faster. I use the same trick, as does just about every decent
> computer algebra system out there.
>
> Interestingly, Magma only allows exponents up to about 30 bits, but it
> takes a few minutes to compute x^(2^30 - 1).
>
I wonder why this happens - a Flint issue? :
sage: R.<x>=QQ[]
sage: x^(2^30)-1
Exception (FLINT memory_manager). Unable to allocate memory.
sage: x^(2^30-1)
Killed
(which appears to indicate that the recovery from the exception was not
complete)
On the other hand:
sage: timeit('x^(2^20-1)')
125 loops, best of 3: 1.66 ms per loop
sage: 2^20-1
1048575
sage: timeit('x^1048575')
125 loops, best of 3: 1.66 ms per loop
sage: timeit('x^10')
625 loops, best of 3: 381 ns per loop
sage: 2^30-1
1073741823
sage: timeit('x^1073741823')
5 loops, best of 3: 1.72 s per loop
sage: timeit('x^(2^30-1)')
5 loops, best of 3: 1.71 s per loop
but then
sage: x^(2^30-1)
<repr(<sage.rings.polynomial.polynomial_rational_flint.Polynomial_rational_flint
at 0x7fbb07bd7910>) failed: MemoryError>
looks quite strange...
Dima
>
>>
>>
>>
>>> I guess it isn't easy for Sage to change the relevant ring upon overflow
>>> to one using 64 bit exponents.
>>>
>>> I can't say whether it would be easy or hard for Singular to
>>> automatically change the exponent size for you. For basic arithmetic, I
>>> have implemented precisely this in the code I've been writing. But Singular
>>> is almost infinitely more complex than the very simple cases I've been
>>> dealing with in my own code. At this stage I couldn't even hazard a guess.
>>>
>>> I'll ask Hans if I remember. But either way, I believe this would be an
>>> *extremely* time consuming thing to fix. How important is it?
>>>
>>> Bill.
>>>
>>> On Wednesday, 5 October 2016 01:10:31 UTC+2, Jakob Kroeker wrote:
>>>>
>>>>
>>>> https://trac.sagemath.org/ticket/6472
>>>>
>>>> even for recent singular upgrade
>>>>
>>>> https://trac.sagemath.org/ticket/17254
>>>>
>>>> and it was not(?) reported to upstream...
>>>>
>>>>
>>>>
>>>>
>>>>
>>>>
>>>>
>>>>
>>>>
>>>>
>>>>
>>>>
>>>>
>>>>
>>>>
--
You received this message because you are subscribed to the Google Groups
"sage-devel" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to sage-devel+unsubscr...@googlegroups.com.
To post to this group, send email to sage-devel@googlegroups.com.
Visit this group at https://groups.google.com/group/sage-devel.
For more options, visit https://groups.google.com/d/optout.
