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.
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.
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).
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 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.
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>
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 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.
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 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?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)
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.
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
ring rng = 0,(x,y),dp;
short = 0;
poly h = x^2147483647;
// ? OVERFLOW in power(d=1, e=2147483647, max=32767)
>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.
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.
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?
Is it transparent for overflow detection?I don't understand the question.