## 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

Anonymous said...

Hey Bill, there's a mistake in your n-fold-smooth procedure, just like dmi3s said.
The corrected version is:

(define (n-fold-smooth f n)
((repeated smooth n) f))

(define dx 0.00001)

(define (smooth f)
(lambda (x) (/ (+ (f (- x dx))
(f x)
(f (+ x dx)))
3.0)))

I defined dx outside the function as the authors of SICP had done this in section 1.3.4 for the deriv procedure used in Newton's method.

You can check that this version of n-fold-smooth gives the correct result by using the procedures given by dmi3s.
You were applying the smoothed function to itself instead of applying smooth to the smoothed function. i.e. You were doing ((smooth f)^n) instead of ((smooth)^n f).

Anonymous said...

Applying smooth to sin results in [(2 cos dx + 1) / 3] sin x.

This confirms that smooth merely scales sin but doesn't change its shape.

Note that for small dx, the above formula can be approximated by (1 - dx² / 3) sin x.

Anonymous said...

Applying n-fold-smooth to sin results in
[(2 cos dx + 1)^n / 3^n] sin x.

This confirms that n-fold-smooth merely scales sin but doesn't change its shape.

Note that for small dx, the above formula can be approximated by [1 - dx^(2n) / 3^n] sin x.

Anonymous said...

Correction to my last comment…

The approximation formula I gave previously is incorrect, it should have been
(1 - n dx² / 3) sin x.