[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