Code

#lang racket

(require "common.scm")

(define (fast-fib n)
  (fib-iter 1 0 0 1 n))

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

(define (iter-fib n)
  (fib-iter1 1 0 n))

(define (fib-iter1 a b count)
  (display count)
  (newline)
  (if (= count 0)
      b
      (fib-iter1 (+ a b) a (- count 1))))

; tests

(fast-fib 30)
(newline)
(iter-fib 30)

Output

30
15
14
7
6
3
2
1
0
832040

30
29
28
27
26
25
24
23
22
21
20
19
18
17
16
15
14
13
12
11
10
9
8
7
6
5
4
3
2
1
0
832040

Group theory in action.