332 views

Skip to first unread message

Oct 4, 2016, 7:10:31 PM10/4/16

to sage-devel

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

even for recent singular upgrade

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

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

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.

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.

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.

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

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

Oct 10, 2016, 11:55:22 PM10/10/16

to sage-devel

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

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: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 GPUThe 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)-1Exception (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 loopsage: 2^20-11048575sage: timeit('x^1048575')125 loops, best of 3: 1.66 ms per loopsage: timeit('x^10')625 loops, best of 3: 381 ns per loopsage: 2^30-11073741823sage: timeit('x^1073741823')5 loops, best of 3: 1.72 s per loopsage: timeit('x^(2^30-1)')5 loops, best of 3: 1.71 s per loopbut thensage: 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.

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

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

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: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 GPUI wonder why this happens - a Flint issue? :sage: R.<x>=QQ[]sage: x^(2^30)-1Exception (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)

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.

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: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.I wonder why this happens - a Flint issue? :sage: R.<x>=QQ[]sage: x^(2^30)-1Exception (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.

Oct 12, 2016, 8:01:17 AM10/12/16

to sage-devel

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.

Feb 7, 2017, 2:15:44 PM2/7/17

to sage-devel

Probably closely related:

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

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

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.

Feb 8, 2017, 8:54:27 PM2/8/17

to sage-devel

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

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.

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.

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 onhttps://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.

Feb 11, 2017, 11:16:29 AM2/11/17

to sage-devel

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;

Feb 13, 2017, 3:40:03 PM2/13/17

to sage-devel

I can only answer one of your questions.

On Saturday, 11 February 2017 17:16:29 UTC+1, Jakob Kroeker wrote:

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.

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?

Reply all

Reply to author

Forward

0 new messages

Search

Clear search

Close search

Google apps

Main menu