From Structure and Implementation of Computer Programs, second edition:

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.

(I suppose "apply the transformation twice" must really mean something to do with "squaring the transformation," of which I can find something online saying "T2(x)=T(T(x))", which doesn’t really help here, as T_(pq) only transforms the pair (a,b) and I’m supposed to be figuring out how to calculate p' and q' from p and q... let me know if I’m barking up the wrong tree, here.)

Anyway, I suppose I must be missing some tools in my mental toolbox for understanding any of this, so please let me know what they are. Please DO NOT give me the answer to the exercise, or directly describe how to calculate p' and q'; I’m trying to get through this book legit. I just need to know what it is I’m supposed to understand and don’t. Thank you.