1 (define (square x)
2   (* x x))
3 (define (fib n)
4   (fib-iter 1 0 0 1 n))
5 (define (fib-iter a b p q count)
6   (cond ((= count 0) b)
7 	((even? count) (fib-iter a
8 				 b
9 				 (+ (square q) (square p))
10 				 (+ (* 2 q p) (square q))
11 				 (/ count 2)))
12 	(else (fib-iter (+ (* b q) (* a q) (* a p))
13 			(+ (* b p) (* a q))
14 			p
15 			q
16 			(- count 1)))))
17 
18 (define (test-case actual expected)
19   (load-option 'format)
20   (newline)
21   (format #t "Actual: ~A Expected: ~A" actual expected))
22 
23 (test-case (fib 0) 0)
24 (test-case (fib 1) 1)
25 (test-case (fib 2) 1)
26 (test-case (fib 3) 2)
27 (test-case (fib 4) 3)
28 (test-case (fib 5) 5)
29 (test-case (fib 6) 8)
30 (test-case (fib 7) 13)
31 (test-case (fib 8) 21)
32 (test-case (fib 9) 34)
33 
34 (define (fib n)
35   (fib-iter 1 0 0 1 n)
36 
37 (define (fib-iter a b p q n)
38   (cond ((= n 0) b)
39 	((even? n) (fib-iter a
40 			     b
41 			     (+ (square p) (square q))
42 			     (+ (* 2 p q) (square q))
43 			     (/ n 2)))
44 	(else (fib-iter (+ (* b q) (* a q) (* a p))
45 			(+ (* b p) (* a q))
46 			p 
47 			q
48 			(- n 1)))))