Exercise 1.33 asks us to us to write an even more general form of the
accumulateprocedure 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.
filtered-accumulateprocedure 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
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)))
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.
> (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
As luck would have it, we've already seen a
gcdprocedure 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
gcdto define a
coprime?procedure, and use that as our filter. Note that normally a
coprime?procedure should take two parameters. Since
filtered-accumexpects the filter function to take only one parameter,
coprime?is borrowing one of its input parameters, n, from
(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.