(declare (usual-integrations))
; Function (f n) returns the n'th Fibonacci number
; It uses ALGORITHM 1A: BINARY RECURSION
(define f (lambda (n)
 (if (< n 2) 1
  (+ (f (- n 1)) (f(- n 2))))))
; Function (f_print n) prints the n'th Fibonacci number
(define f_print (lambda (n)
 (display (string-append
  (number->string n) "th Fibonacci number is " (number->string (f n))))))
; This is the entry point of the program.
(f_print 45)

(declare (usual-integrations))
; Function (f n) returns the n'th Fibonacci number
; It uses ALGORITHM 2A-3: DATA STRUCTURE - SIMPLE LIST
(define f (lambda (n)
 (letrec ((z (lambda (k)
  (append k (list (+ (list-ref k (- (length k) 1))
                     (list-ref k (- (length k) 2)))))))
		  (l (lambda (n r)
  (if (< n (length r)) (list-ref r n) (l n (z r))))))
 (l n '(1 1)))))
; Function (f_print n) prints the n'th Fibonacci number
(define f_print (lambda (n)
 (display (string-append
  (number->string n) "th Fibonacci number is " (number->string (f n))))))
; This is the entry point of the program.
(f_print 50000)

(declare (usual-integrations))
; Function (f n) returns the n'th Fibonacci number
; It uses ALGORITHM 2B: SIMPLE RECURSION
(define f (lambda (n)
 (letrec ((l (lambda (a b c)
  (if (< c 2) a (l (+ a b) a (- c 1))))))
 (l 1 1 n))))
; Function (f_print n) prints the n'th Fibonacci number
(define f_print (lambda (n)
 (display (string-append
  (number->string n) "th Fibonacci number is " (number->string (f n))))))
; This is the entry point of the program.
(f_print 50000)

(declare (usual-integrations))
; Function (f n) returns the n'th Fibonacci number
; It uses ALGORITHM 2C: NON-RECURSIVE LOOP
(define f (lambda (n)
 (do ((x1 1) (x2 1) (tmp 1) (i 1 (+ i 1)))
  ((> i n) x1)
  (set! tmp (+ x1 x2))
  (set! x1 x2)
  (set! x2 tmp))))
; Function (f_print n) prints the n'th Fibonacci number
(define f_print (lambda (n)
 (display (string-append
  (number->string n) "th Fibonacci number is " (number->string (f n))))))
; This is the entry point of the program.
(f_print 50000)

(declare (usual-integrations))
; Function (mm m1 m2) multiplies two 2x2 matricies m1 and m2
(define mm (lambda (l1 l2)
 (cons (cons (+ (* (car (car l1)) (car (car l2)))
                (* (cdr (car l1)) (car (cdr l2))))
             (+ (* (car (car l1)) (cdr (car l2)))
                (* (cdr (car l1)) (cdr (cdr l2)))))
       (cons (+ (* (car (cdr l1)) (car (car l2)))
                (* (cdr (cdr l1)) (car (cdr l2))))
             (+ (* (car (cdr l1)) (cdr (car l2)))
                (* (cdr (cdr l1)) (cdr (cdr l1))))))))
; Function (mp n m) raises the matrix m into nth power
(define mp (lambda (n m)
 (if (<= n 1) m
   (let* ((a (mp (quotient n 2) m))
		  (s (mm a a)))
	 (if (= 1 (modulo n 2)) (mm m s) s)))))
; Function (f n) returns the n'th Fibonacci number
; It uses ALGORITHM 3A: MATRIX EQUATION
(define f (lambda (n)
 (car (car (mp n '((1 . 1) 1 . 0))))))
; Function (f_print n) prints the n'th Fibonacci number
(define f_print (lambda (n)
 (display (string-append
  (number->string n) "th Fibonacci number is " (number->string (f n))))))
; This is the entry point of the program.
(f_print 500000)

(declare (usual-integrations))
; Function (f n) returns the n'th Fibonacci number
; It uses ALGORITHM 3B: FAST RECURSION
; This function was written by Bradley Lucier from Purdue University
; who saw my poor code and rewrote it 30% faster and a whole lot cleaner.
; Guys, do this more often!
(define (f n)
 ;; returns f_n f_{n+1}
 (case n
  ((1) (values 1 1))
  ((2) (values 1 2))
  (else
   (let ((m (quotient n 2)))
	(call-with-values
	 (lambda () (f m))
	 (lambda (f_m f_m+1)
	  (let ((f_m^2 (* f_m f_m))
			(f_m+1^2 (* f_m+1 f_m+1)))
	   (if (even? n)
		(values (- (* 2 f_m+1^2)
				 (* 3 f_m^2)
				 (if (odd? m)
				  -2
				  2))
		 (+ f_m^2 f_m+1^2))
		(values (+ f_m^2 f_m+1^2)
		 (- (* 3 f_m+1^2)
		  (* 2 f_m^2)
		  (if (odd? m)
		   -2
		   2)))))))))))

; Function (f_print n) prints the n'th Fibonacci number
(define f_print (lambda (n)
 (display (string-append
  (number->string n) "th Fibonacci number is " (number->string (car (call-with-values (lambda () (f n)) cons)))))))
; This is the entry point of the program.
(f_print 50000)

(declare (usual-integrations))
; Function (f n) returns the n'th Fibonacci number
; It uses ALGORITHM 3C: BINET'S FORMULAN
(define f (lambda (n)
 (let ((phi (/ (+ 1 (sqrt 5)) 2)))
  (round (/ (- (expt phi (+ n 1)) (expt (- 1 phi) (+ n 1))) (sqrt 5))))))
; Function (f_print n) prints the n'th Fibonacci number
(define f_print (lambda (n)
 (display (string-append
  (number->string n) "th Fibonacci number is " (number->string (f n))))))
; This is the entry point of the program.
(f_print 74)