sicp-ex-2.34


Taking the example of 1 + 3x + 5x³ + x⁵, applying Horner’s rule gives us (((((1x + 0)x + 5)x + 0)x + 3)x + 1). Translated into prefix notation yields (+ (* (+ (* (+ (* (+ (* (+ (* 1 x) 0) x) 5) x) 0) x) 3) x) 1), which reveals the recursive structure:

 (+ (* (+ (* (+ (* (+ (* (+ (* 1 x) 0) x) 5) x) 0) x) 3) x) 1) 
 (+ (* ………………………………………………………………………………………………………………………………… x) 1) 
       (+ (* ………………………………………………………………………………………………… x) 3) 
             etc. 

Which indicates that the function to be used to accumulate will be (+ (* ⟨higher-order termsx) ⟨coefficent⟩):

 (define (horner-eval x coefficient-sequence) 
   (accumulate (lambda (this-coeff higher-terms) 
                 (+ (* higher-terms x) this-coeff)) 
               0 
               coefficient-sequence)) 
  
 (horner-eval 2 (list 1 3 0 5 0 1)) 
 ⇒ 79 
 (horner-eval 2 (list 2 3 0 5 0 1)) ; Expect 1 greater than above. 
 ⇒ 80 
 (horner-eval 2 (list 2 3 0 5 0 2)) ; Expect 2⁵ = 32 greater than above. 
 ⇒ 112 

<< Previous exercise (2.33) | Index | Next exercise (2.35) >>


jz

  
 ;; Accumulates the result of the first and the already-accumulated 
 ;; rest. 
 (define (accumulate op initial sequence) 
   (if (null? sequence) 
       initial 
       (op (car sequence) 
           (accumulate op initial (cdr sequence))))) 
  
  
 (define nil '())  ;; stupid environment ... 
  
 (define (horner-eval x coefficient-sequence) 
   (accumulate (lambda (this-coeff accum-sum) 
                 (+ this-coeff 
                    (* x accum-sum))) 
               0 
               coefficient-sequence)) 
  
 (horner-eval 2 (list 1 3 0 5 0 1))