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

[Jakob Kroeker]

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

even for recent singular upgrade

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

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

[Bill Hart]

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]

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

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

[Bill Hart]

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]

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]

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

[Bill Hart]

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]

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]

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]

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]

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]

 

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]

Probably closely related:

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

[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

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

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

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

[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

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

[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&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?