# weima learns to program

my attempt to do the exercises in sicp.

## Thursday, July 17, 2008

### sicp exercise 2.34

#!/usr/bin/guile -s
!#

;  Exercise 2.34. Evaluating a polynomial in x at a given value of x can be formulated as an accumulation.
;  We evaluate the polynomial
;       a(n)x^n + a(n-1)x^(n-1) + ... + a(1)x + a(0)
;  using a well-known algorithm called Horner's rule, which structures the computation as
;      (...(a(n)x + a(n-1))x + ... a(1))x + a(0)
;  In other words, we start with an, multiply by x, add a(n-1), multiply by x, and so on, until
;  we reach a(0). Fill in the following template to produce a procedure that evaluates a
;  polynomial using Horner's rule. Assume that the coefficients of the polynomial are arranged
;  in a sequence, from a(0) through a(n).

;  (define (horner-eval x coefficient-sequence)
;      (accumulate (lambda (this-coeff higher-terms) <??>) 0 coefficient-sequence))
;  For example, to compute 1 + 3^x + 5x^3 + x^5 at x = 2 you would evaluate
;  (horner-eval 2 (list 1 3 0 5 0 1))

(define accumulate (lambda (oper init seq)
(cond ((null? seq) init)
(else (oper (car seq) (accumulate oper init (cdr seq)))))))

(define (horner-eval1 x coeff-seq)
(cond ((null? coeff-seq) 0)
(else (+ (car coeff-seq) (* x (horner-eval1 x (cdr coeff-seq)))))))

(define (horner-eval x coeff-seq)
(accumulate (lambda (term higher) (+ term (* x higher))) 0 coeff-seq))

(display (horner-eval  2 (list 1 1 1 1))) (newline)
(display (horner-eval1 2 (list 1 1 1 1))) (newline)
(display (horner-eval  2 (list 1 3 0 5 0 1))) (newline)
(display (horner-eval1 2 (list 1 3 0 5 0 1))) (newline)