On Monday, 10 October 2016 12:31:25 UTC+2, Dima Pasechnik wrote:
>
>
>
> 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.
>
I'm not precisely sure why that happens. How much memory did you have
available on your machine?
This should create the polynomial x, then try to raise it to the power of
2^30, which is about a billion I think.
Along the way it will use the FFT, which is a bit of a memory hog.
One day we ought to fix the powering code to handle monomials separately.
It is 2016 after all.
> 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>
>
>
There's some caching in Flint I guess, though I'm not entirely sure why
that would matter here.
Bill.
>
> 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.
