; fibonacci numbers
(define (make-matrix rows columns . value)
(do ((m (make-vector rows)) (i 0 (+ i 1)))
((= i rows) m)
(if (null? value)
(vector-set! m i (make-vector columns))
(vector-set! m i (make-vector columns (car value))))))
(define (matrix-rows x) (vector-length x))
(define (matrix-cols x) (vector-length (vector-ref x 0)))
(define (matrix-ref m i j) (vector-ref (vector-ref m i) j))
(define (matrix-set! m i j x) (vector-set! (vector-ref m i) j x))
(define-syntax for
(syntax-rules ()
((for (var first past step) body ...)
(let ((ge? (if (< first past) >= <=)))
(do ((var first (+ var step)))
((ge? var past))
body ...)))
((for (var first past) body ...)
(let* ((f first) (p past) (s (if (< first past) 1 -1)))
(for (var f p s) body ...)))
((for (var past) body ...)
(let* ((p past)) (for (var 0 p) body ...)))))
(define (matrix-multiply a b)
(let ((ar (matrix-rows a)) (ac (matrix-cols a))
(br (matrix-rows b)) (bc (matrix-cols b)))
(if (not (= ac br))
(error 'matrix-multiply "incompatible matrices")
(let ((c (make-matrix ar bc 0)))
(for (i ar)
(for (j bc)
(for (k ac)
(matrix-set! c i j
(+ (matrix-ref c i j)
(* (matrix-ref a i k)
(matrix-ref b k j)))))))
c))))
(define (fib-r n)
(cond ((zero? n) 0)
((< n 2) 1)
(else (+ (fib-r (- n 1)) (fib-r (- n 2))))))
(define (fib-i n)
(let loop ((n n) (f-1 1) (f-2 0))
(if (zero? n) f-2
(loop (- n 1) (+ f-1 f-2) f-1))))
(define (matrix-power m n)
(cond ((= n 1) m)
((even? n)
(matrix-power
(matrix-multiply m m)
(/ n 2)))
(else (matrix-multiply m
(matrix-power
(matrix-multiply m m)
(/ (- n 1) 2))))))
(define (fib-m n)
(if (zero? n) 0
(matrix-ref (matrix-power #(#(1 1) #(1 0)) n) 1 0)))
(time (display (fib-r 25)) (newline))
(time (display (fib-i 25000)) (newline))
(time (display (fib-m 25000)) (newline))