I've coded up binomial expansion in the FLINT polynomial powering function for the special case of exponentiating length 2 polynomials.
Here are the times for raising (x+1) to the power n = 2^13-1: real 0m0.040s user 0m0.020s sys 0m0.020s Here are the times for n = 2^13: real 0m0.040s user 0m0.016s sys 0m0.024s I've coded it quite sloppily in places, so the time could be made to drop further with some extra effort. In particular I've made no attempt to cancel common factors when updating the binomial coefficients. Bill. On 28 Aug, 04:42, Bill Hart <[EMAIL PROTECTED]> wrote: > Come to think of it, it is not sufficient to compute the binomial > coefficients separately. One wants to compute each of them from the > previous one. > > Bill. > > On 28 Aug, 04:00, Bill Hart <[EMAIL PROTECTED]> wrote: > > > Yep. After some timing experiments, I think Magma uses only two > > tricks: > > > 1) For length 2 polynomials it just writes the answer down without > > polynomial multiplication (actually GMP has fast computation of > > binomial coefficients, so this wouldn't be hard to implement in sage). > > > 2) Polynomials are shifted if they have trailing zero coefficients > > before the powering is done (in fact I suspect their multiplication > > routine does this rather than their powering code, but I could be > > wrong). > > > Bill. --~--~---------~--~----~------------~-------~--~----~ To post to this group, send email to [email protected] 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/ -~----------~----~----~----~------~----~------~--~---
