SICP

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

Exercise 1.32.    a. 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 . b. 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. SOLUTION The code and tests are here .

Exercise 1.31.     a.  The  sum  procedure is only the simplest of a vast number of similar abstractions that can be captured as higher-order procedures. 51  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 52 b.  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. SOLUTION The code and tests are here .

Exercise 1.30.    The  sum  procedure above 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 < ?? >         < ?? >         (iter < ?? > < ?? >)))   (iter < ?? > < ?? >)) SOLUTION The code and tests are here .

Exercise 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 where  h  = ( b  -  a )/ n , for some even integer  n , and  y k  =  f ( a  +  k h ). (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. SOLUTION The code and tests are here .

Exercise 1.28.    One variant of the Fermat test that cannot be fooled is called the  Miller-Rabin test  (Miller 1976; Rabin 1980). This starts from  an alternate form of Fermat's Little Theorem, which states that if  n  is a prime number and  a  is any positive integer less than  n , then  a  raised to the ( n  - 1)st power is congruent to 1 modulo  n . To test the primality of a number  n  by the Miller-Rabin test, we pick a random number  a < n  and raise  a  to the ( n  - 1)st 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  n  - 1 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 , co

Exercise 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. SOLUTION The code and tests are here . Observations ============ The above program demonstrates that the Carmichael numbers 561, 1105....to 6601 fool the Fermat  test. These are all composite numbers that pass the Fermat test.

Exercise 1.26.   Louis Reasoner is having great difficulty doing 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  ( log   n ) process into a  ( n ) process.'' Explain. SOLUTION

Exercise 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. SOLUTION

Exercise 1.24.   Modify the  timed-prime-test  procedure of exercise  1.22  to use  fast-prime?  (the Fermat method), and test each of the 12 primes you found in that exercise. Since the Fermat test has  ( 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? SOLUTION Fermat Method The code and tests are here . Observations ============ the O(log n) growth can be seen. For every 10 fold increase of the number, the time taken is increasing by the same roughly constant amount. There are some discrepancies (see Excel sheet). These are probably due to other stuff happening on the computer

Exercise 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 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

Exercise 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  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 (runtime))) (define (start-prime-test n start-time)   (if (prime? n)       (report-prime (- (runtime) start-time)))) (define (report-prime elapsed-time)   (display " *** ")   (display elapsed-time)) 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

Exercise 1.21.   Use the  smallest-divisor  procedure to find the smallest divisor of each of the following numbers: 199, 1999, 19999. SOLUTION The code and tests are here .

Exercise 1.20.    The process that a procedure generates is of course dependent on the rules used by the interpreter. As an example, consider the iterative  gcd  procedure given above. Suppose we were to interpret this procedure using normal-order evaluation, as discussed in section  1.1.5 . (The normal-order-evaluation 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 normal-order evaluation of  (gcd 206 40) ? In the applicative-order evaluation? SOLUTION

Exercise 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 section  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  F i b ( n  + 1) and  F i b ( 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 p q , where  T p q  transforms the pair ( a , b ) according to  a     b q  +  a q  +  a p  and  b     b p  +  a q . Show that if we apply such a transformation  T p q  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

Exercise 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. 40 SOLUTION The code is here .

Exercise 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. SOLUTION The code is here .

Exercise 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 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  a   b 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.) SOLUTION The code is here .

Exercise 1.15.    The sine of an angle (specified in radians) can be computed by making use of the approximation  sin   x     x  if  x  is sufficiently small, and the trigonometric identity 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? SOLUTION

Exercise 1.14.   Draw the tree illustrating the process generated by the  count-change  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? SOLUTION

Exercise 1.13.   Prove that  F i b ( n ) is the closest integer to  n / 5, where   = (1 +  5)/2. Hint: Let  = (1 -  5)/2. Use induction and the definition of the Fibonacci numbers (see section  1.2.2 ) to prove that  F i b ( n ) = ( n  -  n )/ 5. SOLUTION

Exercise 1.12.    The following pattern of numbers is called  Pascal's triangle . 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. 35  Write a procedure that computes elements of Pascal's triangle by means of a recursive process. SOLUTION The code is here . The tests are here .

Exercise 1.11.   A function  f  is defined by the rule that  f ( n ) =  n  if  n <3 and  f ( n ) =  f ( n  - 1) + 2 f ( n  - 2) + 3 f ( 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. Part 1: Recursive The code is here . Part 2: Iterative The code is here . Part 3: Tests The tests and results are here .

Exercise 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 example,  (k n)  computes 5 n 2 . SOLUTION