OK, I've fixed this problem now. FLINT takes just 0.032s for the original problem I noted at the start of the thread of powering a degree 1 polynomials. It's about three times faster than Magma now, so that should be good enough.
It basically boiled down to the algorithm I was using. It was O(n^3), or something like that, in the number of bits of the output coefficients, whereas now it is basically O(n). One needs to write each whole output coefficient out and compute the next one recursively from it. I had been doing three passes over the output coefficients, once to write down the binomial coefficients, once to multiply by the power of the first coefficient and once to multiply by the power of the second coefficient. Each of the binomial coefficients were computed recursively, as were the powers, but it was all the multi- precision multiplications which were slowing it down. I could still do some optimisations for when the coefficients of the original polynomial are divisible by powers of 2. But this actually isn't as much as a problem as I thought, since I use GMP's powering code anyway, and it already takes powers of 2 into account. The other operations used don't matter so much, though when I implement Jebelean's algorithm for division, it will speed up slightly. Bill. On 8 Oct, 04:22, Bill Hart <[EMAIL PROTECTED]> wrote: > You are right. It's in the powering code I think, where powers of 2 > are taken out before powering. This is at least evidence that Magma > uses the binomial expansion after all. > > Actually, Magma is still about 4 times quicker for the original > problem at the start of this thread. I had some errors in my code. So > I've sped it up, but not by enough, although it is now much faster for > short length polynomials where the length is not 2. > > If I am computing (ax+b)^n what I am doing in the binomial method is > writing down the binomial coefficients (computing them recursively), > then computing each of the powers of a recursively and going through > and multiplying by them, then doing the same for powers of b. > > What I should be doing is perhaps either computing each coefficient > recursively, i.e. computing bin(n,i)a^i*b^(n-i) from > bin(n,i-1)a^(i-1)*b^(n-i+1), or at worst, writing down the binomial > coefficients then computing each of the a^i*b^(n-i) recursively then > multiplying by them in turn. Of course I also need to be careful about > powers of 2 dividing a and b. > > It is hard to believe that someone in Sydney went to so much trouble!! > > Bill. > > On 8 Oct, 03:24, David Harvey <[EMAIL PROTECTED]> wrote: > > > On Oct 7, 2007, at 10:02 PM, Bill Hart wrote: > > > > 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). > > > SAGE is just using NTL for this, so it's doing whatever NTL is doing. > > > > I think mpz's have some special code for multiplications with > > > long strings of zeroes in the representation. > > > I don't think this is true. The GMP documentation says explicitly to > > the contrary somewhere. > > > david --~--~---------~--~----~------------~-------~--~----~ 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/ -~----------~----~----~----~------~----~------~--~---
