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/ -~----------~----~----~----~------~----~------~--~---
