I wrote up a ridiculously naive polynomial powering function in FLINT.
Here is a basic FLINT program for computing the above powers:
fmpz_poly_t poly, power;
fmpz_poly_init(power);
fmpz_poly_init(poly);
fmpz_poly_set_coeff_ui(poly, 0, 1);
fmpz_poly_set_coeff_ui(poly, 1, 1);
fmpz_poly_power(power, poly, (1UL<<13));
Here are the times:
real 0m1.190s
user 0m0.960s
sys 0m0.232s
If I replace 2^13 with 2^13-1 I get:
real 0m0.758s
user 0m0.628s
sys 0m0.128s
I'm sure there's plenty we can do to speed that up. For a start the
system time could trivially be all but wiped out by allocating all the
required memory up front. There's probably also some FFT caching I
could do but haven't.
Polynomial evaluation should probably be used beyond some point, but
we haven't implemented that yet.
Bill.
On 27 Aug, 18:32, [EMAIL PROTECTED] wrote:
> I was recently contacted by Niell Clift, who is arguably the foremost expert
> on addition chains. Though he's most concerned with computing minimal
> addition chains, which aren't always optimal and can take a ridiculous amount
> of time to compute, I believe that some of the work that he's done can be
> used to construct a rather generic addition chain package. I don't expect to
> beat numeric exponentiation, but polynomial exponentiation seems oddly slow.
>
> Already, there seems to be a cutoff point where my work on addition chains
> can be used to improve the speed of exponentiation.
>
> (x^n)(x+1) constructs the polynomial x^n and evaluates it (this uses my
> polynomial evaluation code)
>
> The for loop performs binary exponentiation (I pick 2^13 and 2^13-1 to make
> this easy). This puzzles me -- binary exponentiation in python currently
> beats the pants off of whatever is getting used for the polynomials. What
> gives?
>
> sage: x = polygen(ZZ)
> sage: n = 2^13
>
> sage: time a = (x+1)^n
> CPU time: 16.82 s, Wall time: 16.82 s
>
> sage: time a = (x^n)(x+1)
> CPU time: 2.47 s, Wall time: 2.47 s
>
> sage: %time
> sage: z = x+1
> sage: for i in range(13):
> ... z = z*z
> CPU time: 2.46 s, Wall time: 2.46 s
>
> sage: n = 2^13-1
>
> sage: time a = (x+1)^n
> CPU time: 3.66 s, Wall time: 3.66 s
>
> sage: time a = (x^n)(x+1)
> CPU time: 0.91 s, Wall time: 0.91 s
>
> sage: %time
> sage: z = x+1
> sage: y = z
> sage: for i in range(12):
> ... z = z*z
> ... y*= z
> CPU time: 1.61 s, Wall time: 1.61 s
--~--~---------~--~----~------------~-------~--~----~
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/
-~----------~----~----~----~------~----~------~--~---
