## Sunday, August 15, 2010

### SICP 1.44: Smoothing a function

From SICP section 1.3.4 Procedures as Returned Values

Exercise 1.44 introduces the idea of smoothing a function, a concept from signal processing. The smoothed version of a function f is the function whose value at x is the average of f(x), f(x + dx), and f(x - dx), where dx is some small value.

We're to write a procedure smooth that takes as its input a procedure that computes f(x) and returns a procedure that computes the smoothed f. Since it is sometimes valuable to repeatedly smooth a function, we also need to show how to generate an n-fold smoothed function using smooth and the repeated procedure from exercise 1.43. The exercise doesn't specify a value for dx, so we'll pass that in as a parameter to smooth.

The smooth procedure is fairy straightforward to implement, but a little bit complicated to test. Here is the implementation:
(define (smooth f dx)  (lambda (x)    (/ (+ (f x)          (f (+ x dx))          (f (- x dx)))       3)))

But what should we use for test data? It would be nice to have some independent data to use to verify that the function works, but we don't have any. We can create some using a spreadsheet though (click the image to enlarge).

You can see from the image the affects of smoothing on the sine wave function. It's already a smooth function, so instead of the intended affect of smoothing out noise, we've just damped the function. Still, this gives us data to test with. Here's the output of our smooth function at 90 and 180 degrees.
> (sin (/ pi 2))1.0> ((smooth sin 0.7) (/ pi 2))0.8432281248563256> (sin pi)1.2246467991473532e-016> ((smooth sin 0.7) pi)7.401486830834377e-017

To complete the exercise we need to write an n-fold smooth function using the repeated function.
(define (n-fold-smooth f dx n)  (repeated (smooth f dx) n))

Repeatedly smoothing the sine function in this way should have the affect of simply damping the function even more.
> ((n-fold-smooth sin 0.7 2) (/ pi 2))0.6297176112540723> ((n-fold-smooth sin 0.7 3) (/ pi 2))0.49659100370209336> ((n-fold-smooth sin 0.7 4) (/ pi 2))0.4017400886852076

Related:

For links to all of the SICP lecture notes and exercises that I've done so far, see The SICP Challenge.

dmi3s said...

(define (impulse-maker a y)
(lambda (x)
(if (= x a)
y
0)))

(define my-impulse-function
(impulse-maker 0 6))

dmi3s said...

Compare:

> ((n-fold-smooth my-impulse-function 0.00001 3) 0)
2
> (+ 0.0 ((smooth (smooth (smooth my-impulse-function 0.00001) 0.00001) 0.00001) 0))
1.5555555555555556