# [plt-edu] Re: [plt-scheme] calculation time for 11.5.3

>>* Note that this uses "multiplication", but only the restricted case
*>>* of multiplication by 2. With this representation,
*>>* add(n1, n2) takes O(max(log(n1), log(n2)) time
*>>* mult(n1, n2) takes O(log(n1) * log(n2)) time (assuming you don't
*>>* start doing fast Fourier transforms!)
*>>* raise(x, n) takes O(n*log(x)) time by the obvious algorithm, or
*>>* O(log(n)*log(x)) time by a less-obvious but fairly
*>>* straightforward algorithm.
*>*
*>* Only if you count manipulation of large numbers in Scheme as taking
*>* constant time. I think technically we need to toss in another O(log
*>* n) factor for raise (not for modular exponentiation).
*
Perhaps, if you do it with built-in bignums. If you do it with a
list representation, as I did in my subsequent post, then checking
for even/oddness of n, and halving n, are constant-time operations.
Oh, wait: the last multiplication alone, squaring x^(n/2) to get x^n,
takes time
O(log(x^(n/2))^2) = O(n^2 * log^2(x))
which utterly dwarfs the O(log n) loop and the bignum overhead.
>* And all of this is structurally recursive! --PR
*
Yes, isn't that elegant?
Stephen Bloch
sbloch at adelphi.edu