Ask Your Question
0

Exponent overflow in PolynomialRing(): need a work around

asked 2013-05-08 02:53:01 -0600

apeel gravatar image

updated 2013-05-08 02:56:51 -0600

PolynomialRing() gives an OverflowError for exponents larger than 32768. For example

sage: R = GF(2**28, 'a')
sage: a = R.gen() 
sage: x = PolynomialRing(R, 'x', 4).gens() 
sage: f = x[0]**32768 
sage: f = x[0]**32769 
...
OverflowError: Exponent overflow (32769).

I need to make a function containing x[0]**(2**28 - 2). How can I get Sage to do that?

I am using Sage Version 5.3, Release Date: 2012-09-08.

edit retag flag offensive close merge delete

3 answers

Sort by ยป oldest newest most voted
1

answered 2013-05-08 22:59:37 -0600

Volker Braun gravatar image

updated 2013-05-08 22:59:51 -0600

See also http://trac.sagemath.org/sage_trac/ti.... You either use less variables so that there is enough space for the bit-packed exponents

sage: R.<x,y> = QQ[]
sage: x**(2**28 - 2)
x^268435454

or you use the symbolic ring. Its not like you have memory for a dense polynomial of that degree anyways...

edit flag offensive delete link more

Comments

Thanks. It looks like a fundamental limit arising from the implementation in singular.

apeel gravatar imageapeel ( 2013-05-16 16:10:45 -0600 )edit
2

answered 2013-05-08 11:05:38 -0600

tmonteil gravatar image

Actually, this does not work on sage-5.9 either. apeel seems to use a 32-bit system whereas ppurka seems to use a 64-bit system. On a 64-bit system, you will only be able to go twice further (65536 = 2^16 instead of 32768 = 2^15):

sage: f = x[0]**(2^16-1)   
sage: f = x[0]**(2^16)  
...
OverflowError: Exponent overflow (65536).

If you really need to work with such a big exponent, you could request it on the trac server and then on singular as well, though it is possible they won't change this limit due to a possible loss of performance (i didn't check the code, so it might be possible to go until 2^32 without much loss).

If you are looking for a mathematical workaround, you need to give more information on what is your function doing. For example, if you only use the variable x[0] in this function, you could try to transform your polynomial f as a univariate polynomial, and then work with it:

sage: P = f.univariate_polynomial()
edit flag offensive delete link more

Comments

Indeed, I am on a 64bit system.

ppurka gravatar imageppurka ( 2013-05-08 15:23:36 -0600 )edit

Yes, I am using a 32 bit system.

apeel gravatar imageapeel ( 2013-05-16 16:03:14 -0600 )edit

I need all of the variables. I am trying to make a resilient function to hash an input string. Each input symbol in the string becomes an input variable.

apeel gravatar imageapeel ( 2013-05-16 16:06:36 -0600 )edit
1

answered 2013-05-08 04:21:06 -0600

ppurka gravatar image

Maybe there has been some changes in the later versions. It works here in sage-5.9 and sage-5.7 too.

sage: R = GF(2**28, 'a')
sage: a = R.gen()
sage: x = PolynomialRing(R, 'x', 4).gens()
sage: f = x[0]**32768
sage: f = x[0]**32769
sage: f
x0^32769
edit flag offensive delete link more

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

1 follower

Stats

Asked: 2013-05-08 02:53:01 -0600

Seen: 467 times

Last updated: May 08 '13