# SICP Chapter 1 Exercises & Solutions

The HTML for this page has been automatically generated by parsing the loosely formatted source code & comments included in my solutions repository (https://github.com/zv/SICP-guile), if you encounter any unformatted solutions, you think you've spotted an error or you have something you'd like to share about the exercises, don't hesitate to leave a comment below (or a pull request on the source repo).

## Exercises Chapter 1

### 1.1

Below is a sequence of expressions. What is the result printed by the

interpreter in response to each expression? Assume that the sequence is to be

evaluated in the order in which it is presented.

(Expressions Contained in Answer Section)

#### Answer

Respectively:

10 scheme@(guile-user)> 10

(+ 5 3 4) scheme@(guile-user)> 12

(- 9 1) scheme@(guile-user)> 8

(/ 6 2) scheme@(guile-user)> 3

(+ (* 2 4) (- 4 6)) scheme@(guile-user)> 6

(define a 3) (define b (+ a 1)) (+ a b (* a b)) scheme@(guile-user)> 19

(= a b) scheme@(guile-user)> #f

(if (and (> b a) (< b (* a b))) b a) scheme@(guile-user)> 4

(cond ((= a 4) 6) ((= b 4) (+ 6 7 a)) (else 25)) scheme@(guile-user)> 16

(+ 2 (if (> b a) b a)) scheme@(guile-user)> 6

(* (cond ((> a b) a) ((< a b) b) (else -1)) (+ a 1)) scheme@(guile-user)> 16

### 1.2

Translate the following expression into prefix form.

5 + 4 + (2 - (3 - (6 + 4/5)))

------------------------–—

3(6 - 2)(2 - 7)

#### Answer

(/ (+ (+ 5 4) (- 2 (- 3 (+ 6 (/ 4 5))))) (* 3 (- 6 2) (- 2 7)))

### 1.3

Define a procedure that takes three numbers as arguments and returns the sum of

the squares of the two larger numbers.

#### Answer

(define (largest-squares x y z) (+ (if (> x y) (square x) (square y)) (if (> y z) (square y) (square z))))

### 1.4

Observe that our model of evaluation allows for combinations whose operators are

compound expressions. Use this observation to describe the behavior of the

following procedure:

(define (a-plus-abs-b a b)

((if (> b 0) + -) a b))

#### Answer

If b is greater than 0, add a to b. Otherwise, subtract b from a

### 1.5

Ben Bitdiddle has invented a test to determine whether the interpreter he is

faced with is using applicative-order evaluation or normal-order evaluation. He

defines the following two procedures:

(define (p) (p))

(define (test x y)

(if (= x 0)

0

y))

Then he evaluates the expression

(test 0 (p))

What behavior will Ben observe with an interpreter that uses applicative-order

evaluation? What behavior will he observe with an interpreter that uses

normal-order evaluation? Explain your answer. (Assume that the evaluation rule

for the special form `if' is the same whether the interpreter is using normal or

applicative order: The predicate expression is evaluated first, and the result

determines whether to evaluate the consequent or the alternative expression.)

#### Answer

An applicative order evaluator would never terminate. The value of `p' is

expanded prior to the logic of `test' being applied.

Conversely, a normal-order evaluator would return 0, it never had the chance to

expand `p'

### 1.6

Alyssa P. Hacker doesn't see why `if' needs to be provided as a special form.

"Why can't I just define it as an ordinary procedure in terms of `cond'?" she

asks. Alyssa's friend Eva Lu Ator claims this can indeed be done, and she

defines a new version of `if':

(define (new-if predicate then-clause else-clause)

(cond (predicate then-clause)

(else else-clause)))

Eva demonstrates the program for Alyssa:

(new-if (= 2 3) 0 5)

5

(new-if (= 1 1) 0 5)

0

Delighted, Alyssa uses `new-if' to rewrite the square-root program:

(define (sqrt-iter guess x)

(new-if (good-enough? guess x)

guess

(sqrt-iter (improve guess x)

x)))

What happens when Alyssa attempts to use this to compute square

roots? Explain.

#### Answer

Any function supplied to `new-if' will be applied, `sqrt-iter' will thus infinitely loop.

### 1.7

The `good-enough?' test used in computing square roots will not be very

effective for finding the square roots of very small numbers. Also, in real

computers, arithmetic operations are almost always performed with limited

precision. This makes our test inadequate for very large numbers. Explain these

statements, with quotes showing how the test fails for small and large

numbers.

An alternative strategy for implementing `good-enough?' is to watch how

`guess' changes from one iteration to the next and to stop when the change

is a very small fraction of the guess. Design a square-root procedure that

uses this kind of end test. Does this work better for small and large

numbers?

#### Answer

(define (fix/sqrt-iter guess last-guess x) (let ([good-enough? (< (abs (- guess last-guess)) 0.001)] [next-guess (average guess (/ x guess))]) (if good-enough? guess (fix/sqrt-iter next-guess guess x))))

### 1.8

Newton's method for cube roots is based on the fact that if y is an

approximation to the cube root of x, then a better approximation is given

by the value

x/y^{2} + 2y

-----–—

3

Use this formula to implement a cube-root procedure analogous to the

square-root procedure. (In section 1.3.4 we will see how to implement

Newton's method in general as an abstraction of these square-root and

cube-root procedures.)

#### Answer

(define (1.8/sqrt-iter guess last-guess x) (let ([good-enough? (< (abs (- guess last-guess)) 0.001)] [next-guess (/ (+ (/ x (square guess)) (* 2 guess)) 3)]) (if good-enough? guess (fix/sqrt-iter next-guess guess x))))

### 1.9

Each of the following two procedures defines a method for adding two

positive integers in terms of the procedures `inc', which increments its

argument by 1, and `dec', which decrements its argument by 1.

(define (+ a b)

(if (= a 0)

b

(inc (+ (dec a) b))))

(define (+ a b)

(if (= a 0)

b

(+ (dec a) (inc b))))

Using the substitution model, illustrate the process generated by each

procedure in evaluating `(+ 4 5)'. Are these processes iterative or

recursive?

#### Answer

The first is recursive:

scheme@(guile-user)> ,trace (+ 4 5)

trace: | (+ 4 5)

trace: | | (+ 3 5)

trace: | | | (+ 2 5)

trace: | | | | (+ 1 5)

trace: | | | | | (+ 0 5)

trace: | | | | | 5

trace: | | | | 6

trace: | | | 7

trace: | | 8

trace: | 9

The second function is iterative

scheme@(guile-user)> ,trace (pl 4 5)

trace: | (pl 4 5)

trace: | | (dec 4)

trace: | | 3

trace: | | (inc 5)

trace: | | 6

trace: | (pl 3 6)

trace: | | (dec 3)

trace: | | 2

trace: | | (inc 6)

trace: | | 7

trace: | (pl 2 7)

trace: | | (dec 2)

trace: | | 1

trace: | | (inc 7)

trace: | | 8

trace: | (pl 1 8)

trace: | | (dec 1)

trace: | | 0

trace: | | (inc 8)

trace: | | 9

trace: | (pl 0 9)

trace: | 9

### 1.10

The following procedure computes a mathematical function called Ackermann's

function.

(define (A x y)

(cond ((= y 0) 0)

((= x 0) (* 2 y))

((= y 1) 2)

(else (A (- x 1)

(A x (- y 1))))))

What are the values of the following expressions?

(A 1 10)

(A 2 4)

(A 3 3)

Consider the following procedures, where A is the procedure defined above:

(define (f n) (A 0 n))

(define (g n) (A 1 n))

(define (h n) (A 2 n))

(define (k n) (* 5 n n))

Give concise mathematical definitions for the functions computed by the

procedures f, g, and h for positive integer values of n. For quote, (k n)

computes 5n^{2}.

#### Answer

A trace of the first Ackermann function shown produces a long list of

recursive calls, which is only exaggerated as `x' increases.

scheme@(guile-user)> ,trace (A 1 10)

trace: | (A 1 10)

trace: | | (A 1 9)

trace: | | | (A 1 8)

trace: | | | | (A 1 7)

trace: | | | | | (A 1 6)

trace: | | | | | | (A 1 5)

trace: | | | | | | | (A 1 4)

trace: | | | | | | | | (A 1 3)

trace: | | | | | | | | | (A 1 2)

trace: | | | | | | | | | | (A 1 1)

trace: | | | | | | | | | | 2

trace: | | | | | | | | | (A 0 2)

trace: | | | | | | | | | 4

trace: | | | | | | | | (A 0 4)

trace: | | | | | | | | 8

trace: | | | | | | | (A 0 8)

trace: | | | | | | | 16

trace: | | | | | | (A 0 16)

trace: | | | | | | 32

trace: | | | | | (A 0 32)

trace: | | | | | 64

trace: | | | | (A 0 64)

trace: | | | | 128

trace: | | | (A 0 128)

trace: | | | 256

trace: | | (A 0 256)

trace: | | 512

trace: | (A 0 512)

trace: | 1024

scheme@(guile-user)> (A 2 4)

$2 = 65536

scheme@(guile-user)> (A 3 3)

$3 = 65536

The functions described can be simplified as follows:

(define (f n) (A 0 n))

→ 2n

(define (g n) (A 1 n))

→ n²

(define (h n) (A 2 n))

→ 2↑n

### 1.11

A function f is defined by the rule that

f(n) = n if n < 3

and

f(n) = f(n - 1) + 2f(n - 2) + 3f(n - 3) if n >= 3.

Write a procedure that computes f by means of a recursive process.

Write a procedure that computes f by means of an iterative process.

#### Answer

(define (rule1.11/recursive n) (if (< n 3) n (+ (rule1.11/recursive (- n 1)) (* 2 (rule1.11/recursive (- n 2))) (* 3 (rule1.11/recursive (- n 3)))))) (define (rule1.11/iterative n) (define (driver count a b c) (if (= count n) c (driver (+ count 1) (+ a (* 2 b) (* 3 c)) a b))) (driver 0 2 1 0))

### 1.12

The following pattern of numbers is called "Pascal's triangle".

1

1 1

1 2 1

1 3 3 1

1 4 6 4 1

The numbers at the edge of the triangle are all 1, and each number inside

the triangle is the sum of the two numbers above it. Write a procedure that

computes elements of Pascal's triangle by means of a recursive process.

#### Answer

(define (pascals-triangle depth) ;; `build-entry' doesn't memoize the finding of each number. You could do ;; so either here or with more changes to `build-row'. (define (build-entry rows col) (cond [(and (= rows 0) (= col 0)) 1] [(or (< col 0) (< rows col)) 0] [else (+ (build-entry (- rows 1) (- col 1)) (build-entry (- rows 1) col))])) (define (build-row ctr length) (if (= ctr (1+ length)) '() (cons (build-entry length ctr) (build-row (+ ctr 1) length)))) (define (build n) (if (= n depth) '() (cons (build-row 0 n) (build (1+ n))))) (build 0))

### 1.13

#### Answer

### 1.14

Draw the tree illustrating the process generated by the `count-change'

procedure of section *Note 1.2.2 in making change for 11 cents. What are

the orders of growth of the space and number of steps used by this process

as the amount to be changed increases?

#### Answer

trace: (count-change 11)

trace: (cc 11 5)

trace: | (cc 11 4)

trace: | | (cc 11 3)

trace: | | | (cc 11 2)

trace: | | | | (cc 11 1)

trace: | | | | | (cc 11 0)

trace: | | | | | 0

trace: | | | | | (first-denomination 1)

trace: | | | | | 1

trace: | | | | | (cc 10 1)

trace: | | | | | | (cc 10 0)

trace: | | | | | | 0

trace: | | | | | | (first-denomination 1)

trace: | | | | | | 1

trace: | | | | | | (cc 9 1)

trace: | | | | | | | (cc 9 0)

trace: | | | | | | | 0

trace: | | | | | | | (first-denomination 1)

trace: | | | | | | | 1

trace: | | | | | | | (cc 8 1)

trace: | | | | | | | | (cc 8 0)

trace: | | | | | | | | 0

trace: | | | | | | | | (first-denomination 1)

trace: | | | | | | | | 1

trace: | | | | | | | | (cc 7 1)

trace: | | | | | | | | | (cc 7 0)

trace: | | | | | | | | | 0

trace: | | | | | | | | | (first-denomination 1)

trace: | | | | | | | | | 1

trace: | | | | | | | | | (cc 6 1)

trace: | | | | | | | | | | (cc 6 0)

trace: | | | | | | | | | | 0

trace: | | | | | | | | | | (first-denomination 1)

trace: | | | | | | | | | | 1

trace: | | | | | | | | | | (cc 5 1)

trace: | | | | | | | | | | | (cc 5 0)

trace: | | | | | | | | | | | 0

trace: | | | | | | | | | | | (first-denomination 1)

trace: | | | | | | | | | | | 1

trace: | | | | | | | | | | | (cc 4 1)

trace: | | | | | | | | | | | | (cc 4 0)

trace: | | | | | | | | | | | | 0

trace: | | | | | | | | | | | | (first-denomination 1)

trace: | | | | | | | | | | | | 1

trace: | | | | | | | | | | | | (cc 3 1)

trace: | | | | | | | | | | | | | (cc 3 0)

trace: | | | | | | | | | | | | | 0

trace: | | | | | | | | | | | | | (first-denomination 1)

trace: | | | | | | | | | | | | | 1

trace: | | | | | | | | | | | | | (cc 2 1)

trace: | | | | | | | | | | | | | 15> (cc 2 0)

trace: | | | | | | | | | | | | | 15< 0

trace: | | | | | | | | | | | | | 15> (first-denomination 1)

trace: | | | | | | | | | | | | | 15< 1

trace: | | | | | | | | | | | | | 15> (cc 1 1)

trace: | | | | | | | | | | | | | 16> (cc 1 0)

trace: | | | | | | | | | | | | | 16< 0

trace: | | | | | | | | | | | | | 16> (first-denomination 1)

trace: | | | | | | | | | | | | | 16< 1

trace: | | | | | | | | | | | | | 16> (cc 0 1)

trace: | | | | | | | | | | | | | 16< 1

trace: | | | | | | | | | | | | | 15< 1

trace: | | | | | | | | | | | | | 1

trace: | | | | | | | | | | | | 1

trace: | | | | | | | | | | | 1

trace: | | | | | | | | | | 1

trace: | | | | | | | | | 1

trace: | | | | | | | | 1

trace: | | | | | | | 1

trace: | | | | | | 1

trace: | | | | | 1

trace: | | | | 1

trace: | | | | (first-denomination 2)

trace: | | | | 5

trace: | | | | (cc 6 2)

trace: | | | | | (cc 6 1)

trace: | | | | | | (cc 6 0)

trace: | | | | | | 0

trace: | | | | | | (first-denomination 1)

trace: | | | | | | 1

trace: | | | | | | (cc 5 1)

trace: | | | | | | | (cc 5 0)

trace: | | | | | | | 0

trace: | | | | | | | (first-denomination 1)

trace: | | | | | | | 1

trace: | | | | | | | (cc 4 1)

trace: | | | | | | | | (cc 4 0)

trace: | | | | | | | | 0

trace: | | | | | | | | (first-denomination 1)

trace: | | | | | | | | 1

trace: | | | | | | | | (cc 3 1)

trace: | | | | | | | | | (cc 3 0)

trace: | | | | | | | | | 0

trace: | | | | | | | | | (first-denomination 1)

trace: | | | | | | | | | 1

trace: | | | | | | | | | (cc 2 1)

trace: | | | | | | | | | | (cc 2 0)

trace: | | | | | | | | | | 0

trace: | | | | | | | | | | (first-denomination 1)

trace: | | | | | | | | | | 1

trace: | | | | | | | | | | (cc 1 1)

trace: | | | | | | | | | | | (cc 1 0)

trace: | | | | | | | | | | | 0

trace: | | | | | | | | | | | (first-denomination 1)

trace: | | | | | | | | | | | 1

trace: | | | | | | | | | | | (cc 0 1)

trace: | | | | | | | | | | | 1

trace: | | | | | | | | | | 1

trace: | | | | | | | | | 1

trace: | | | | | | | | 1

trace: | | | | | | | 1

trace: | | | | | | 1

trace: | | | | | 1

trace: | | | | | (first-denomination 2)

trace: | | | | | 5

trace: | | | | | (cc 1 2)

trace: | | | | | | (cc 1 1)

trace: | | | | | | | (cc 1 0)

trace: | | | | | | | 0

trace: | | | | | | | (first-denomination 1)

trace: | | | | | | | 1

trace: | | | | | | | (cc 0 1)

trace: | | | | | | | 1

trace: | | | | | | 1

trace: | | | | | | (first-denomination 2)

trace: | | | | | | 5

trace: | | | | | | (cc -4 2)

trace: | | | | | | 0

trace: | | | | | 1

trace: | | | | 2

trace: | | | 3

trace: | | | (first-denomination 3)

trace: | | | 10

trace: | | | (cc 1 3)

trace: | | | | (cc 1 2)

trace: | | | | | (cc 1 1)

trace: | | | | | | (cc 1 0)

trace: | | | | | | 0

trace: | | | | | | (first-denomination 1)

trace: | | | | | | 1

trace: | | | | | | (cc 0 1)

trace: | | | | | | 1

trace: | | | | | 1

trace: | | | | | (first-denomination 2)

trace: | | | | | 5

trace: | | | | | (cc -4 2)

trace: | | | | | 0

trace: | | | | 1

trace: | | | | (first-denomination 3)

trace: | | | | 10

trace: | | | | (cc -9 3)

trace: | | | | 0

trace: | | | 1

trace: | | 4

trace: | | (first-denomination 4)

trace: | | 25

trace: | | (cc -14 4)

trace: | | 0

trace: | 4

trace: | (first-denomination 5)

trace: | 50

trace: | (cc -39 5)

trace: | 0

trace: 4

### 1.15

The sine of an angle (specified in radians) can be computed by making use

of the approximation `sin' xapprox x if x is sufficiently small, and the

trigonometric identity

x x

sin x = 3 sin — - 4 sin^{3} —

3 3

to reduce the size of the argument of `sin'. (For purposes of this

exercise an angle is considered "sufficiently small" if its magnitude is

not greater than 0.1 radians.) These ideas are incorporated in the

following procedures:

(define (cube x) (* x x x))

(define (p x) (- (* 3 x) (* 4 (cube x))))

(define (sine angle)

(if (not (> (abs angle) 0.1))

angle

(p (sine (/ angle 3.0)))))

a. How many times is the procedure `p' applied when `(sine 12.15)' is

evaluated?

b. What is the order of growth in space and number of steps (as a function

of a) used by the process generated by the `sine' procedure when `(sine a)'

is evaluated?

#### Answer

a. The procedure is evaluated 5 times b. The order of growth is O(log(n))

### 1.16

Design a procedure that evolves an iterative exponentiation process that

uses successive squaring and uses a logarithmic number of steps, as does

`fast-expt'.

(Hint: Using the observation that (bⁿ/²)²= (b²)ⁿ/², keep, along with the

exponent `n' and the base `b', an additional state variable `a', and define

the state transformation in such a way that the product abⁿ is unchanged

from state to state. At the beginning of the process a is taken to be 1,

and the answer is given by the value of `a' at the end of the process. In

general, the technique of defining an "invariant quantity" that remains

unchanged from state to state is a powerful way to think about the design

of iterative algorithms.)

#### Answer

(define (zv/expt-iter b n a) (cond [(= n 0) a] [(even? n) (zv/expt-iter (* b b) (/ n 2) a)] [else (zv/expt-iter b (- n 1) (* a b))]))

### 1.17

The exponentiation algorithms in this section are based on performing

exponentiation by means of repeated multiplication. In a similar way, one

can perform integer multiplication by means of repeated addition. The

following multiplication procedure (in which it is assumed that our

language can only add, not multiply) is analogous to the `expt' procedure:

(define (* a b)

(if (= b 0)

0

(+ a (* a (- b 1)))))

This algorithm takes a number of steps that is linear in `b'. Now suppose

we include, together with addition, operations `double', which doubles an

integer, and `halve', which divides an (even) integer by 2. Using these,

design a multiplication procedure analogous to `fast-expt' that uses a

logarithmic number of steps.

#### Answer

(define (1.17/fast-* a b) (define (double x) (+ x x)) (define (halve x) (/ x 2)) (cond ((= b 0) 0) ((even? b) (double (* a (halve b)))) (else (+ a (* a (- b 1))))))

### 1.18

#### Answer

### 1.19

There is a clever algorithm for computing the Fibonacci numbers in a

logarithmic number of steps. Recall the transformation of the state

variables a and b in the fib-iter process of 1.2.2: a ← a + b and b ← a.

Call this transformation T, and observe that applying T over and over again

n times, starting with 1 and 0, produces the pair Fib(n + 1) and Fib(n) .

In other words, the Fibonacci numbers are produced by applying T n, the

n-th power of the transformation T, starting with the pair (1, 0). Now

consider T to be the special case of p = 0 and q = 1 in a family of

transformations T_{pq} , where T_{pq} transforms the pair(a, b) according to a

← bq + aq + ap and b ← bp + aq .

Show that if we apply such a transformation T_{pq} twice, the effect is the

same as using a single transformation T_{p}′q′ of the same form, and compute

p′ and q′ in terms of p and q .

This gives us an explicit way to square these transformations, and thus we

can compute T n using successive squaring, as in the fast-expt procedure.

Put this all together to complete the following procedure, which runs in a

logarithmic number of steps:

#### Answer

(define (1.19/fib n) (1.19/fib-iter 1 0 0 1 n)) (define (1.19/fib-iter a b p q count) (cond ((= count 0) b) ((even? count) (1.19/fib-iter a b (+ (square p) (square q)) ; compute p' (+ (* 2 p q) (square q)) ; compute q' (/ count 2))) (else (1.19/fib-iter (+ (* b q) (* a q) (* a p)) (+ (* b p) (* a q)) p q (- count 1))))) ;; TODO XXX write test

### 1.20

The process that a procedure generates is of course dependent on the rules

used by the interpreter. As an quote, consider the iterative `gcd'

procedure given above. Suppose we were to interpret this procedure using

normal-order evaluation, as discussed in section *Note 1-1-5. (The

normal-order-evaluation rule for `if' is described in *Note Exercise 1-5)

Using the substitution method (for normal order), illustrate the process

generated in evaluating `(gcd 206 40)' and indicate the `remainder'

operations that are actually performed. How many `remainder' operations are

actually performed in the normal-order evaluation of `(gcd 206 40)'? In the

applicative-order evaluation?

#### Answer

Performs 18 `remainder' operations

### 1.21

Use the smallest-divisor procedure to find the smallest divisor of each of

the following numbers: 199, 1999, 19999.

#### Answer

(define (divides? a b) (= (remainder b a) 0)) (define (find-divisor n test-divisor) (cond ((> (square test-divisor) n) n) ((divides? test-divisor n) test-divisor) (else (find-divisor n (+ test-divisor 1))))) (define (smallest-divisor n) (find-divisor n 2)) ;; TODO XXX write test ;; (format #f "~a" (for-each smallest-divisor '(199 1999 1999)))

### 1.22

Most Lisp implementations include a primitive called `runtime' that returns

an integer that specifies the amount of time the system has been running

(measured, for quote, in microseconds). The following `timed-prime-test'

procedure, when called with an integer n, prints n and checks to see if n

is prime. If n is prime, the procedure prints three asterisks followed by

the amount of time used in performing the test.

(define (timed-prime-test n)

(newline)

(display n)

(start-prime-test n (current-time)))

(define (start-prime-test n start-time)

(if (prime? n)

(report-prime (- (current-time) start-time))))

(define (report-prime elapsed-time)

(display " ***** ")

(display elapsed-time)

#t)

Using this procedure, write a procedure `search-for-primes' that

checks the primality of consecutive odd integers in a specified range. Use

your procedure to find the three smallest primes larger than 1000; larger

than 10,000; larger than 100,000; larger than 1,000,000. Note the time

needed to test each prime. Since the testing algorithm has order of growth

of [theta](_[sqrt]_{(n)}), you should expect that testing for primes around

10,000 should take about _[sqrt]_{(10)} times as long as testing for primes

around 1000. Do your timing data bear this out? How well do the data for

100,000 and 1,000,000 support the _[sqrt]_{(n)} prediction? Is your result

compatible with the notion that programs on your machine run in time

proportional to the number of steps required for the computation?

#### Answer

(define (prime? n) (= n (smallest-divisor n))) (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 (search-for-primes start) (define (is-prime? n) (cond [(even? n) #f] [(< n 0) #f] [(timed-prime-test n) #t] [else (is-prime? (- n 2))])) (define (driver n primes count) (cond [(even? n) (driver (+ n 1) primes count)] [(= count 3) primes] [(is-prime? n) (driver (+ n 2) (cons n primes) (+ count 1))] [else (driver (+ n 2) primes count)])) (driver start '() 0))

### 1.23

The `smallest-divisor' procedure shown at the start of this section does

lots of needless testing: After it checks to see if the number is divisible

by 2 there is no point in checking to see if it is divisible by any larger

even numbers. This suggests that the values used for `test-divisor' should

not be 2, 3, 4, 5, 6, …, but rather 2, 3, 5, 7, 9, …. To implement this

change, define a procedure `next' that returns 3 if its input is equal to 2

and otherwise returns its input plus 2. Modify the `smallest-divisor'

procedure to use `(next test-divisor)' instead of `(+ test-divisor 1)'.

With `timed-prime-test' incorporating this modified version of

`smallest-divisor', run the test for each of the 12 primes found Note in 1.22

Since this modification halves the number of test steps, you should expect

it to run about twice as fast. Is this expectation confirmed? If not, what

is the observed ratio of the speeds of the two algorithms, and how do you

explain the fact that it is different from 2?

#### Answer

(define (1.23/next n) (if (= n 2) 3 (+ n 2)))

### 1.24

#### Answer

### 1.25

Alyssa P. Hacker complains that we went to a lot of extra work in writing

`expmod'. After all, she says, since we already know how to compute

exponentials, we could have simply written

(define (expmod base exp m)

(remainder (fast-expt base exp) m))

Is she correct? Would this procedure serve as well for our fast prime

tester? Explain.

#### Answer

Depending on the behavior of large values of `base' and `exp' combined with the system's handling of large numbers, it is either a middling gain or an

### 1.26

Louis Reasoner is having great difficulty doing *Note Exercise 1.24. His

`fast-prime?' test seems to run more slowly than his `prime?' test. Louis

calls his friend Eva Lu Ator over to help. When they examine Louis's code,

they find that he has rewritten the `expmod' procedure to use an explicit

multiplication, rather than calling `square':

(define (expmod base exp m)

(cond ((= exp 0) 1)

((even? exp)

(remainder (* (expmod base (/ exp 2) m)

(expmod base (/ exp 2) m))

m))

(else

(remainder (* base (expmod base (- exp 1) m))

m))))

"I don't see what difference that could make," says Louis. "I do."

says Eva. "By writing the procedure like that, you have transformed the

[theta](`log' n) process into a [theta](n) process." Explain.

#### Answer

Assuming the computer doesn't perform any sort of sophisticated memoization, effectively each step is performing twice as much work for n steps, e.g n

^{2}, trimming the speed of the original implementation down to

### 1.27

#### Answer

### 1.28

#### Answer

### 1.30

The sum procedure above generates a linear recursion. The procedure can be

rewritten so that the sum is performed iteratively.

#### Answer

(define (1.30/sum term a next b) (define (iter a result) (if (> a b) result (iter (next a) (+ (term a) result)))) (iter a 0))

### 1.31

1. The `sum' procedure is only the simplest of a vast number of similar

abstractions that can be captured as higher-order procedures. Write an

analogous procedure called product that returns the product of the values

of a function at points over a given range. Show how to define factorial in

terms of product. Also use product to compute approximations to π using the

formula:

π/4 = 2/3 ⋅ 4/3 ⋅ 4/5 ⋅ 6/5 ⋅ 6/7 ⋅ 8/7

2. If your product procedure generates a recursive process, write one that

generates an iterative process. If it generates an iterative process, write

one that generates a recursive process.

#### Answer

(define (recursive-product term a next b) (if (> a b) a) (* (term a) (recursive-product term (next a) next b))) (define (iterative-product term a next b) (define (iter a result) (if (> a b) result (iter (next a) (* (term a) result)))) (iter a 0)) (define (1.31/factorial n) (if (zero? n) 1 (iterative-product identity 1 inc n))) (define (1.31/pi-approximate n) (define (fnth nth) (if (even? nth) (/ (double nth) (inc (double nth))) (/ (inc (double nth)) (double nth)))) (* 4.0 (iterative-product fnth 0 inc n)))

### 1.32

1. Show that sum and product (Exercise 1.31) are both special cases of a still

more general notion called accumulate that combines a collection of terms,

using some general accumulation function:

(accumulate

combiner null-value term a next b)

Accumulate takes as arguments the same term and range specifications as sum

and product, together with a combiner procedure (of two arguments) that

specifies how the current term is to be combined with the accumulation of

the preceding terms and a null-value that specifies what base value to use

when the terms run out. Write accumulate and show how sum and product can

both be defined as simple calls to accumulate.

2. If your accumulate procedure generates a recursive process, write one

that generates an iterative process. If it generates an iterative process,

write one that generates a recursive process.

#### Answer

(define (1.32/recursive-accumulate combiner null term a next b) (if (> a b) a (combiner (term a) (1.32/recursive-accumulate combiner null term (next a) next b)))) (define (1.32/iterative-accumulate combiner null term a next b) (define (fold-left n acc) (if (> n b) acc (fold-left (next n) (combiner (term n) acc)))) (fold-left a null)) ;; XXX: add to test ;; (1.32/iterative-accumulate * 1 identity 1 inc 5) => 120

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

1. the sum of the squares of the prime numbers in the interval a to b

(assuming that you have a prime? predicate already written)

2. 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).

#### Answer

(define (1.33/filtered-accumulate combiner null term a next b filter) (if (> a b) null (if (filter a) (combiner (term a) (1.33/filtered-accumulate combiner null term (next a) next b filter)) (1.33/filtered-accumulate combiner null term (next a) next b filter)))) (define (1.33/sum-of-prime-squares a b) (1.33/filtered-accumulate + 0 square a inc b prime?)) (define (1.33/coprimes n) (1.33/filtered-accumulate * 1 identity 1 inc n (λ (i) (= 1 (gcd i n)))))

### 1.34

Suppose we define the procedure

(define (f g) (g 2))

Then we have

(f square)

4

(f (lambda (z) (* z (+ z 1))))

6

What happens if we (perversely) ask the interpreter to evaluate the

combination (f f)?

Explain.

#### Answer

### 1.35

Show that the golden ratio φ (1.2.2) is a fixed point of the transformation

x↦1+1/x, and use this fact to compute φ by means of the fixed-point

procedure.

#### Answer

(define (1.35/find-golden-ratio) (fixed-point (λ (n) (+ 1 (/ 1 n))) 1))

### 1.36

#### Answer

### 1.37

a. An infinite "continued fraction" is an expression of the form

N_{1}

f = ----------------–—

N_{2}

D_{1} + ----------–—

N_{3}

D_{2} + ----–—

D_{3} + …

As an quote, one can show that the infinite continued

fraction expansion with the Nᵢ and the Dᵢ all equal to 1

produces 1/φ, where φ is the golden ratio (described

in section *Note 1.2.2). One way to approximate an

infinite continued fraction is to truncate the expansion

after a given number of terms. Such a truncation–a

so-called finite continued fraction "k-term finite continued

fraction"–has the form

N_{1}

------------–—

N_{2}

D_{1} + ------–—

… N_{K}

+ –—

D_{K}

Suppose that `n' and `d' are procedures of one argument (the

term index i) that return the Nᵢ and Dᵢ of the terms of the

continued fraction. Define a procedure `cont-frac' such that

evaluating `(cont-frac n d k)' computes the value of the

k-term finite continued fraction. Check your procedure by

approximating 1/φ using

(cont-frac (lambda (i) 1.0)

(lambda (i) 1.0)

k)

for successive values of `k'. How large must you make `k' in

order to get an approximation that is accurate to 4 decimal

places?

b. If your `cont-frac' procedure generates a recursive process,

write one that generates an iterative process. If it

generates an iterative process, write one that generates a

recursive process.

#### Answer

(define (1.37/cont-frac-recursive n d kth) (define (nth-continuation nth) (if (> nth kth) (d nth) (/ (n nth) (+ (d nth) (nth-continuation (inc nth)))))) (nth-continuation 1)) (define (1.37/cont-frac-iter n d kth) (define (nth-continuation nth acc) (if (> nth kth) acc (nth-continuation (inc nth) (/ (n nth) (+ (d nth) acc))))) (nth-continuation 1 0)) (define cont-frac 1.37/cont-frac-iter)

### 1.38

In 1737, the Swiss mathematician Leonhard Euler published a memoir `De

Fractionibus Continuis', which included a continued fraction expansion for

e - 2, where e is the base of the natural logarithms. In this fraction, the

nᵢ are all 1, and the Dᵢ are successively 1, 2, 1, 1, 4, 1, 1, 6, 1, 1,

8, …. Write a program that uses your `cont-frac' procedure from Exercise

1.37 to approximate e, based on Euler's expansion.

#### Answer

(define (e-2 k) (cont-frac (λ (i) 1.0) (λ (n) (if (= 0 (modulo (+ n 1) 3)) (* 2 (/ (+ n 1) 3)) 1)) k))

### 1.39

A continued fraction representation of the

tangent function was published in 1770 by the German mathematician

J.H. Lambert:

x

tan x = ----------–—

x^{2}

1 - ------–—

x^{2}

3 - --–—

5 - …

where x is in radians. Define a procedure `(tan-cf x k)' that

computes an approximation to the tangent function based on

Lambert's formula. `K' specifies the number of terms to compute,

as in *Note Exercise 1.37

#### Answer

(define (1.39/tan-cf x k) (cont-frac (λ (i) (if (= i 1) x (* -1.0 (* x x)))) (λ (i) (- (* i 2) 1.0)) k))

### 1.40

Define a procedure cubic that can be used together with the newtons-method

procedure in expressions of the form

(newtons-method (cubic a b c) 1)

to approximate zeros of the cubic x³+ax²+bx+c.

#### Answer

(define (cubic a b c) (λ (x) (+ (* x x x) (* a (* x x)) (* b x) c)))

### 1.41

Define a procedure double that takes a procedure of one argument as

argument and returns a procedure that applies the original procedure twice.

For quote, if inc is a procedure that adds 1 to its argument, then

(double inc) should be a procedure that adds 2. What value is returned by

(((double (double double)) inc) 5)

?

#### Answer

(define (1.41/double fn) (λ (n) (fn (fn n))))

### 1.42

Let f and g be two one-argument functions. The composition f after g is

defined to be the function x↦f(g(x)). Define a procedure compose that

implements composition. For quote, if inc is a procedure that adds 1 to

its argument,

((compose square inc) 6)

49

#### Answer

(define (1.42/compose f g) (λ (n) (f (g n))))

### 1.43

If f is a numerical function and n is a positive integer, then we can form

the nth repeated application of f, which is defined to be the function

whose value at x is f(f(…(f(x))…)). For quote, if f is the function

x↦x+1, then the nth repeated application of f is the function x↦x+n. If f

is the operation of squaring a number, then the nth repeated application of

f is the function that raises its argument to the 2n-th power. Write a

procedure that takes as inputs a procedure that computes f and a positive

integer n and returns the procedure that computes the nth repeated

application of f. Your procedure should be able to be used as follows:

((repeated square 2) 5)

625

Hint: You may find it convenient to use compose from Exercise 1.42.

#### Answer

(define (1.43/repeated-apply fn times) (if (= times 1) (λ (n) (fn n)) (λ (n) (fn ((1.43/repeated-apply fn (- times 1)) n)))))

### 1.44

The idea of smoothing a function is an important concept in signal

processing. If f is a function and dx is some small number, then the

smoothed version of f is the function whose value at a point x is the

average of f(x−dx), f(x), and f(x+dx). Write a procedure smooth that takes

as input a procedure that computes f and returns a procedure that computes

the smoothed f. It is sometimes valuable to repeatedly smooth a function

(that is, smooth the smoothed function, and so on) to obtain the n-fold

smoothed function. Show how to generate the n-fold smoothed function of any

given function using smooth and repeated from Exercise 1.43.

#### Answer

(define (1.44/smooth f) (λ (x) (/ (+ (f (- x dx)) (f x) (f (+ x dx))) 3)))

### 1.45

#### Answer

### 1.46

Several of the numerical methods described in this chapter are instances of

an extremely general computational strategy known as iterative improvement.

Iterative improvement says that, to compute something, we start with an

initial guess for the answer, test if the guess is good enough, and

otherwise improve the guess and continue the process using the improved

guess as the new guess. Write a procedure iterative-improve that takes two

procedures as arguments: a method for telling whether a guess is good

enough and a method for improving a guess. Iterative-improve should return

as its value a procedure that takes a guess as argument and keeps improving

the guess until it is good enough. Rewrite the sqrt procedure of 1.1.7 and

the fixed-point procedure of 1.3.3 in terms of iterative-improve.

#### Answer

(define (iterative-improve good-enough? improve) (λ (guess) (let ([improved (improve guess)]) (if (good-enough? guess improved) guess ((iterative-improve good-enough? improve) improved))))) (define (1.46/iterative-sqrt n) (iterative-improve (λ (guess improved) (< (abs (- guess improved)) 0.001)) (λ (guess) (average guess (/ n guess))))) (define (1.46/fixed-point f first-guess) ((iterative-improve (λ (guess) (< (abs (- (f guess) guess)) 0.00001)) (λ (guess) (f guess))) first-guess))

## Comments

You can add a comment to this page by writing one on it's Github Issue Page