# weima learns to program

my attempt to do the exercises in sicp.

## Sunday, June 29, 2008

### sicp exercise 1.33

;  Exercise 1.33. You can obtain an even more general version of accumulate (exercise 1.32) by introducing
;  the notion of a filter on the terms to be combined. That is, combine only those terms derived from
;  values in the range that satisfy a specified condition. The resulting filtered-accumulate abstraction
;  takes the same arguments as accumulate, together with an additional predicate of one argument that
;  specifies the filter. Write filtered-accumulate as a procedure. Show how to express the following
;  using filtered-accumulate:
;  a. the sum of the squares of the prime numbers in the interval a to b (assuming that you have a
;  b. the product of all the positive integers less than n that are relatively prime to n (i.e., all
;  positive integers i < n such that GCD(i,n) = 1).

(define true  #t)
(define false #f)

(define (square num) (* num num))

(define (expmod base exp m)
(cond ((= exp 0) 1)
((even? exp)
(remainder (square (expmod base (/ exp 2) m)) m))
(else
(remainder (* base (expmod base (- exp 1) m)) m))))

(define (fermat-test n)
(define (prime-impl n base)
(= (expmod base n n) base))
(prime-impl n (+ 1 (random (- n 1)))))

(define (prime-test n times)
(cond ((= times 0) true)
((fermat-test n) (prime-test n (- times 1)))
(else false)))

(define (prime? n) (prime-test n 10))

(define (filtered-accumulate-recur combiner filter null-value term a next b)
(if (> a b)
null-value
(if (filter a)
(combiner (term a) (filtered-accumulate-recur combiner filter null-value term (next a) next b))
(filtered-accumulate-recur combiner filter null-value term (next a) next b))))

(define (filtered-accumulate-iter combiner filter null-value term a next b)
(define (iter a result)
(if (> a b)
result
(if (filter a)
(iter (next a) (combiner (term a) result))
(iter (next a) result))))
(iter a null-value))

(define (sum-square-if-prime a b)
(define (next x) (+ x 1))
(filtered-accumulate-iter + prime? 0 square a next b))

(display (sum-square-if-prime 4 10)) (newline)