On Sat, Sep 25, 2010 at 12:05 PM, Isaac Dupree
(better names would be good if these are going to be exported though! But I don't think they need to be exported, unless hmm, is removing 'gcd' an *asymptotic* speedup for large integers?)
Calculating the GCD takes time "O(M(N)*log(N)), where M(N) is the time for multiplying two N-limb numbers" [1,2]. 'ratPow n e' takes at most O(M(N)*log(E)), where N is the size of the result and E is the size of the exponent. So with this optimization we go from O(M(N)*(log(E)+log(N))) to O(M(N)*log(E)). If we assume E to be constant and assume that I didn't do anything wrong, then it's an asymptotic improvement. [1] http://gmplib.org/manual/Greatest-Common-Divisor-Algorithms.html#Greatest-Co... [2] http://gmplib.org/manual/Subquadratic-GCD.html#Subquadratic-GCD -- Felipe.