; 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))