SICP 問題 2.34（Hornerの方法）

【問題】

x の多項式の、ある x の値での評価は、アキュムレーションとして形式化できる。多項式

a_n・x^n + a_(n-1)・x^(n-1) + … + a_1・x + a_0

は、計算を

(… (a_n・x + a_(n-1))・x) + … + a_1)・x + a_0

と構造化する Horner の方法（Horner's rule）としてよく知られたアルゴリズムで評価する。
つまり、a_n から初め、x を掛け a_(n-1)を足し、x を掛け、これを a_0 になるまで繰り返す。
下の雛形を補って、Horner の方法で多項式を評価する手続きを作れ。
多項式の係数は a_0 から a_n の順に、並びに配置されていると仮定せよ。

(define (horner-eval x coefficient-sequence)
  (accumulate (lambda (this-coeff higher-terms) <??>)
	      0
	      coefficient-sequence))

例えば　x = 2 で、1 + 3x + 5x^3 + x^5 の計算は、
1 + 3x2 + 5x8 + 32
1 + 6 + 40 + 32
79

(horner-eval 2 (list 1 3 0 5 0 1))

と評価する。

【解答】

例によって accumulate の定義を。

(define (accumulate op initial sequence)
  (if (null? sequence)
      initial
      (op (car sequence)
	  (accumulate op initial (cdr sequence)))))

で、Horner の方法を完成させるとこんな感じ

(define (horner-eval x coefficient-sequence)
  (accumulate (lambda (this-coeff higher-terms)
		;x と係数を掛け合わせ、現在の累積値に加算する感じ。
		(+ (* x higher-terms)
		   this-coeff))
	      0
	      coefficient-sequence))

では実験。

gosh> (horner-eval 2 (list 1 3 0 5 0 1))

79

gosh> (horner-eval 2 (list 2 3 1 5 0 1))

84

gosh>

合ってるねぇ。