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

 From: Stephen Bloch (sbloch at adelphi.edu) Date: Sat Nov 8 10:52:09 EST 2008 Previous message: [plt-scheme] calculation time for 11.5.3 Next message: [plt-scheme] web-server struct binding:file - content-type ? Messages sorted by: [date] [thread] [subject] [author]

```>> 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

```

 Posted on the users mailing list. Previous message: [plt-scheme] calculation time for 11.5.3 Next message: [plt-scheme] web-server struct binding:file - content-type ? Messages sorted by: [date] [thread] [subject] [author]