On Tuesday, 11 October 2016 15:18:26 UTC+2, Dima Pasechnik wrote:
>
>
>
> On Tuesday, October 11, 2016 at 4:47:23 AM UTC, Bill Hart wrote:
>>
>>
>>
>> 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?
>>
>
> 16GB x86_64 Linux system, lightly loaded.
>
Then it just ran out of memory, for sure.
>
>
>>
>> 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.
>>
>
> I imagine that, more generally, for the fewnomials (so that the monimials
> are (almost) algebraically independent), it's faster to do "naive"
> powering, no? (i.e., the multinomial formula)
>
>
There are many algorithms for powering of multivariate polynomials. But
yes, in the case of univariates, the multinomial formula is fast. Actually,
now that you mention it, we have that implemented. I'm not sure why that
wouldn't be used here by default. It's clearly not, since that wouldn't run
out of 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>
>>>
>>>
>> 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.
