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 this 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 terms ⟩  x   ) ⟨ 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 

 ;; 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)) 
  

 ;; I prefer recursion on the right because it makes it 
 ;; easier to grasp the recursion process. 
  
 (define (horner-eval x coefficient-sequence)  
    (accumulate (lambda (this-coeff higher-terms)  
                  (+ this-coeff (* higher-terms x)))  
                0  
                coefficient-sequence))