Proposal: Better power for Rational

Felipe Lessa felipe.lessa at
Sat Sep 25 13:43:39 EDT 2010

On Sat, Sep 25, 2010 at 12:05 PM, Isaac Dupree
<ml at> 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.



More information about the Libraries mailing list