[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