[sage-devel] Re: a 7(!) year old (Singular) overflow issue still holds

[Jakob Kroeker]

I asked in the Singular forum, how to change the exponent size for Singular:

https://www.singular.uni-kl.de/forum/viewtopic.php?f=10=2576

Is it transparent for overflow detection?
>

I don't understand the question.

My question is, does overflow detection work correcly with different 
exponent sizes than 16 bit?


Am Montag, 13. Februar 2017 21:40:03 UTC+1 schrieb Bill Hart:
>
> I can only answer one of your questions.
>
> On Saturday, 11 February 2017 17:16:29 UTC+1, Jakob Kroeker 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.
>>>
>>
>> How to change this? Is it runtime or compile-time?
>>
>
> I believe it can be set at runtime. Hans surely knows how to change it.
>  
>
>> Is it transparent for overflow detection?
>>
>
> I don't understand the question.
>  
>
>>
>> I guess it isn't easy for Sage to change the relevant ring upon overflow 
>>> to one using 64 bit exponents.
>>>
>>
>> I have no idea;
>>
>> Jakob
>>
>

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

[sage-devel] Re: a 7(!) year old (Singular) overflow issue still holds

['Bill Hart' via sage-devel]

I can only answer one of your questions.

On Saturday, 11 February 2017 17:16:29 UTC+1, Jakob Kroeker 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.
>>
>
> How to change this? Is it runtime or compile-time?
>

I believe it can be set at runtime. Hans surely knows how to change it.
 

> Is it transparent for overflow detection?
>

I don't understand the question.
 

>
> I guess it isn't easy for Sage to change the relevant ring upon overflow 
>> to one using 64 bit exponents.
>>
>
> I have no idea;
>
> Jakob
>

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

[sage-devel] Re: a 7(!) year old (Singular) overflow issue still holds

[Jakob Kroeker]

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

How to change this? Is it runtime or compile-time? Is it transparent for 
overflow detection?

I guess it isn't easy for Sage to change the relevant ring upon overflow to 
> one using 64 bit exponents.
>

I have no idea;

Jakob

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

[sage-devel] Re: a 7(!) year old (Singular) overflow issue still holds

[kcrisman]

On Wednesday, February 8, 2017 at 8:54:27 PM UTC-5, Jakob Kroeker wrote:
>
>
> >If someone who knows what they are talking about [...]
>
> to give a precise answer to the question on 
> https://ask.sagemath.org/ 
> 
> question/36480/restricted-usability-of-singular-after-upgrade/ 
> 
> it would be helpful to examine the failing example.
>
>
Naturally.

Your answer seems like it should give that person a good start at debugging 
it themselves, though, thank you.

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

[sage-devel] Re: a 7(!) year old (Singular) overflow issue still holds

[Jakob Kroeker]

>If someone who knows what they are talking about [...]

to give a precise answer to the question on 
https://ask.sagemath.org/ 

question/36480/restricted-usability-of-singular-after-upgrade/ 

it would be helpful to examine the failing example.

First guess: 
because there _could be an overflow_ for some operation if an exponent in 
the input is bigger than 16 bit,
in recent Singular the input exponent is restricted to 16 bit. No explicit 
overflow test is implemented.
For example, if you try in recent Singular 

ring rng = 0,(x,y),dp;
short = 0;
poly h = x^2147483647;
//   ? OVERFLOW in power(d=1, e=2147483647, max=32767)


you get an overflow exception with the hint that max allowed exponent is 
32767. This was not the case for older Singular versions.

My second guess is: an overflow occurs in the computation by Singular 
which was not detected in older Singular version => result seems computable 
but is likely incorrect.
In the new Singular version and thus in Sage with upgraded Singular  the 
overflow is detected correctly so the computation 
is aborted.




Am Mittwoch, 8. Februar 2017 20:32:43 UTC+1 schrieb kcrisman:
>
>
>
>
> as far as I know, limiting to 16 bit exponents for _input_ was introduced 
>> to prevent undetected overflows;
>> it must be one of the tickets
>>>
>>>
>>>
>
> If someone who knows what they are talking about (i.e., not me) could 
> mention this on the ask.sagemath question that would be really helpful. 
> https://ask.sagemath.org/ 
> 
> question/36480/restricted-usability-of-singular-after-upgrade/ 
> 
> Seems to be an otherwise-satisfied customer who is at a loss.
>

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

[sage-devel] Re: a 7(!) year old (Singular) overflow issue still holds

[kcrisman]

as far as I know, limiting to 16 bit exponents for _input_ was introduced 
> to prevent undetected overflows;
> it must be one of the tickets
>>
>>
>>

If someone who knows what they are talking about (i.e., not me) could 
mention this on the ask.sagemath question that would be really helpful. 
https://ask.sagemath.org/ 

question/36480/restricted-usability-of-singular-after-upgrade/ 

Seems to be an otherwise-satisfied customer who is at a loss.

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

[sage-devel] Re: a 7(!) year old (Singular) overflow issue still holds

[Jakob Kroeker]

as far as I know, limiting to 16 bit exponents for _input_ was introduced 
to prevent undetected overflows;
it must be one of the tickets

https://www.singular.uni-kl.de:8005/trac/ticket/630
https://www.singular.uni-kl.de:8005/trac/ticket/631
https://www.singular.uni-kl.de:8005/trac/ticket/696
https://www.singular.uni-kl.de:8005/trac/ticket/698

see commits in February 2015, like
https://github.com/Singular/Sources/commit/fc77091687ca4452f82b084b30f8522dec3b357d


There is a history of overflow issues in Singular, for example see
https://www.singular.uni-kl.de:8005/trac/ticket/232
https://www.singular.uni-kl.de:8005/trac/ticket/414

Thus I suspect (without proof) that it is still possible to construct 
various examples leading to overflows in the results.

So can someone try to find new(unknown) overflow issues in recent Singular?

Jakob

Am Dienstag, 11. Oktober 2016 09:33:57 UTC+2 schrieb Jean-Pierre Flori:
>
> Yes it is a feature of the Singular 4 update that Singular and Sage work 
> by default with 16 bit exponents on 32 and 64 bit platform by default.
> If only all of of you had read carefully the 543 comments of the update 
> ticket and remembered this tcomment 
> https://trac.sagemath.org/ticket/17254#comment:126 and commit 
> https://git.sagemath.org/sage.git/commit/?id=8c0275427c66b709413188b82da7845a3196e4bb
>  
> that would be obvious to you.
> Now if we want to give more bits when fewer variables are used that should 
> be possible.
> (I'm just kidding, this is a not so serious post except for the previous 
> sentence.)
>

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

[sage-devel] Re: a 7(!) year old (Singular) overflow issue still holds

[kcrisman]

Probably closely related:
https://ask.sagemath.org/question/36480/restricted-usability-of-singular-after-upgrade/

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

[sage-devel] Re: a 7(!) year old (Singular) overflow issue still holds

['Bill Hart' via sage-devel]

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

Oh, I guess the multinomial code may not be in the latest official Flint 
release.

Bill. 

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

[sage-devel] Re: a 7(!) year old (Singular) overflow issue still holds

['Bill Hart' via sage-devel]

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

[sage-devel] Re: a 7(!) year old (Singular) overflow issue still holds

['Bill Hart' via sage-devel]

On Tuesday, 11 October 2016 09:33:57 UTC+2, Jean-Pierre Flori wrote:
>
> Yes it is a feature of the Singular 4 update that Singular and Sage work 
> by default with 16 bit exponents on 32 and 64 bit platform by default.
> If only all of of you had read carefully the 543 comments of the update 
> ticket and remembered this tcomment 
> https://trac.sagemath.org/ticket/17254#comment:126 and commit 
> https://git.sagemath.org/sage.git/commit/?id=8c0275427c66b709413188b82da7845a3196e4bb
>  
> that would be obvious to you.
> Now if we want to give more bits when fewer variables are used that should 
> be possible.
> (I'm just kidding, this is a not so serious post except for the previous 
> sentence.)
>

Singular is not limited to one 64 bit word per monomial. It can have 
monomials up to 1000 words or something like that. So the number of 
variables should have no bearing on the packing. 

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

[sage-devel] Re: a 7(!) year old (Singular) overflow issue still holds

[Dima Pasechnik]

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

[sage-devel] Re: a 7(!) year old (Singular) overflow issue still holds

[Jean-Pierre Flori]

Yes it is a feature of the Singular 4 update that Singular and Sage work by 
default with 16 bit exponents on 32 and 64 bit platform by default.
If only all of of you had read carefully the 543 comments of the update 
ticket and remembered this tcomment 
https://trac.sagemath.org/ticket/17254#comment:126 and commit 
https://git.sagemath.org/sage.git/commit/?id=8c0275427c66b709413188b82da7845a3196e4bb
 
that would be obvious to you.
Now if we want to give more bits when fewer variables are used that should 
be possible.
(I'm just kidding, this is a not so serious post except for the previous 
sentence.)

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

[sage-devel] Re: a 7(!) year old (Singular) overflow issue still holds

['Bill Hart' via sage-devel]

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

[sage-devel] Re: a 7(!) year old (Singular) overflow issue still holds

[Ralf Stephan]

See also the comments in https://trac.sagemath.org/ticket/12589

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

[sage-devel] Re: a 7(!) year old (Singular) overflow issue still holds

[Dima Pasechnik]

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



 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.

[sage-devel] Re: a 7(!) year old (Singular) overflow issue still holds

['Bill Hart' via sage-devel]

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.

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

[sage-devel] Re: a 7(!) year old (Singular) overflow issue still holds

[Dima Pasechnik]

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.
 
 

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

[sage-devel] Re: a 7(!) year old (Singular) overflow issue still holds

['Bill Hart' via sage-devel]

Note that Hans has fixed the fact that Singular wasn't reporting this as an 
overflow.

On Sunday, 9 October 2016 17:35:57 UTC+2, 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.
>
> 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.

[sage-devel] Re: a 7(!) year old (Singular) overflow issue still holds

['Bill Hart' via sage-devel]

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.

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.