Peter SheatsFreelance Hacker

Exercise 1.16

Posted on Thursday, September 13th, 2007

(define (square x) (* x x))

(define (even? n)
  (= (remainder n 2) 0))

(define (exp b n)
  (exp-iter b n 1))

(define (exp-iter b n a)
  (cond ((= n 1) a)
        ((even? n)(exp-iter (square b)
                            (/ n 2)
                            (square b)))
        (else (* b (exp-iter b (- n 1) a)))))

One Response to
“Exercise 1.16”

• Bao Yu says: June 6th, 2008 at 1:52 am

  I’m not an expert but looks like exp-iter has some recursive in it: the “(else (* b (exp-iter b (- n 1) a)))” part, you can’t evaluate “* b” immediately, this is a delayed evaluation.

  Maybe could do it this way:
  (define (fast-expt b n)
  (if (= n 0) 1 (fast-expt-iter b 1 n)))

  (define (fast-expt-iter b a n)
  (cond ((= n 0) a)
  ((even? n) (fast-expt-iter (* b b) a (/ n 2)))
  (else (fast-expt-iter b (* b a) (- n 1)))))