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 T^n, 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 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:(5)

(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)))))

(5) This exercise was suggested to us by Joe Stoy, based on an example in Kaldewaij 1990.

I don’t know where to start with how confused I am. T is a "special case" of a transformation that is totally different and involves two extra variables? (Well, it says it’s a "special case" of a "family of transformations," and I’m guessing those are both mathematical terms of art of which I am unaware and for which I cannot find any definitions.) Also, apparently if you use p and q to transform a and b once, according to a ← bq + aq + ap and b ← bp + aq, a becomes the next number in the Fibonacci sequence (while b holds a’s previous value), just like in the original fib-iter process, but if you apply the transformation twice, you can halve the number of steps it takes to get the desired value in the Fibonacci sequence?! Given all this, I have absolutely no idea what p' and q' are supposed to be; I mean, judging from the text and the code, I have to assume that p' and q' are the values of p and q that, when used to transform a and b, would end up getting them halfway down the road to b becoming the desired value in the Fibonacci sequence (and a becoming the value after that), but not only do I have no idea how to start figuring out the method for computing p' and q', I also can’t understand how the transformation a ← bq + aq + ap and b ← bp + aq is supposed to be equivalent to a ← a + b and b ← a when you apply it once but something totally different when you apply it twice.

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 Tⁿ, 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 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:(5)

(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)))))

(5) This exercise was suggested to us by Joe Stoy, based on an example in Kaldewaij 1990.

I don’t know where to start with how confused I am. T is a "special case" of a transformation that is totally different and involves two extra variables? (Well, it says it’s a "special case" of a "family of transformations," and I’m guessing those are both mathematical terms of art of which I am unaware and for which I cannot find any definitions.)

Also, apparently if you use p and q to transform a and b once, according to a ← bq + aq + ap and b ← bp + aq, a becomes the next number in the Fibonacci sequence (while b holds a’s previous value), just like in the original fib-iter process, but if you apply the transformation twice, you can halve the number of steps it takes to get the desired value in the Fibonacci sequence?!

Given all this, I have absolutely no idea what p' and q' are supposed to be; I mean, judging from the text and the code, I have to assume that p' and q' are the values of p and q that, when used to transform a and b, would end up getting them halfway down the road to b becoming the desired value in the Fibonacci sequence (and a becoming the value after that), but not only do I have no idea how to start figuring out the method for computing p' and q', I also can’t understand how the transformation a ← bq + aq + ap and b ← bp + aq is supposed to be equivalent to a ← a + b and b ← a when you apply it once but something totally different when you apply it twice.