<< Previous exercise (2.33) | Index | Next exercise (2.35) >>
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 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
;; 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))
this is a comment on solution posted by jz. @jz I think calling the variable as accum-sum is bit misleading, as the processing hasn't accumulated any sum yet .
jz