Hello! I'm so glad this Math Forum exists. Hopefully the people here can help me out. First off, I'm not sure if I'm posting in the right section. I didn't see anything specifically on algorithms and computing but I saw someone else post a Fibonacci question here.

Also, even though I am referencing an exercise of a book (SICP), this is not for any type of school assignment, I am studying this stuff on my own.

MIT offers the book free, and the section this problem is in is here:

Structure and Interpretation of Computer Programs

Earlier in the text it was demonstrated that the recursively defined Fibonacci sequence can be computed with a "linear iterative" process (so only O(n) steps and O(1) space is required to complete the process). The exercise (1.19) is to complete an algorithm that computes Fib(n) in O(Log(n)) time. This is achieved by essentially "squaring" the Fibonacci function. Here is the text of the exercise:

Quote:

Recall the transformation of the state variablesaandbin the fib-iter process of section 1.2.2:ahttp://mitpress.mit.edu/sicp/full-te...k-Z-G-D-14.gifa+bandbhttp://mitpress.mit.edu/sicp/full-te...k-Z-G-D-14.gifa. Call this transformationT, and observe that applyingTover and over againntimes, starting with 1 and 0, produces the pairFib(n+ 1) andFib(n). In other words, the Fibonacci numbers are produced by applyingTn, thenth power of the transformationT, starting with the pair (1,0). Now considerTto be the special case ofp= 0 andq= 1 in a family of transformationsTpqwhereTpqtransforms the pair (a,b) according toahttp://mitpress.mit.edu/sicp/full-te...k-Z-G-D-14.gifbq+aq+apandbhttp://mitpress.mit.edu/sicp/full-te...k-Z-G-D-14.gifbp+aq. Show that if we apply such a transformationTpqtwice, the effect is the same as using a single transformationTp'q' of the same form, and computep' andq' in terms ofpandq. This gives us an explicit way to square these transformations, and thus we can computeTnusing 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:

So what I'm looking for is basically some hints on where to start and how to think about solving this type of problem (in this case, how to find p' and q'). I'm looking more for general problem-solving methods than specifics. Here is some of the work I've done on the problem so far:Code:`(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

<??>; computep'

<??>; computeq'

(/ count 2)))

(else (fib-iter (+ (* b q) (* a q) (* a p))

(+ (* b p) (* a q))

p

q

(- count 1)))))

I started out trying to do some kind of algebra on the problem :/ Here is an image of my scratch work:

http://www.chrisdavaz.com/files/19.png (I gave a link rather than uploaded because no matter what I seem to do the website says that this is not a valid image file.)

And later on as text:

a <- bq + aq + ap

b <- bp + aq

a <- (bp + aq) q + (bq + aq + ap) q + (bq + aq + ap) p

b <- (bp + aq) p + (ba + aq + ap) q

bpq + aq^2 + bq^2 + aq^2 + apq + bqp + aqp + ap ^2

pq(b + a + b + a) + q^2(a + b + a) + p^2(a)

2 pq (b + a) + q^2 (2 a + b) + p^2 (a)

Later on I tried looking at the problem as a ratio between a and b (i.e., "the golden ratio"), since that ratio must be maintained from iteration to iteration:

a(p + q) + bq

----------------

bp + aq

Again, I feel like I am on to something but wind up just staring at this and getting nowhere.

Do any of the thoughts here make sense or is it just aimless wandering?