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.
>
> 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)
>
>
>> 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.
