gcd problem / really bignums for exponents


> -----Original Message-----
> From: maxima-bounces at math.utexas.edu [mailto:maxima-
> bounces at math.utexas.edu] On Behalf Of Robert Dodier
> Sent: Tuesday, February 13, 2007 7:35 PM
> To: Stavros Macrakis
> Cc: Andreas Eder; Raymond Toy; Maxima at math.utexas.edu
> Subject: Re: [Maxima] gcd problem
> 
> On 2/13/07, Stavros Macrakis <macrakis at alum.mit.edu> wrote:
> 
> > In the particular case of CRE exponents, I am not sure.  There are
> > unlikely to be many practical applications of exponents > 2^31,
> 
> Bug reports which seem to be related to fixnum overflow are
> evidence of such applications, I believe.

OK, here's the choice. Making factorization (and other computations using
canonical polynomials) n% slower, or when some exponent larger than about
2^29 occurs, giving a warning: please reformulate the problem so that such
large exponents do not occur.
Note that some computer algebra systems represent polynomials as vectors
with explicit zero coefficients. In them, a polynomial of degree 2^29
requires something like 4 gigabytes of memory to store. This is not
impossible, on some machines, but a polynomial of degree 2^64 is unlikely.

And what about the barrier when bignums run out?  That is, x^(2^(2^32)) or
whatever it is... You must face the same question of crashing or
reformulating. So by making everything slower, you do not solve the problem
in principle, you just defer it until someone breaks it with a test example
taking 4 more characters.  

Oh, by the way, factoring a polynomial of degree n using Berlekamp's
algorithm, as used by Maxima, probably requires allocating an array of
numbers modulo k>n  of size n X n.  So you can't do it unless you can store
at least 4 x n x n bytes.

If (as someone has suggested) he was going to edit code so that f+ is
replaced by +, I oppose this.  If he wants to make a compile-time flag to
optionally redefine the f+ macro to expand to generic +, and thus enable
making 2 versions of Maxima, the "fast" one and the "one that allows bignum
exponents", we can then test them. We can even say, in the fast one, OH, you
ran out of exponent space. Fire up the slower Maxima and see if that works.

RJF

> 
> If changing f+ to + fixes some bugs, then it is well worth doing,
> even at the cost of some speed penalty. I'm not convinced by the
> "original intent" argument here. The factorization code is well-nigh
> impenetrable as it stands; I don't see the substitution f+ --> +
> making much difference.
> 
> All the best
> Robert
> _______________________________________________
> Maxima mailing list
> Maxima at math.utexas.edu
> http://www.math.utexas.edu/mailman/listinfo/maxima