Sunday, May 16, 2010

SICP Exercise 1.33: Filtered Accumulator

From SICP section 1.3.1 Procedures as Arguments

Exercise 1.33 asks us to us to write an even more general form of the accumulate procedure that we wrote in 1.32. A filtered accumulate procedure should combine only those terms in a specified range that meet a specified condition. The new procedure will take the same arguments as the old one, plus an additional argument that specifies the filtering function.

Once we've written the new procedure we need to test it by using it to write two additional procedures. The first will find the sum of the squares of the prime numbers in a given range, and the second will find the product of all the positive integers less than n that are relatively prime to n.

The filtered-accumulate procedure should be very similar to what we saw in the last exercise. The only difference is that we check each new value to see if it passes through the filter before applying the combiner function.
(define (filtered-accum filter combiner null-value term a next b)
(if (> a b)
(if (filter a)
(combiner (term a)
(filtered-accum filter combiner null-value term (next a) next b))
(filtered-accum filter combiner null-value term (next a) next b))))

Note that we're filtering on the value of a, not the value of (term a).

Sum of squared primes

We came up with several different ways to test if a number is prime in section 1.2.6. You can choose any implementation you like, but I'm going to use the fast-prime? procedure from exercises 1.22 and 1.23 (shown here in block structure).
(define (fast-prime? n)
(define (smallest-divisor n)
(define (find-divisor n test-divisor)
(define (next x)
(if (= x 2) 3 (+ x 2)))
(define (divides? a b)
(= (remainder b a) 0))
(cond ((> (square test-divisor) n) n)
((divides? test-divisor n) test-divisor)
(else (find-divisor n (next test-divisor)))))
(find-divisor n 2))
(= n (smallest-divisor n)))

Using fast-prime? as a filtering function, we can implement a procedure to sum the square of primes in a given range.
(define (sum-squared-primes a b)
(filtered-accum fast-prime? + 0 square a inc b))

(define (inc x) (+ x 1))

(define (square x)
(* x x))

We can use a few small examples to test with.

22 + 32 = 13
22 + 32 + 52 = 38
22 + 32 + 52 + 72 = 87

> (sum-squared-primes 2 3)
> (sum-squared-primes 2 6)
> (sum-squared-primes 2 10)

Procuct of coprimes

The second challenge was to find the product of all the positive integers less than n that are relatively prime (coprime) to n. In other words, multiply together all positive integers i < n such that

gcd(i, n) = 1

As luck would have it, we've already seen a gcd procedure too. SICP section 1.2.5 was all about finding greatest common divisors using Euclid's algorithm.
(define (gcd a b)
(if (= b 0)
(gcd b (remainder a b))))

We can use gcd to define a coprime? procedure, and use that as our filter. Note that normally a coprime? procedure should take two parameters. Since filtered-accum expects the filter function to take only one parameter, coprime? is borrowing one of its input parameters, n, from product-of-coprimes.
(define (product-of-coprimes n)
(define (coprime? i)
(= 1 (gcd i n)))
(filtered-accum coprime? * 1 identity 1 inc (- n 1)))

(define (identity x) x)

Again, I'm only going to test with a few small samples, since the results can potentially get very big, very fast. A quick mental check reveals that 3, 7, and 9 are the only values less than 10 that are also coprime to 10.
> (product-of-coprimes 10)

All values less than a prime number are coprime to that number, so the product of coprimes to 11 should result in the product of all the values from 2 to 10, or 10!.
> (product-of-coprimes 11)

You can check that and any other inputs with a calculator.


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


Anonymous said...

Hi Bill. I'm currently trying myself on solving these problems too and I've cracked 1.3 rather easily. But what about this? We have almost the same solution ant it's not so hard to understand what does the code do - every line except the last one.
Let's call it "else-clause":
(filtered-accum filter combiner null-value term (next a) next b))))
Why do we need this? I know that program doesn't work without it, but why? I can't make an algorithm in my head, so i'm totally stuck on it. If we look at the code without the line, everything looks logical - if the value fits the filter, than we call (combiner x y), as we did in 1.32. But if not, why don't we just skip? Thank you in advance and sorry for my English:)

Bill the Lizard said...


That line accumulates all the remaining terms except for a. If the value fits the filter we call (combiner x y) as you said. That combines the current term with the remaining terms in the sequence. If the value doesn't pass the filter, we want just the remaining terms.

Anonymous said...

Thank you for your answer and for writing all those excersises with explanations. Really usefull things.