# a 7(!) year old (Singular) overflow issue still holds

332 views

### Jakob Kroeker

Oct 4, 2016, 7:10:31 PM10/4/16
to sage-devel

https://trac.sagemath.org/ticket/6472

https://trac.sagemath.org/ticket/17254

and it was not(?) reported to upstream...

### Bill Hart

Oct 9, 2016, 11:35:57 AM10/9/16
to 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.

### Bill Hart

Oct 9, 2016, 11:41:30 AM10/9/16
to sage-devel
Note that Hans has fixed the fact that Singular wasn't reporting this as an overflow.

### Dima Pasechnik

Oct 9, 2016, 12:08:29 PM10/9/16
to sage-devel

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.

### Bill Hart

Oct 9, 2016, 12:48:31 PM10/9/16
to 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).

### Dima Pasechnik

Oct 10, 2016, 6:31:25 AM10/10/16
to sage-devel

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

### Ralf Stephan

Oct 10, 2016, 11:55:22 PM10/10/16
to sage-devel

### Bill Hart

Oct 11, 2016, 12:47:23 AM10/11/16
to 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.<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.

### Jean-Pierre Flori

Oct 11, 2016, 3:33:57 AM10/11/16
to sage-devel
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.)

### Dima Pasechnik

Oct 11, 2016, 9:18:26 AM10/11/16
to sage-devel

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)

### Bill Hart

Oct 12, 2016, 7:55:17 AM10/12/16
to sage-devel
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.

### Bill Hart

Oct 12, 2016, 7:59:08 AM10/12/16
to 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.<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.

### Bill Hart

Oct 12, 2016, 8:01:17 AM10/12/16
to 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.

### kcrisman

Feb 7, 2017, 2:15:44 PM2/7/17
to sage-devel
Probably closely related:

### Jakob Kroeker

Feb 8, 2017, 8:16:34 AM2/8/17
to sage-devel
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

### kcrisman

Feb 8, 2017, 2:32:43 PM2/8/17
to sage-devel

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.
Seems to be an otherwise-satisfied customer who is at a loss.

### Jakob Kroeker

Feb 8, 2017, 8:54:27 PM2/8/17
to sage-devel

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

to give a precise answer to the question on
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.

### kcrisman

Feb 9, 2017, 8:03:18 AM2/9/17
to sage-devel

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

Naturally.

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

### Jakob Kroeker

Feb 11, 2017, 11:16:29 AM2/11/17
to 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.

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

### Bill Hart

Feb 13, 2017, 3:40:03 PM2/13/17
to sage-devel

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.

### Jakob Kroeker

Mar 3, 2017, 4:24:12 PM3/3/17
to sage-devel

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&t=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?