I figured it out....partly. I was being very stupid with the binary powering algorithm in FLINT. If I wanted to raise a polynomial f of length n to the power of 7 I would do:
out = f pow = f pow = pow*pow // n x n out *= pow // n x 2n-1 pow = pow*pow 2n-1 x 2n-1 out *= pow // 3n-2 x 4n-3 Instead I should just do: out = f out = out*out // n x n out *= f // 2n-1 x n out = out*out // 3n-2 x 3n-2 out *= f // 6n-5 x n i.e. work the binary algorithm in reverse. Because of the truncated FFT in FLINT, this turns out to be way more efficient. I believe Magma gets around this by using classical multiplication when the length of one of the operands is less than 10 (this is something SAGE could do too). Magma does still seem to use something tricky for degee 1 polynomials though. One can see Magma is up to something smart by computing (1+7*x)^(2^13) and (1+8*x)^(2^13). The second is about three times faster!! Or perhaps this is just because I am using mpn's instead of mpz's. I think mpz's have some special code for multiplications with long strings of zeroes in the representation. Times are now down to about the same as Magma in FLINT for the original problem that I started this thread for. Bill. On 8 Oct, 01:05, Bill Hart <[EMAIL PROTECTED]> wrote: > On 8 Oct, 01:03, Bill Hart <[EMAIL PROTECTED]> wrote: > > > I've just been playing around with polynomial powering in sage, using > > magma, ZZ['x'] and Fmpz_poly objects. > > > I've noticed that if I raise 743*x+423 to the power 2000, magma takes > > about 0.1s, Fmpz_poly takes about 3s and ZZ['x'] takes about 1s!! > > > This sort of thing only happens for polynomials of degree 1, so I had > > presumed that Magma was just using the binomial expansion, and that is > > what Fmpz_poly does. And in fact if you raise x+1 to the power 2000, > > it is fast. But there is clearly another trick. Magma is again doing > > something special. > > > If anyone has any ideas.... > > > Bill. --~--~---------~--~----~------------~-------~--~----~ To post to this group, send email to sage-devel@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/sage-devel URLs: http://sage.scipy.org/sage/ and http://modular.math.washington.edu/sage/ -~----------~----~----~----~------~----~------~--~---
