#!/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)

3 days ago

## No comments:

Post a Comment