Exercises of Chapter 1
1.1
Omit.
1.2
(/ (+ 5 4 ( 2 ( 3 (+ 6 (/ 4 5)))))
(* 3 ( 6 2) ( 2 7)))
1.3
Define a procedure that take three numbers as arguments and returns the sum of the squares of the two larger numbers.
(define (squaresumlargetwo a b c)
(define (squaresum x y)
(+ (* x x) (* y y)))
(cond ((and (< c a) (< c b)) (squaresum a b))
((and (< a b) (< a c)) (squaresum b c))
((and (< b c) (< b a)) (squaresum a c))
((= a b) (squaresum b c))
((= a c) (squaresum a b))
((= b c) (squaresum a b))
))
(squaresumlargetwo 3 3 3)
1.4
Observe that our model of evaluation allows for combinations whose operators are compound expressions.
(define (aplusabsb a b)
((if (> b 0) + ) a b))
1.5
Determine whether interpreter is using applicativeorder evaluation or normalorder evaluation. There are two procedures defined as follows:
(define (p) (p))
(define (test x y)
(if (= x 0) 0 y))
;; then evaluate the expression
(test 0 (p))
What behavior will be observed with an interpreter that uses applicativeorder evaluation? What behavior will be observed with an interpreter that uses normalorder evaluation? (Assume that the evaluation rule for the special form if
is the same for both cases: the predicate expression is evaluated first, and the result determines whether to evaluate the consequent or the alternative expression).
The normalorder will fully expand and notice the predicate is true and return 0; However, the applicativeorder will try to evaluate (p)
first and apply that, but it is a recursive call to (p)
itself, so, following this rule, it ends up with an infinite loop.
1.6
Why if
has to be a special form?
(define (newif predicate thenclause elseclause)
(cond (predicate thenclause)
(else elseclause)))
Delighted, Alyssa uses newif
to rewrite the squareroot program:
(define (sqrtiter guess x)
(newif (goodenough? guess x)
guess
(sqrtiter (improve guess x)
x)))
What happens when Alyssa attempts to use this to compute square roots? Explain.
Because the newif
is not a special form, so the subexpressions need to be evaluated before we can apply the newif
to the operands. However, the third formal parameter is a recursive call to sqrtiter
, which will lead to infinite evaluation loop for subexpressions. A dead loop.
1.7
The goodenough?
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 examples showing how the test fails for small and large numbers.
An alternative strategy for implementing goodenough?
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 squareroot procedure that uses this kind of end test. Does this work better for small and large
A: For very small numbers: assume \(t\) is the tolerance we set for the goodenough?
procedure, and \(\varepsilon\) is a very small number that is smaller than the tolerance we set. When the guess approaches to a point where \(guess^2 < (t + \varepsilon)\), than the absolute difference between \(guess^2\) and \(\varepsilon\) is always in the tolerance range but the \(guess\) right now is not necessary the right answer. Example (small number): Let \(\varepsilon = 0.0000001\), start \(guess\) from 1.0.
For very large numbers, what will happen if the arithmetic operations are performed with limited precision? For large numbers, when the precision digits runs out, we might get stuck at a number which is not the answer but we are not able to proceed because the goodenough?
procedure is unable to tell the difference because of precision overflow. Then the procedure will continue forever without convergence.
How floatingpoint numbers work
The idea is to compose a number of two main parts:
 A significand that contains the number’s digits. Negative significands represent negative numbers.
 An exponent that says where the decimal (or binary) point is placed relative to the beginning of the significand. Negative exponents represent numbers that are very small (i.e. close to zero).
Such a format satisfies all the requirements:
 It can represent numbers at wildly different magnitudes (limited by the length of the exponent)
 It provides the same relative accuracy at all magnitudes (limited by the length of the significand)
 It allows calculations across magnitudes: multiplying a very large and a very small number preserves the accuracy of both in the result.
Decimal floatingpoint numbers usually take the form of a scientific notation with an explicit point always between the 1st and 2nd digits.
Implementing it another way:
(define (sqrt x)
(define tolerance 0.01) ;; when changed ratio is less than 1%
(define (average a b) (/ (+ a b) 2))
(define (goodenough? oldguess newguess)
(< (/ (abs ( oldguess newguess)) ;; if the changed ration is smaller than tolerance
oldguess)
tolerance))
(define (improve guess) ;; improve the guess
(average (/ x guess) guess))
(define (sqrtiter guess) ;; iteration
(if (goodenough? guess (improve guess)) ;; if further improving only changes a small ratio
guess
(sqrtiter (improve guess))))
(sqrtiter 1.0))
(sqrt 3)
1.8
Replace the approximation of the square root procedure with: [ \frac{x/y^2 + 2y}{3} ]
(define (cubert x)
(define tolerance 0.0001)
(define goodenough?
(lambda (guess)
(< (abs ( (* guess guess guess)
x))
tolerance)))
(define improve
(lambda (y)
(/ (+ (/ x (* y y))
(* 2 y))
3)))
(define cbrtiter
(lambda (guess)
(if (goodenough? guess)
guess
(cbrtiter (improve guess)))))
(cbrtiter 1.0))
(cubert 23)
1.9
Considering the following two procedure of adding numbers:
;; first procedure, recursive process
(define (+ a b)
(if (= a 0)
b
(inc (+ (dec a) b))))
;; second procedure, iterative process
(define (+ a b)
(if (= a 0)
b
(+ (dec a) (inc b))))
illustrate the process generated by each procedure in evaluating (+ 4 5)
;; first one
(+ 4 5)
(inc (+ 3 5))
(inc (inc (+ 2 5)
(inc (inc (inc (+ 1 5))))
(inc (inc (inc (inc (+ 0 5)))))
(inc (inc (inc (inc 5))))
(inc (inc (inc 6)))
(inc (inc 7))
(inc 8)
9
;; second one
(+ 4 5)
(+ (dec 4) (inc 5))
(+ 3 6)
(+ (dec 3) (inc 6))
(+ 2 7)
(+ (dec 2) (inc 7))
(+ 1 8)
(+ (dec 1) (inc 8))
(+ 0 9)
9
As we can see, the first procedure creates a recursive shape. While the second one creates a iterative shape.
1.10
The following procedure computes a mathematical function called Armani’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))))))
(A 2 4)
What are the values of the following expressions?
(A 1 10)
(A 0 (A 1 9))
(A 0 (A 0 (A 1 8)))
(A 0 (A 0 (A 0 (A 1 7))))
;; ... 2 * 2 * 2 * ...
;; 2^10
(A 2 4)
(A 1 (A 2 3))
(A 1 (A 1 (A 2 2)))
(A 1 (A 1 (A 1 (A 2 1))))
(A 1 (A 1 (A 1 2)))
(A 1 (A 1 (A 0 (A 1 1))))
(A 1 (A 1 (A 0 2)))
(A 1 (A 1 4))
(A 1 (A 0 (A 1 3)))
(A 1 (A 0 8))
(A 1 16)
;; 2^16 = 2^{2^{4}}
(A 3 3)
;; 2^{2^{2^3}}
Consider the following procedures, where A is the procedure defined above:
(define (f n) (A 0 n)) ;; 2n
(define (g n) (A 1 n)) ;; 2^n
(define (h n) (A 2 n)) ;; 2^{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 example, (k, n)
computes \(5n^2\).
1.11
A function \(f\) is defined as follows:
Write a procedure that computes \(f\) by means of an iterative process.
(define (f n)
(cond ((< n 3) n)
(else (fiter 1 2 3 ( n 3)))))
(define (fiter 1st 2ec 3rd count)
(cond ((= count 0) 3rd)
(else (fiter 2ec
3rd
(+ (* 3 1st)
(* 2 2ec)
3rd)
( count 1)))))
(f 7)
;; 1 2 3 10 (10+6+6)=22
1.12
The following pattern of numbers is Pascal’s triangle.
Write a procedure that computes elements of Pascal’s triangle by means of a recursive process.
The goal is to write a recursive procedure (pastri r c)
that gives the number located at the \(r\) row and \(c\) column in the Pascal’s triangle.
;; notice that there are special cases
;; 1. at the edge
;; 2. at the top
(define (pastri r c)
(cond ((or (= r c)
(= c 0))
1)
(else (+ (pastri ( r 1) ;; the line above
( c 1));; the column to the left
(pastri ( r 1) ;; the line above
c))))) ;; the same column
(pastri 6 4)
1.13
Prove that \(Fib(n)\) is the closest integer to \(\phi^n / \sqrt{5}\), where \(\phi = (1+\sqrt{5}) / 2\) Hint: Let \(\psi = (1  \sqrt{5}) / 2\). Use induction and the definition of the Fibonacci numbers to prove that \(Fib(n) = (\phi^n  \psi^n) / \sqrt{5}\)
 Prove that \(Fib(n) = (\phi^n  \psi^n) / \sqrt{5}\) by verifying for \(n = 0, 1\), and use the \(Fib(n) = Fib(n1) + Fib(n2)\) equation to further prove it. Notice that \(\phi^2 = \frac{3 + \sqrt{5}}{2}\) and \(\psi^2 = \frac{3  \sqrt{5}}{2}\).
 How to prove that \(Fib(n)\) is the closest integer then? First it is an integer. And the difference between \(Fib(n)\) and \(\frac{\phi^n}{\sqrt{5}}\) is \(\psi^n / \sqrt{5}\)
[ \frac{\psi^n}{\sqrt{5}} = \frac{(1\sqrt{5})^n}{2^n\cdot\sqrt{5}} ]
Next step is to prove the equation is actually smaller than \(1/2\). This can be proven by two observations:
 \(\psi\) itself is smaller than \(1/2\). So \(\psi^n\) must be much smaller than \(1/2\).
 \(\sqrt{5}\) is bigger than 2
So dividing something that is clearly smaller than 1/2 by something that is bigger than 2 is going to produce a number that is less than 0.5.
That means the target \(\phi^n / \sqrt{5}\) is apart from the integer \(Fib(n)\) less than 0.5, making \(Fib(n)\) is the closest integer.
1.14
Draw the tree illustrating the process generated by the countchange
procedure of section 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?
(countchange 11)
(cc 11 5)
(+ (cc 11 4)
(cc 39 5))
(+ (+ (cc 11 3)
(cc 14 4)) ;; 0
0)
(+ (+ (cc 11 3)
0)
0)
(+ (+ (+ (cc 11 2)
(cc 1 3)) ;; used a dime(10)
0)
0)
(+ (+ (+ (+ (cc 11 1) ;; change 11 cents merely with 1 cent coins
(cc 6 2)) ;; used a nickle, 6 cents to go with last two types
(+ (cc 1 2) ;; doing the rest 1 cent with two types of coins
(cc 9 3))) ;; 0
0)
0)
(+ (+ (+ (+ (+ (cc 11 0)
(cc 10 1)) ;; used one cent
(+ (cc 6 1) ;; used a nickle, try no more nickles solution
(cc 1 2))) ;; used another nickle, 1 cent left to change
(+ (+ (cc 1 1) ;; doing the rest 1 cent with only one type of coins
(cc 4 2)) ;; 0
0))
0)
0)
(+ (+ (+ (+ (+ (cc 11 0)
(cc 10 1)) ;; used one cent
(+ (cc 6 1) ;; used a nickle, try no more nickles solution
(cc 1 2))) ;; used another nickle, 1 cent left to change
(+ (+ 1 ;; only one way to do 1 cent with 1 cent coins
0) ;; 0
0))
0)
0)
(+ (+ (+ (+ (+ 0
(+ (cc 10 0) ;; 0
(cc 9 1))) ;; used the second cent
(+ (+ (cc 6 0) ;; 0
(cc 5 1)) ;; used a nickle, one cent, try more cents
(+ (cc 1 1) ;; one cent with one cent coins => 1
(cc 4 2)))) ;; used two nickles, trying third, fail
(+ 1
0))
0)
0)
This procedure creates a treerecursive structure, and the branching factor is 2. The deepest branch goes \(O(n)\) steps down, where \(n\) is the money to change. So the process takes \(O(2^n)\) steps to finish and \(O(n)\) space to run.
1.15
The sine of an angle (specified in radians) can be computed by making use of the approximation \(\sin{x}\approx x\) if \(x\) is sufficiently small, and the trigonometric identity:
[ \sin{x} = 3 \sin{\frac{x}{3}}  4\sin^3{\frac{x}{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)))))

How many times is the procedure
p
applied when(sine 12.15)
is evaluated? \(12.5 / 3^x \leq 0.1\) By solving the equation above, we get \(x\geq5\), thusp
is applied 5 times. 
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? The order of growth in number of steps is \(O(\log_3a)\). The order of growth in space is \(O(1)\).
1.16
Design a procedure that evolves an iterative exponentiation process that uses successive squaring and uses a logarithmic number of steps, as does fastexpt
. Hint: use the observation that \((b^{n/2})^2 = (b^2)^{n/2}\), 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^n\) 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.
IDEA: Iteratively, take the exponent inside and replace old base with new ones, until outer exponent is 1. When the outer exponent left is even, further the process by making \(a\Leftarrow a^2\) and thus shrink the exponent by dividing it by 2. When the outer exponent is odd, take 1 away and make \(a\Leftarrow ab\), shrink the exponent by 1.
The above idea is terribly wrong! Because the case for dealing with odd exponent is problematic. The “1” taken out is not on the base of \(b\), but rather on the base of what is inside right now. Can we put another variable that hold what’s outside?
(define (expt b n) ;; expect b and n both to be integers.
(exptiter b n b 1))
;; outer is for keep track of what is outside.
(define (exptiter b cnt a outer)
(cond ((= cnt 0) 1)
((= cnt 1) (* a outer))
((even? cnt) (exptiter b
(/ cnt 2) ;; divide the outside expo by 2
(square a) ;; double the inside
outer)) ;; outside additional remains the same
(else (exptiter b
( cnt 1) ;; minus 1 to make it even
a ;; inside remains the same
(* outer a))))) ;; outer additional get multiplied by the base
(define (even? x)
(= (remainder x 2) 0))
(define (square x) (* x x))
(expt 2 19)
This solution I have here does not follow the hint given in the book. I haven’t figured out how to compute it with an invariant quantity.
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 the integer, and halve
, which divides an (even) integer by 2. Using these, design a multiplication procedure analogous to fastexpt
that uses a logarithmic number of steps.
(define (double x) (+ x x))
(define (halve x) (/ x 2))
(define (even? x)
(= (remainder x 2)
0))
(define (fastmul a b)
(cond ((= b 0) 0)
((even? b) (fastmul (double a)
(halve b)))
(else (+ a
(fastmul a
( b 1))))))
1.18
Using the results of exercises 1.16 and 1.17, devise a procedure that generates an iterative process for multiplying two integers in terms of adding, doubling, and halving and uses a logarithmic number of steps.
(define (double x) (+ x x))
(define (halve x) (/ x 2))
(define (even? x) (= (remainder x 2) 0))
(define (fastmul a b)
(muliter a b 0))
(define (muliter a b add)
(cond ((= b 0) 0)
((= b 1) (+ a add))
((even? b) (muliter (double a)
(halve b) ;; logarithmic
add))
(else (muliter a
( b 1)
(+ add a))))) ;; carry the information along, makes it an iterative process
(fastmul 23 59)
1.19
There is a clever algorithm for computing the Fibonacci numbers in logarithmic numbers of steps. Recall the transformation of the state variables \(a\) and \(b\) in the fibiter
process of section 1.2.2:
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 \(T^n\), the $n$th power or the transformation \(T\), starting with the pair \((1,0)\).
Now consider the \(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:
Show that if we apply such transformation \(T_{pq}\) twice, the effect is the same as using a single transformation \(T_{p^\prime q^\prime}\) of the same form, and compute \(p^\prime\) and \(q^\prime\) 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 fastexpt
procedure. Put this all together to complete the following procedure, which runs in a logarithmic number of steps:
(define (fib n)
(fibiter 1 0 0 1 n))
(define (fibiter a b p q count)
(cond ((= count 0) b)
((even? count)
(fibiter a
b
(+ (square p) (square q))
(+ (square q) (* 2 p q))
(/ count 2)))
(else (fibiter (+ (* b q) (* a q) (* a p))
(+ (* b p) (* a q))
p
q
( count 1)))))
(define (even? x) (= (remainder x 2) 0))
(define (square x) (* x x))
(fib 13)
1.20
The process that a procedure generates is of course independent on the rules used by the interpreter. As an example, consider the iterative gcd
procedure given in text book. Suppose we were to interpret this procedure using normalorder evaluation, as discussed in section 1.1.5. (The normalorderevaluation rule for if
is described in 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 normalorder evaluation of (gcd 206 40)
? In the applicativeorder evaluation?
Review that applicativeorder will evaluate the operands whenever possible, and then apply the operator to the operands. However, normal order will delay any evaluation to a point where something has to be evaluated to proceed. In this exercise, the normal order will only evaluate expressions either when: 1) fully expanded, 2) if
special form’s predicate needs to be evaluated to decide which clause (the consequent or the alternative) to expand next.
For applicativeorder, remainder
gets evaluated 4 times as it shows here:
(gcd 206 40)
;; 
;; v
(gcd 40 (remainder 206 40)) ;; 1 (remainder eval counter)
(gcd 40 6)
;; 
;; v
(gcd 6 (remainder 40 6)) ;; 2
(gcd 6 4)
;; 
;; v
(gcd 4 (remainder 6 4)) ;; 3
(gcd 4 2)
;; 
;; v
(gcd 2 (remainder 4 2)) ;; 4
(gcd 2 0) ;; predicate is true, stop and return 2
For normalorder evaluation:
(gcd 206 40)
(if (= 40 0) ...)
(gcd 40 (remainder 206 40))
(if (= (remainder 206 40) 0) ...) ;; 1
;; 6, not 0
(gcd (remainder 206 40)
(remainder 40
(remainder 206 40)))
(if (= (remainder 40 ;; 1 +2
(remainder 206 40))
0) ...)
;;40%6 = 4, not 0
(gcd (remainder 40
(remainder 206 40)) ;; a
(remainder (remainder 206 40)
(remainder 40
(remainder 206 40)))) ;; b
(if (= (remainder (remainder 206 40) ;; 1 +2 +4
(remainder 40
(remainder 206 40))) ;; b == 0?
0) ...)
;; 2, not zero
(gcd (remainder (remainder 206 40)
(remainder 40
(remainder 206 40))) ;; a
(remainder (remainder 40
(remainder 206 40))
(remainder (remainder 206 40)
(remainder 40
(remainder 206 40))))) ;; b
(if (= (remainder (remainder 40 ;; 1 +2 +4 +7 = 14
(remainder 206 40))
(remainder (remainder 206 40)
(remainder 40
(remainder 206 40)))) ;; 4%2 = 0
0) ...)
(remainder (remainder 206 40)
(remainder 40
(remainder 206 40))) ;; fully expanded, evaluate all rest expressions
;; finally, 14 + 4 = 18
;; So the remainder get evaluated 18 times in total.
;; FORMULA?
Notice that, the changing of numbers of remainder
appearing in the two operands of gcd
obeys the following pattern:
Assume our iteration starts from 0. For simplicity, we consider when applying gcd
, the two operands \(a\) and \(b\) are generated by last iteration in the alternate clause. The 1 that appears in each line is the new remainder
that kicks in in the alternative clause. And the addition between the parentheses means using the operand \(a\) and \(b\) from previous iteration are used as new operands for the new remainder
procedure.
First off, we mainly evaluate remainder
when in the if
predicate. Each time, when we forward one iteration, the number of remainder
in \(b\) from last iteration is evaluated, to determine which clause to expand next. That is: \(0+1+2+4+7\) in this example. Generally, the predicate evaluation will not stop until in the final iteration, where \(b\) equals to 0. When that happens, all the things in \(a\) got evaluated.
To formulate it, lets assume \((R_a^{\langle i \rangle}, R_b^{\langle i \rangle})\) is a pair of integers that record how many times remainder
is invoked in \(a\) and \(b\) during \(i\) th iteration, starting from 0. Say \(k\) is the final iteration where \(b^{\langle k1 \rangle}=0\). Then the total times that remainder
gets evaluated is:
[ T(remainder) = R_b^{\langle 0 \rangle} + R_b^{\langle 1 \rangle} + R_b^{\langle 2 \rangle} + \cdots + R_b^{\langle k1 \rangle} + R_a^{\langle k1 \rangle} ]
Notice that, [ R_b^{\langle i \rangle} = R_a^{\langle i+1 \rangle} = \sum_{j = 0}^i Fib(j) ]
Thus the formula can be rewritten into:
[ T(remainder) = \sum_{j = 0}^0 Fib(j) + \sum_{j = 0}^1 Fib(j) + \sum_{j = 0}^2 Fib(j) + \cdots + 2\sum_{j = 0}^{k2} Fib(j) + \sum_{j = 0}^{k1} Fib(j) ]
1.21
Use the smallestdivisor
procedure to find the smallest divisor of each of the following numbers: 199, 1999, 199999.
Recall that the procedure ~~ is:
(define (smallestdivisor n)
(finddivisor n 2)) ;; find the first divisor starting from 2
(define (finddivisor n testdivisor)
(cond ((> (square testdivisor) n) n) ;; end test
((divides? testdivisor n) testdivisor) ;; modulo test
(else (finddivisor n (+ testdivisor 1)))))
(define (divides? a b)
"b%a == 0?"
(= (remainder b a)
0))
Running this procedure yields:
Number  smallestdivisor  primality 

199  199  Y 
1999  1999  Y 
19999  7  N 
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 example, in microseconds). The following timedprimetest
procedure, when called with an integer \(n\), prints \(n\) and checks to see if \(n\) is prime. If it is, the procedure prints three asterisks followed by the amount of time used in performing the test.
(define (timedprimetest n)
(newline)
(display n)
(startprimetest n (runtime)))
(define (startprimetest n starttime)
(if (prime? n)
(reportprime ( (runtime) starttime))))
(define (reportprime elapsedtime)
(display " *** ")
(display elapsedtime))
Using this procedure, write a procedure searchforprimes
that checks the primality of consecutive odd integers in a specified range. Use your procedure to find the 3 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 \(\Theta(\sqrt{n})\), you should expect that testing or 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?
(define (even? x) (= (remainder x 2) 0))
(define (searchforprimes start end)
"checks the primality of consecutive odd integers in a specified range."
(searchiter start end start))
(define (searchiter start end curr)
(cond ((> curr end) (display "END"))
((even? curr) (searchiter start end (+ curr 1)))
(else (timedprimetest curr)
(searchiter start end (+ curr 2)))))
Smallest 3 Larger than  Prime Numbers  Elapsed Time  

>1,000  1009  0.  
1013  0.  
1019  0.  
>10,000  10007  0.  
10009  0.  
10037  0.  
>100,000  100003  0.  
100019  0.  
100043  0.  
>1,000,000  1000003  1e4  
1000033  0.  
1000037  0.  
>1,000,000,000  1000000007  2e2  
1000000009  2e2  
1000000021  1e2  
>10,000,000,000  10000000019  0.05  
10000000033  0.07  
10000000061  0.05 
My data for required tests doesn’t bear out any signs of \(\Theta(\sqrt{n})\) order of growth. Maybe I should try larger numbers.
After trying numbers larger than 1 billion and numbers larger than 10 billion, the relationship between them starts to reveal itself. Notice that the average running time ratio is:
[ \frac{(0.05 + 0.07 + 0.05) / 3}{(0.02 + 0.02 + 0.01) / 3} = \frac{17}{5} = 3.4 \approx \sqrt{10} ]
1.23
The smallesdivisor
procedure shown at the start of this section does lots of needles 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 testdivisor
should not be 2,3,4,5,6…, but rather 2,3,5,7,9… (Not quite here, notice 9 is also a repeated useless check because we would have get the result from testing 3. Actually we should only try prime numbers here. But seems like the exercise is not aimed at that, so we will not consider this fact yet.) To implement this change, define a procedure next
that returns 3 if its input is 2 and otherwise returns its input plus 2. Modify the smallestdivisor
procedure to use (next testdivisor)
instead of (+ testdivisor 1)
. With timedprimetest
incorporating this modified version of smallestdivisor
, run the test for each of the 12 primes found in exercise 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?
(define (next curr)
"return the next number as new testdivisor."
(if (= curr 2)
3
(+ curr 2)))
(define (smallestdivisor n)
"Find the smallest divisor of n that is bigger than 1."
(finddivisor n 2))
(define (finddivisor n testdivisor)
"Find divisor of n, starting from testdivisor."
(cond ((> (square testdivisor) n) n)
((divides? testdivisor n) testdivisor)
(else (finddivisor n
(next testdivisor)))))
(define (divides? a b)
"Can b be divided by a with remainder 0."
(= (remainder b a)
0))
Because the normal 12 tests required in the textbook doesn’t yield big enough elapse time on my machine, I am going to do the billion tests instead here.
Bigger Than  Number  Original  Modified  

>1,000,000,000  1000000007  2e2  0.02  
1000000009  2e2  0.02  
1000000021  1e2  0.01  
>10,000,000,000  10000000019  0.05  0.05  
10000000033  0.07  0.04  
10000000061  0.05  0.04 
Notice that for most numbers the result remained the same when it comes to time took. Why? Let’s count how many steps we actually do in each finddivisor
iteration in both cases:
Step  Original  Modified 

Comparison  Y  Y 
divides?  Y  Y 
else  (+ testdivisor 1)  Equal to 2 test 
;; forward next iteration  (most cases) (+ curr 2) 
As we can see here, although we have less iterations because we only test odd numbers now, but to generate the next
sequence correctly, we embedded a lots of useless comparisons against 2 to handle the special starting case. Thus make the total steps needed are the same. (This answer may not be correct.)
1.24
Modify the timedprimetest
procedure of exercise 1.22 to use fastprime?
(the Fermat method), and test each of the 12 primes you found in that exercise. Since the Fermat test has \(\Theta(\log n)\) growth, how would you expect the time to test primes near 1,000,000 to compare with the time needed to test primes near 1000? Do your data bear this out? Can you explain any discrepancy you find?
Quick review of the code:
(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 (fermattest n)
(define (tryit a)
(= (expmod a n n) a))
(tryit (+ 1 (random ( n 1)))))
(define (fastprime? n times)
(cond ((= times 0) true) ;; all tests passed, very likely a prime number
((fermattest n) (fastprime? n ( times 1))) ;; pass one test, continue
(else false))) ;; failed one test, certainly not a prime number
Then, embedded this into our timedprimetest
:
(define (timedprimetest n)
(newline)
(display n)
(startprimetest n (runtime)))
(define (startprimetest n starttime)
(if (fastprime? n 1000000) ;; replaced the prime test used here!
(reportprime ( (runtime) starttime))))
(define (reportprime elapsedtime)
(display " *** ")
(display elapsedtime))
Bigger Than  Number  Time(100)  (1000000)  

>1,000,000,000  1000000007  0.01  26.23  
1000000009  0.00  25.61  
1000000021  0.01  26.14  
>10,000,000,000  10000000019  0.01  30.73  
10000000033  0.01  30.05  
10000000061  0.01  31.90 
Right now, the results seems identical, I suppose that is because the number of times we test for each number is too small, replacing 100 with 1000,000.
The ratio: [ \frac{30.73 + 30.05 + 31.90}{26.23 + 26.61 + 26.14} = 1.1769 \approx \frac{\log 10000000000}{\log 1000000000} = 1.1111 ]
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 (expmod2 base exp m)
(remainder (fastexpt base exp) m))
Is she correct? Would this procedure serve as well for our fast prime tester? Explain.
They both yield the same results. However, the version of expmod
is constantly using modulo arithmetic to downsize the numbers related in computation. However, the version proposed by Alyssa, is actually computing the real result for the exponential, which can be slower when the numbers are large enough. It will still give the correct answer but slower.
1.26
Louis Reasoner is having great difficulty doing exercise 1.24. His fastprime?
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.
The recursive call for the even cases are now have branching factor of 2 instead of 1. So instead of a linear recursion with the depth of \(O(\log n)\), now the explicit multiplication version becomes a tree recursion with the depth of \(O(\log n)\). Thus the growth becomes \(\Theta(n)\)
1.27
Demonstrate that the Carmichael numbers listed in footnote 47 really do fool the Fermat test. That is, write a procedure that takes an integer \(n\) and tests whether \(a^n\) is congruent to \(a\) modulo \(n\) for every \(a<n\), and try your procedure on the given Carmichael numbers.
(define (congruenttest n)
"test every number a<n: if a^n is congruent to a modulo n"
(congruentiter n 1))
(define (congruentiter n counter)
"Counter starts from 1 and ends at n"
(cond ((= counter n) true) ;; end test
;; test counter, if passed, continue
((singlefermattest n counter) (congruentiter n (+ counter 1)))
(else false)))
(define (singlefermattest n a)
(= (expmod a n n) a))
Running it with the 6 Carmichael numbers mentioned:
Carmichael Number  Result 

561  t 
1105  t 
1729  t 
2465  t 
2821  t 
6601  t 
We can see that all these numbers can fool Fermat test.
(The following section is not required by the exercise. It is out of my own curiosity.) Next, I want to find the next Carmichael number not mentioned in the book using the above procedure:
(define (findcarmichael start end)
"Find all carmichael numbers between start and end."
(findcarmichaeliter start end start))
(define (findcarmichaeliter start end test)
(cond ((= test end) (display "==END=="))
((and (not (prime? test)) (congruenttest test))
(display test)
(newline)
(findcarmichaeliter start end (+ test 1)))
(else (findcarmichaeliter start end (+ test 1)))))
It is a procedure that looks for Carmichael numbers within an range \([start, end)\).
By running the above procedure, I found the following Carmichael Numbers: 8911, 10585, 15841.
Comparing them with the Carmichael number list online confirms the correctness of the findcarmichael
procedure.
1.28
One variant of Fermat test that cannot be fooled is called the MillerRabin test. This starts from an alternate form of Fermat’s Little Theorem, which states that if \(n\) is prime number and \(a\) is any positive integer less than \(n\), then \(a^{n1}\) is congruent to 1 modulo \(n\). To test the primality of a number \(n\) by the MillerRabin test, we pick a random number \(a<n\) and raise \(a\) to the \((n1)\) power modulo \(n\) using the expmod
procedure. However, whenever we perform the squaring step in expmod
, we check to see if we have discovered a “nontrivial square root of 1 modulo n,” that is, a number not equal to 1 or \(n1\) whose square is equal to 1 modulo \(n\). It is possible to prove that if such a nontrivial square root of 1 exists, then \(n\) is not prime. It is also possible to prove that if \(n\) is an odd number that is not prime, then, for at least half the numbers \(a<n\), computing \(a^{n1}\) in this way will reveal a nontrivial square root of 1 modulo \(n\). (This is why the MillerRabin test cannot be fooled.) Modify the expmod
procedure to signal if it discovers a nontrivial square root of 1, and use this to implement the MillerRabin test with a procedure analogous to fermattest
. Check your procedure by testing various known primes and nonprimes. Hint: One convenient way to make expmod
signal it to have it return 0.
(define (expmodm1 base exp m)
(cond ((= exp 0) 1)
((even? exp)
(remainder (square (testnontrivialm1 (expmodm1 base (/ exp 2) m) m))
m))
(else
(remainder (* base (expmodm1 base ( exp 1) m))
m))))
(define (testnontrivialm1 a n)
"test if: a not equal to 1 or n1 but a^2 equals to 1 modulo n"
(cond ((and (> a 1)
(< a ( n 1))
(= (remainder (square a) n) 1)) ;; if it is nontrivial case
0) ;; return zero
(else a))) ;; else, return its original value
(define (millerrabin n)
"test if n is prime using miller rabin method"
(define (tryit a)
(= (expmodm1 a ( n 1) n) 1))
(tryit (+ 1 (random ( n 1)))))
(define (fastprime? n times)
(cond ((= times 0) true)
((millerrabin n) (fastprime? n ( times 1)))
(else false)))
I tested this procedure with common numbers and large prime numbers. Next I am going to write a procedure that tests and gives all prime numbers within a range:
(define (printprimes start end)
(printprimesiter start end start))
(define (printprimesiter start end curr)
(cond ((> curr end) (display "END"))
((fastprime? curr 20) ;; test 20 random numbers
(newline)
(display curr)
(printprimesiter start end (+ curr 1)))
(else (printprimesiter start end (+ curr 1)))))
By printing a lot of prime numbers and comparing them with prime?
procedure’s outputs, we can verify that this procedure does what we intended.
1.29
Simpson’s Rule is a more accurate method of numerical integration than the method illustrated above. Using Simpson’s rule, the integral of a function \(f\) between \(a\) and \(b\) is approximated as [ \frac{h}{3}[y_0 + 4y_1 + 2y_2 + 4y_3 + 2y_4 + \cdots + 2y_{n2} + 4y_{n1} + y_n] ] where \(h=(ba)/n\), for some even integer \(n\), and \(y_k=f(a+kh)\). (Increasing \(n\) increases the accuracy of the approximation.) Define a procedure that takes as arguments \(f\), \(a\), \(b\), and \(n\) and returns the value of the integral, computed using Simpson’s Rule. Use your procedure to integrate cube
between 0 and 1 (with \(n=100\) and \(n=1000\), and compare the results to those of the integral
procedure shown above.
(define (simpsonintegral f a b n)
(define h (/ ( b a) n))
(define (coef x)
(let ((diff (/ ( x a) h))) ;; compute coefficients based on the x difference.
(cond ((or (= diff 0) (= diff n)) 1.0)
((even? diff) 2.0)
(else 4.0))))
(define (simpsonterm x) (* (coef x)
(f x))) ;; how to deal with the coefficients? 1, 4, 2, 4, 2, ..., 2, 4, 1
(define (simpsonnext x) (+ x h))
(* (sum simpsonterm a simpsonnext b)
(/ h 3.0)))
Running this procedure with different \(n\) yields:
\(n\) value  Result 
100  .24999999999999992 
1000  .2500000000000002 
We see that it is more accurate than the results in previous section.
1.30
The sum
procedure in the textbook generates a linear recursion. The procedure can be rewritten so that the sum is performed iteratively. Show how to do this by filling in the missing expressions in the following definition:
(define (sum term a next b)
(define (iter a result)
(if (> a b)
result
(iter (next a)
(+ result (term a)))))
(iter a 0))
1.31
 The
sum
procedure is only the simplest of a vast number of similar abstractions that can be captured as
higherorder functions. 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 \(\pi\) using the formula: [ \frac{\pi}{4} = \frac{2\cdot 4\cdot 4 \cdot 6 \cdot 6 \cdot 8 \cdots}{3\cdot 3 \cdot 5 \cdot 5 \cdot 7 \cdot 7 \cdots} ]
(define (product term a next b)
(if (> a b)
1
(* (term a)
(product term (next a) next b))))
(define (piproduct start end)
(define (piterm x)
(/ (* ( x 1.0) (+ x 1.0))
(square x)))
(define (pinext x)
(+ x 2))
(product piterm start pinext end))
(define (piestimate accuracy)
"the larger the accuracy, the more accurate the estimation is."
(* 4
(piproduct 3 (+ 3 (* 2 accuracy)))))
Running this procedure yields:
Accuracy  Estimation 

20  3.1774930 
200  3.1454832 
2000  3.1319849 
 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.
(define (product term a next b)
(define (productiter a result)
(if (> a b)
result
(productiter (next a)
(* result
(term a)))))
(productiter a 1.0))
1.32
 Show that
sum
andproduct
are both special cases of a still more general notion calledaccumulate
that combines a collection of terms, using some general accumulation function:(accumulate combiner nullvalue term a next b)
It takes as arguments the same term and range specifications assum
andproduct
, together with acombiner
procedure (of two arguments) that specifies how the current term is to be combined with the accumulation of the preceding terms and anullvalue
that specifies what base value to use when the terms run out. Writeaccumulate
and show how sum and product can both be defined as simple calls toaccumulate
.  Write another version of
accumulate
, that will generate an iterative or a recursive process.
;; recursive process version
(define (accumulate combiner nullvalue term a next b)
(if (> a b)
nullvalue
(combiner (term a)
(accumulate combiner nullvalue term (next a) next b))))
;; iterative process version
(define (accumulate combiner nullvalue term a next b)
(define (accumulateiter a result)
(if (> a b)
result
(accumulateiter (next a)
(combiner (term a)
result))))
(accumulateiter a nullvalue))
(define (sum term a next b)
(accumulate + 0.0 term a next b))
(define (product term a next b)
(accumulate * 1.0 term a next b))
1.33
You can obtain an even more general version of accumulate
by introducing the notion of 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 filteredaccumulate
abstraction takes the same arguments as accumulate, together with an additional predicate of one argument that specifies the filter. Write filteredaccumulate
as a procedure. Show how to express the following using it:
 the sum of the squares of the prime numbers in the interval \(a\) to \(b\) (assuming that you have
prime?
) predicate already written.  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\)).
;; recursive process
(define (filteredaccumulate combiner ;; 2 args, combine values
filter ;; 1 arg, on terms to be combined
nullvalue
term
a
next
b)
(if (> a b)
nullvalue
(combiner (if (filter a)
(term a)
nullvalue);; if it doesn't, replace with nullvalue
(filteredaccumulate combiner
filter
nullvalue
term
(next a)
next
b))))
;; iterative process
(define (filteredaccumulate combiner filter nullvalue term a next b)
(define (filteredaccumiter a result)
(if (> a b)
result
(filteredaccumiter (next a)
(combiner (if (filter a)
(term a)
nullvalue)
result))))
(filteredaccumiter a nullvalue))
(define (smallestdivisor n)
"Find the smallest divisor of n that is bigger than 1."
(finddivisor n 2))
(define (finddivisor n testdivisor)
"Find divisor of n, starting from testdivisor."
(cond ((> (square testdivisor) n) n)
((divides? testdivisor n) testdivisor)
(else (finddivisor n
(+ testdivisor 1)))))
(define (divides? a b)
"Can b be divided by a with remainder 0."
(= (remainder b a)
0))
(define (prime? n)
(= (smallestdivisor n)
n))
(define (squaresumprimes a b)
(filteredaccumulate + prime? 0 square a 1+ b))
;; running (squaresumprimes 2 15) yields 377
;; 377 = (+ 4 9 25 49 121 169)
(define (gcd a b)
(if (= b 0)
a
(gcd b (remainder a b))))
(define (identity x) x)
;; product of all the positive integers less than n that
;; are relatively prime to n
(define (productrelativeprime n)
(define (relativeprime? x)
(= (gcd x n) 1))
(filteredaccumulate * relativeprime? 1 identity 1 1+ ( n 1)))
;; running (productrelativeprime 15) yields 896896
;; 896996 = (* 1 2 4 7 8 11 13 14)
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.
This will be the evaluation process:
(f f)
;;
;;v
(f 2)
;;
;;v
(2 2)
Then, because 2 is not an applicable procedure, the interpreter is going to yield an error.
1.35
Show that the golden ratio \(\phi\) (section 1.2.2) is a fixed point of the transformation \(x \mapsto 1 + 1/x\), and use this fact to compute \(\phi\) by means of the fixedpoint
procedure.
By definition, a fixed point of a function \(f\) is an \(x\) such that \(f(x) = x\). So, let \(x = \phi = \frac{1+\sqrt{5}}{2}\)
Thus, \(\phi\) is a fixed point of transformation \(x \mapsto 1+1/x\).
(define goldenratio
(fixedpoint (lambda (x) (+ 1
(/ 1.0 x)))
1.0))
Running the above procedure yields 1.61800327868852458.
1.36
Modify the fixedpoint
procedure so that it prints the sequence of approximations it generates, using the newline
and display
primitives shown in exercise 1.22. Then find a solution to \(x^x = 1000\) by finding a fixed point of \(x \mapsto \log(1000) / \log(x)\). (Use Scheme’s primitive log
procedure, which computes natural logarithms.) Compare the number of steps this takes with and without average damping. (Note that you cannot start fixedpoint
with a guess of 1, as this could cause division by \(\log(1) = 0\).)
(define tolerance 0.000001)
(define (fixedpoint f firstguess)
(define (closeenough? v1 v2)
(< (abs ( v1 v2)) tolerance))
(define (try guess step)
(newline)
(display step)
(display ": ")
(display guess)
(let ((next (f guess)))
(if (closeenough? guess next)
next
(try next (1+ step)))))
(try firstguess 0))
Then, finding a fixed point of \(x^x = 1000\):
;; without average damping
(define (xexpo n)
(fixedpoint (lambda (x) (/ (log n)
(log x)))
2.0))
(define (average x y) (/ (+ x y) 2))
;; with average damping
(define (xexpodamped n)
(fixedpoint (lambda (x) (average x
(/ (log n)
(log x))))
2.0))
Results:
 Running
(xexpo 1000)
, it takes 40 (starts from 0) steps to converge:
0: 2.
1: 9.965784284662087
2: 3.004472209841214
3: 6.279195757507157
4: 3.759850702401539
5: 5.215843784925895
6: 4.182207192401397
7: 4.8277650983445906
8: 4.387593384662677
9: 4.671250085763899
10: 4.481403616895052
11: 4.6053657460929
12: 4.5230849678718865
13: 4.577114682047341
14: 4.541382480151454
15: 4.564903245230833
16: 4.549372679303342
17: 4.559606491913287
18: 4.552853875788271
19: 4.557305529748263
20: 4.554369064436181
21: 4.556305311532999
22: 4.555028263573554
23: 4.555870396702851
24: 4.555315001192079
25: 4.5556812635433275
26: 4.555439715736846
27: 4.555599009998291
28: 4.555493957531389
29: 4.555563237292884
30: 4.555517548417651
31: 4.555547679306398
32: 4.555527808516254
33: 4.555540912917957
34: 4.555532270803653
35: 4.555537970114198
36: 4.555534211524127
37: 4.555536690243655
38: 4.555535055574168
39: 4.5555361336081
;Value: 4.555535422664798
 Running
(xexpodamped 1000)
, it takes 11 steps to converge:
0: 2.
1: 5.9828921423310435
2: 4.922168721308343
3: 4.628224318195455
4: 4.568346513136242
5: 4.5577305909237005
6: 4.555909809045131
7: 4.555599411610624
8: 4.5555465521473675
9: 4.555537551999825
10: 4.555536019631145
;Value: 4.555535758730802
We can see that with damping, the procedure converges way faster than the version without.
1.37
 An infinite continued fraction is an expression of the form:
[ f = \frac{N_1}{D_1 + \frac{N_2}{D_2 + \frac{N_3}{D_3 + \cdots}}} ]
As an example, one can show that the infinite continued fraction expansion with the \(N_i\) and \(D_i\) all equal to 1 products \(1/\phi\), where \(\phi\) is the golden ratio (described in section 1.2.2). One way to approximate an infinite continued fraction is to truncate the expansion after a given number of terms. Such as a truncation–a socalled kterm finite continued fraction–has the form:
[ \frac{N_1}{D_1 + \frac{N_2}{\ddots + \frac{N_k}{D_k}}} ]
Suppose that \(n\) and \(d\) are procedures of one argument (the term index \(i\)) that return the \(N_i\) and \(D_i\) of the terms of the continued fraction. Define a procedure contfrac
such that evaluating (contfrac n d k)
computes the value of the $k$term finite continued fraction. Check your procedure by approximating \(1/\phi\) using
(contfrac (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?
 If your
contfrac
procedure generates a recursive process, write one that generates an iterative one. If it generates an iterative process, write one that generates a recursive process.
;; recursive
(define (contfrac n d k)
(define (singlefrac i)
(if (= i k) ;; last term
(/ (n i) (d i))
(/ (n i) ;; else
(+ (d i)
(singlefrac (1+ i))))))
(singlefrac 1))
;; iterative
(define (contfrac n d k)
(define (contfraciter res i) ;; cnt starts from k, res starts from zero
(cond ((= i 0) res) ;; end when cnt is zero
((= i k) (contfraciter (+ res
(/ (n i) (d i)))
(1+ i))) ;; first term
(else (contfraciter (/ (n i) ;; replace the result with its new value
(+ (d i)
res))
(1+ i)))))
(contfraciter 0.0 k))
Then test:
(define phi (/ (+ 1 (sqrt 5)) 2))
(contfrac (lambda (i) 1.0)
(lambda (i) 1.0)
k) ;; using different k
So, \(1/\phi\) is 0.61803398874. To the 4 decimal place is 0.6180. Running the contfrac
procedure with \(k=10\) yields .6179775280898876. While using \(k=11\) yields .6180555555555556. So the \(k\) should be at least 11 to make it accurate enough.
1.38
In 1737, the Swiss mathematician Leonhard Euler published a memoir De Fractionibus Continuis, which included a continued fraction expansion for \(e2\), where \(e\) is the base of the natural logarithms. In this fraction, the \(N_i\) are all 1, and the \(D_i\) are successively 1, 2, 1, 1, 4, 1, 1, 6, 1, 1, 8,… Write a program that uses your contfrac
procedure from exercise 1.37 to approximate \(e\), based on Euler’s expansion.
;; 1, 2, 1, 1, 4, 1, 1, 6, 1, 1, 8
;; when (remainder i 3) is 2, than the D_i is (i+1)/3 *2
;; else situations, D_i is 1
(define (eD i)
(if (= (remainder i 3) 2)
(* (/ (+ i 1)
3)
2)
1))
(define (eapprox k) ;; kterm finite, the bigger k is, the more accurate the estimate
(+ (contfrac (lambda (i) 1.0)
eD
k)
2))
Running (eapprox 10)
yields 2.7182817182817183. Running (eapprox 15)
yields 2.718281828470584.
1.39
A continued fraction representation of the tangent function was published in 1770 by the German mathematician J.H. Lambert:
[ \tan x = \frac{x}{1  \frac{x^2}{3  \frac{x^2}{5  \ddots}}} ]
where \(x\) is radians. Define a procedure (tancf 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 exercise 1.37.
One observation is that, we should take the minus sign into \(N_i\) to make it compatible with contfrac
:
And for \(D_i\):
[ D_i = 2i  1 ]
(define (tancf x k)
(contfrac (lambda (i)
(cond ((= i 1) x)
(else (* x x 1.0))))
(lambda (i) ( (* 2 i)
1.0))
k))
Running this procedure with \(k=100\):
Call  Result  Accurate? 
(tancf 3.0 10) 
.1425465438397583  Y 
(tancf 30 10) 
3.468225849832513  N 
(tancf 30 100) 
6.405331196646245  Y 
(tancf 70 100) 
1.2219599181369425  Y 
We notice that, the larger the radian is, the larger \(k\) required to make our approximation accurate.
1.40
Define a procedure cubic
that can be used together with the newtonsmethod
procedure in expressions of the form
(newtonsmethod (cubic a b c) 1)
to approximate zeros of the cubic \(x^3 + ax^2 + bx + c\).
(define (cubic a b c)
(lambda (x)
(+ (* x x x)
(* a x x)
(* b x)
c)))
(define (solvecubic a b c guess)
(newtonsmethod (cubic a b c) guess))
Running results:
Call  Running Results  Actual Answer 
(solvecubic 6 11 6 1.0) 
.9999999999359228  1 
(solvecubic 6 11 6 4) 
2.9999999999839293  3 
(solvecubic 6 11 6 2.1) 
2.000000000000003  2 
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 example, 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)
(define (inc x) (1+ x))
(define (double f)
(lambda (x)
(f (f x))))
Using substitution:
(((double
(double double))
inc)
5)
(((double
(lambda (x) (double (double x))))
inc)
5)
(((lambda (x)
(double (double (double (double x)))))
inc)
5)
((double (double (double (double inc))))
5)
((double (double (double (lambda (x) (inc (inc x)))))))
;; ....
;; finally it is equivalent to +16
Thus the result should be 16+5 = 21.
A easier way to deduct this: double
is nested, and finally applied to inc
.
[ (2^2)^2 \times (+1) = 16 ]
Running it verifies this fact. The answer is 16+5 = 21.
1.42
Let \(f\) and \(g\) be two oneargument functions. The composition \(f\) after \(g\) is defined to be the function \(x \mapsto f(g(x))\). Define a procedure compose
that implements composition. For example, if inc
is a procedure that adds 1 to its argument,
((compose square inc) 6);; should yield 49
(define (compose f g)
(lambda (x)
(f (g x))))
1.43
If \(f\) is a numerical function and \(n\) is a positive integer, then we can form the \(n\) th repeated application of \(f\), which is defined to be the function whose value at \(x\) is
[ f(f(\cdots(f(x))\cdots)) ]
For example, if \(f\) is the function \(x\mapsto x+1\), then the \(n\) th repeated application of \(f\) is the function \(x \mapsto x+n\). If \(f\) is the operation of squaring a number, then the \(n\) th repeated application of \(f\) is the function that raises its argument to the \(2^n\) th power. Write a procedure that takes as inputs a procedure that computes \(f\) and a positive number \(n\) and returns the procedure that computes the \(n\) th repeated application of \(f\). Your procedure should be able to be used as follows:
((repeated square 2) 5) ;; should yield 625
(define (repeated f n)
(define (repeatiter g cnt)
(cond ((> cnt n) g)
(else (repeatiter (lambda (x) (f (g x)))
(1+ cnt)))))
(repeatiter f 2))
It is a iterative version here. Next I will try to write a recursive one:
(define (repeated f n)
(cond ((= n 1) f)
(else (compose f
(repeat f ( n 1))))))
;; or, if we don't have compose at hand
(define (repeated f n)
(cond ((= n 1) f)
(else (lambda (x)
(f ((repeat f ( n 1)) x))))))
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 smoothed version of \(f\) is the function whose value at a point \(x\) is the average of \(f(xdx)\), \(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 obtained 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.
(define dx 0.00001)
(define (smooth f)
(lambda (x)
(/ (+ (f ( x dx))
(f x)
(f (+ x dx)))
3.0)))
(define (nfoldsmooth f n)
(lambda (x)
(((repeated smooth n) f) x)))
Running it using cubic
from exercise 1.40 as an example:
((nfoldsmooth (cubic 1 1 1) 3) 10)
Yields 1111.0000000062.
1.45
We saw in section 1.3.3 that attempting to compute square roots by naively finding a fixed point of \(y \mapsto x/y\) does not converge, and that this can be fixed by average damping. The same method works for finding cube roots as fixed points of the averagedamped \(y \mapsto x/y^2\). Unfortunately, the process does not work for fourth roots–a single average damp is not enough to make a fixedpoint search for \(y \mapsto x/y^3\) converge. On the other hand, if we average damp twice (i.e., use the average damp of the average damp of \(y\mapsto x/y^3\)) the fixedpoint search does converge.
Do some experiments to determine how many average damps are required to compute $n$th roots as a fixedpoint search based upon repeated average damping of \(y \mapsto x/y^{n1}\). Use this to implement a simple procedure for computing $n$th roots using fixedpoint
, averagedamp
, and the repeated
procedure of exercise 1.43. Assume that any arithmetic operations you need are available as primitives.
(define (nthroot x n)
(fixedpoint ((repeated averagedamp
(nthdampneeded n)) ;; how many damping needed
(nthrootmapsto n x)) ;; apply the repeated damping to the original mapsto function.
1.0))
(define (logbase x b)
(/ (log x) (log b)))
(define (nthdampneeded n)
"Returns the exact number of times averagedamp needed for the fixed point to converge."
(floor (logbase n 2)))
(define (nthrootmapsto n x)
"Gives the mapsto function for solving nth root"
(lambda (y)
(/ x (fastexpt y ( n 1)))))
(define (fastexpt b n)
(cond ((= n 0) 1)
((even? n) (square (fastexpt b (/ n 2))))
(else (* b
(fastexpt b ( n 1))))))
(define (even? n)
(= (remainder n 2) 0))
;; some experiments I ran:
(fixedpoint ((repeated averagedamp 1) (nthrootmapsto 3 133)) 1.0)
(fixedpoint ((repeated averagedamp 2) (nthrootmapsto 4 133)) 1.0)
(fixedpoint ((repeated averagedamp 2) (nthrootmapsto 7 133)) 1.0)
(fixedpoint ((repeated averagedamp 3) (nthrootmapsto 8 133)) 1.0)
(fixedpoint ((repeated averagedamp 3) (nthrootmapsto 15 133)) 1.0)
(fixedpoint ((repeated averagedamp 4) (nthrootmapsto 16 133)) 1.0)
The pattern I found from running different experiments is that: \(D = \lfloor \log n \rfloor\), where \(D\) is the required times of repeated damping needed to compute the root for $n$th roots.
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 iterativeimprove
that takes two procedures as arguments: a method for telling whether a guess is good enough and a method for improving a guess. iterativeimprove
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 section 1.1.7 and fixedpoint
procedure of section 1.3.3 in terms of iterativeimprove
.
(define (iterativeimprove goodenough? improve)
(lambda (firstguess)
(define (try guess)
(let ((next (improve guess)))
(if (goodenough? guess next)
guess
(try next))))
(try firstguess)))
(define (average x y) (/ (+ x y) 2.0))
(define (closeenough? x y) (< (abs ( x y)) 0.00001))
(define (sqrt x)
((iterativeimprove closeenough?
(lambda (y) (average y (/ x y))))
x))
(define (fixedpoint f firstguess)
((iterativeimprove closeenough?
f)
firstguess))
Leave a Comment