;;; fibon.lsp - Fibonacci Sequence 

(defun fib-smj (n)
  (cond ((zerop n) 1)
	((equal n 1) 1)
	(T (plus (fib-smj (difference n 1))
		 (fib-smj (difference n 2))))))

;; **********

(defun fib-helper (a b p q n)
  (cond ((zerop n) b)
	((oddp n) (let ((aq (times a q)))
		    (fib-helper (plus (times b q) aq (times a p))
				(plus (times b p) aq)
				p
				q
				(sub1 n))))
	(t (let ((qq (times  q q)))
	     (fib-helper a
			 b
			 (plus (times p p) qq)
			 (plus qq (times 2 p q))
			 (quotient n 2))))))

(defun fib-rm (n)
  (fib-helper 1 0 0 1 n))

;; **********

(defun smooth-fib (x)
  (let* ((pi (atan 0 -1))
	 (sqrt-5 (sqrt 5))
	 (gold-rat (quotient (add1 sqrt-5) 2)))
    (quotient (difference (expt gold-rat x)
			  (times (expt gold-rat (minus x))
				 (cos (times pi x))))
	      sqrt-5)))

;; **********

(defun fib-tab (n)
  (do ((row 0 (1+ row)))
      ((> row n))
    (format t "~&~a~10t~a~20t~a~30t~a" row (fib-smj row) (fib-rm row) (smooth-fib row))))