calculation time for 11.5.3

4 views
Skip to first unread message

mike

unread,
Nov 5, 2008, 7:49:16 PM11/5/08
to Study-HTDP
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?
code is:
(define (multiply n x)
(cond
((= x 0) 0)
(else
(add n (multiply n (sub1 x))))))
which is used for:
(define (exponent x n)
(cond
( (= n 0) 1)
(else
(multiply x (exponent x (sub1 n))))))
mike

Geoffrey S. Knauth

unread,
Nov 5, 2008, 9:33:50 PM11/5/08
to study...@googlegroups.com
Not having your add routine, I tried the following, and the printout was interesting.  I'll spare you the output.  Yoda say, Try you must!

(define add +)

(define (multiply n x)
 (printf "(multiply ~a ~a)\n" n x)
 (cond
   ((= x 0) 0)
   (else    (add n (multiply n (sub1 x))))))

(define (exponent x n)
 (printf "(exponent ~a ~a)\n" x n)
 (cond
   ((= n 0) 1)
   (else    (multiply x (exponent x (sub1 n))))))

Oh, by the way.  Your recursive calls to multiply and exponent are not in tail position.

After you have fun looking at the output, you can do what I often do.  Write down ahead of time the output you expected, and then ask yourself, "Now how could I have made that happen myself?"
Reply all
Reply to author
Forward
0 new messages