;; from mupad

;; Friedrich Schwarz 22.12.1996 
;; fibonacci(n) returns the nth Fibonacci number F_n
;; n - non-negative integer

;; The algorithm simulates the intelligent calculation 
;; of powers [as used in the function powermod].

(defun fibonacci (n)
  (cond ((= n 0) 0)
        ((= n 1) 1)
        (t (let ((x 1) (y 0) (z 1) (a 1) (b 1) (c 0) Z C)
             (while (> n 1)
               (if (= (mod n 2) 1)
                   (setq Z (+ (* y b) (* z c))
                         y (+ (* x b) (* y c))
                         z Z
                         x (+ y z)))
               (setq C (+ (* b b) (* c c))
                     b (* (+ a c) b)
                     c C
                     a (+ b c)
                     n (quotient n 2)))
             (+ (* x b) (* y c))))))

(defun fibonacci-iter (n)
  (let ((i (- n 2))
        (f1 1)
        (f2 1)
        f3)
    (if (or (= n 1) (= n 2))
        (setq f3 1)
      (while (> i 0)
        (setq f3 (+ f1 f2)
              f1 f2
              f2 f3
              i (1- i))))
    f3))

(defun fibonacci-recur (n)
  (if (<= n 2)
      1
    (+ (fibonacci-recur (- n 1)) (fibonacci-recur (- n 2)))))

;;numlib::fibonacci := proc(n)
;;  local x, y, z, a, b, c, Z, C;
;;begin
;;  if testargs() then
;;    if args(0) <> 1 then
;;      error("expected one argument in function call")
;;    elif not testtype(n,Type::Numeric) then
;;      return(procname(args()))
;;    elif domtype(n) <> DOM_INT or n < 0 then
;;      error("the argument must be a non-negative integer")
;;    end_if
;;  end_if;
;;  if n = 0 then
;;    0
;;  elif n = 1 then
;;    1
;;  else
;;    x := 1;
;;    y := 0;
;;    z := 1;
;;    a := 1;
;;    b := 1;
;;    c := 0;
;;    while n > 1 do
;;      if modp(n,2) = 1 then
;;        Z := y*b + z*c;
;;        y := x*b + y*c;   
;;        z := Z;
;;        x := y + z; 
;;      end_if;
;;      C := b^2 + c^2;
;;      b := (a + c)*b;
;;      c := C;
;;      a := b + c;  
;;      n := n div 2
;;   end_while;
;;   x*b + y*c
;;  end_if
;;end_proc: