sicp-ex-1.16



<< Previous exercise (1.15) | sicp-solutions | Next exercise (1.17) >>


  
 ;; ex 1.16 
  
 (define (fast-expt b n) 
   (define (iter a b n) 
     (cond ((= n 0) a) 
           ((even? n) (iter a (square b) (/ n 2))) 
           (else (iter (* a b) b (- n 1))))) 
   (iter 1 b n)) 
  
 (define (square x) (* x x)) 
  
 ;; Testing 
  
 (fast-expt 2 0) 
 (fast-expt 2 1) 
 (fast-expt 2 2) 
 (fast-expt 2 4) 
 (fast-expt 2 8) 
 (fast-expt 2 16) 
  
 (fast-expt 2 3) 
 (fast-expt 2 5) 
 (fast-expt 2 10) 
 (fast-expt 2 20) 
  

another solution

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