[plt-scheme] calculation time for 11.5.3

On Nov 5, 2008, at 8:08 PM, mike wrote:

> Using my def for add ,multiply and finally exponent which is
> dependent
> on the def for add and multiply i find calculation times increase
> dramatically as i raise the exponent. (exponent 10 4) takes a long
> long
> time.
>  Can i assume that the nature of the functions is such that the
> number
> of calculations increases hyperbolically?? and not a function of sick
> computer?

Doing this in the "obvious" way, by structural recursion on Peano  
natural numbers, the add function should take linear time, the  
multiply function quadratic time, and the exponent function cubic  
time.  No, wait... that's too easy.

add(n1,n2) takes O(n1) time (assuming that's the parameter you recur  
on).
mult(n1, n2) takes sum_n1(O(n2)) time, i.e. O(n1 * n2) time.
raise(x, n) takes sum_{i=1}^n{x^i}, which is O(x^n) time.

In other words, the time the function takes is approximately equal to  
its answer.  Which is obvious in retrospect, since the only  
fundamental operation it does on answers is add1; you can't get 10^4  
from 0 without doing that operation at least 10^4 times.

On my computer, (raise 10 4) takes well under a second, but (raise 10  
6) takes about four seconds.

BTW, I tried rewriting all three functions to be tail-recursive, and  
it didn't make any noticeable difference.

As long as you're using Peano numbers (whose only constructor is  
add1), this is unavoidable.  You can do much better, of course, if  
you use binary representation:

; A nat-num is either
; 0,
; 2n where n is a nat-num, or
; 2n+1 where n is a nat-num

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.

Homework problem: define a data structure to represent natural  
numbers in binary form (not using the built-in number type), and  
define these functions on that data type.




Stephen Bloch
sbloch at adelphi.edu