SICP Exercise 1.19

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 Fib(n + 1) and Fib(n). In other words, the Fibonacci numbers are produced by applying Tn, the nth 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 Tpq, where Tpq transforms the pair (a,b) according to a  bq + aq + ap and b  bp + aq. Show that if we apply such a transformation Tpq twice, the effect is the same as using a single transformation Tp'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 Tn 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:41



(define (fib n)
  (fib-iter 1 0 0 1 n))
(define (fib-iter a b p q count)
  (cond ((= count 0) b)
        ((even? count)
         (fib-iter a
                   b
                   <??>      ; compute p'
                   <??>      ; compute q'
                   (/ count 2)))
        (else (fib-iter (+ (* b q) (* a q) (* a p))
                        (+ (* b p) (* a q))
                        p
                        q
                        (- count 1)))))

 SOLUTION

 The code is here.


Comments

Post a Comment

Popular posts from this blog

SICP Exercise 4.9 do for while until

Exercise 4.9.    Many languages support a variety of iteration constructs, such as  do ,  for ,  while , and  until . In Scheme, iterative processes can be expressed in terms of ordinary procedure calls, so special iteration constructs provide no essential gain in computational power. On the other hand, such constructs are often convenient. Design some iteration constructs, give examples of their use, and show how to implement them as derived expressions. SOLUTION The code and tests are  here . I have implemented the following expressions: do-while do-until for while The 'do-while' construct can be as follows: (do   (<one or more statements>)   while (condition) ) Use the while block construct to convert it as follows: (begin   <statements>   (while (condition)   <statements>   ) ) The 'do-until' construct can be as follows: (do   (<one or more statements>) ...
Read more

SICP Exercise 3.56 merge streams

Exercise 3.56.   A famous problem, first raised by  R. Hamming, is to enumerate, in ascending order with no repetitions, all positive integers with no prime factors other than 2, 3, or 5. One obvious way to do this is to simply test each integer in turn to see whether it has any factors other than 2, 3, and 5. But this is very inefficient, since, as the integers get larger, fewer and fewer of them fit the requirement. As an alternative, let us call the required stream of numbers  S  and notice the following facts about it. S  begins with 1. The elements of  (scale-stream S 2)  are also elements of  S . The same is true for  (scale-stream S 3)  and  (scale-stream 5 S) . These are all the elements of  S . Now all we have to do is combine elements from these sources. For this we define a procedure  merge  that combines two ordered streams into one ordered result stream, eliminating repetitions: (define...
Read more

SICP Exercise 4.14 map as compound vs. primitive type

Exercise 4.14.   Eva Lu Ator and Louis Reasoner are each experimenting with the metacircular evaluator. Eva types in the definition of  map , and runs some test programs that use it. They work fine. Louis, in contrast, has installed the system version of  map  as a primitive for the metacircular evaluator. When he tries it, things go terribly wrong. Explain why Louis's  map  fails even though Eva's works. EXPLANATION & SOLUTION Part a of this problem: I implement Eva's way of explicitly typing in  the definition of 'map' into the metacircular evaluator's input prompt. I also type in the  definition of an 'inc' procedure to increment its (numerical) input. And also make use  of Racket's primitive procedure 'abs'. 'inc' and 'abs' are the procedure arguments to  'map' in different tests. As can be seen from the test results, everything works as expected.  Note that in this program, 'map' and 'inc' are...
Read more