Proposal: Better power for Rational
Felipe Lessa
felipe.lessa at gmail.com
Sat Sep 25 13:43:39 EDT 2010
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.
More information about the Libraries
mailing list