Proposal: Better power for Rational

[Felipe Lessa]

On Sat, Sep 25, 2010 at 12:05 PM, Isaac Dupree
<ml at isaac.cedarswampstudios.org> wrote:
> (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-Common-Divisor-Algorithms
[2] http://gmplib.org/manual/Subquadratic-GCD.html#Subquadratic-GCD

-- 
Felipe.