#lang sicp

;; Yeah okay, this one was extremely satisfying.
;; I just did the calculations on-paper.
;; it's some simple algebra anyway, but I'll type it here:
;; assuming Tpq on (a0, b0):
;; a1 = b0q + a0 * ( p + q)
;; b1 = b0p + a0q
;; a2 = (b0p + a0q) * p + (b0q + a0 * ( p + q)) * (p + q)
;; b2 = (b0p + a0q) * p + (b0q + a0 * ( p + q)) * q
;;
;; rearrange a2 and b2 into a similar form to the definition of a1 and b1:
;; (i.e. define a2 and b2 in terms of a0 and b0 and p and q)
;; a2 = b0 * (q^2 + 2*p*q) + a0 * (2*q^2 + 2*p*q + p^2)
;; b2 = b0 * (p^2 + q^2) + a0 * (q^2 + 2*p*q)
;;
;; from here we can see that p'= p^2 + q^2, and q'= q^2 + 2 * p * q
;; and as a result, we have logarithmic fibonacci!

;; printing the resulting number takes longer than calculating it lmao.

(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
                   (+ (* p p) (* q q)) ; compute p′
                   (+ (* q q) (* 2 (* p q))) ; compute q′
                   (/ count 2)))
        (else (fib-iter (+ (* b q) (* a q) (* a p))
                        (+ (* b p) (* a q))
                        p
                        q
                        (- count 1)))))