2011-09-18

SICP Exercise 1.44: Smoothed Functions

The idea of smoothing a function is an important concept in signal processing. If f is a function and dx is some small number, then the smoothed version of f is the function whose value at a point x is the average of f(x - dx), f(x), and f(x + dx). Write a procedure smooth that takes as input a procedure that computes f and returns a procedure that computes the smoothed f. It is sometimes valuable to repeatedly smooth a function (that is, smooth the smoothed function, and so on) to obtained the n-fold smoothed function. Show how to generate the n-fold smoothed function of any given function using smooth and repeated from exercise 1.43.

Now the book already gives us "some small number" for dx, which was defined in the section on Newton's method as:
(define dx 0.00001)
The selection of dx is fairly arbitrary here, but it'll do for this exercise where we'll reuse dx in producing smooth:
(define (smooth f)
  (lambda (x) (/ (+ (f (- x dx))
                    (f x)
                    (f (+ x dx)))
                 3)))
Our definition of smooth simply calculates f(x - dx), f(x), and f(x + dx), sums them and divides by 3 to produce the mean.

To calculate the n-fold smoothed function we simply produce the procedure that will apply smooth n times to a function, and pass f to this:
(define (n-fold-smooth f n)
  ((repeated smooth n) f))
Let's see it in action:
> (square 6.48074)
41.9999909476
> ((smooth square) 6.48074)
41.99999094766667
> ((n-fold-smooth square 1) 6.48074)
41.99999094766667
> ((n-fold-smooth square 2) 6.48074)
41.99999094773333
> ((n-fold-smooth square 3) 6.48074)
41.99999094779999
> ((n-fold-smooth square 4) 6.48074)
41.99999094786666
> ((n-fold-smooth square 5) 6.48074)
41.99999094793333
> ((n-fold-smooth square 10) 6.48074)
41.999990948266635

1 comment: