(* This program calculates the nth fibonacci number
 * using alrogirhtm 1A: naive binary recursion
 *
 * compiled: N/A
 * executed: joy f1a.joy n
 *)
"numlib" libload .
(* fib : n -> n returns N'th Fibonacci number: F(n) = F(n-1) + F(n-2) *)
DEFINE fib == [small] [] [pred dup pred] [+] binrec .
(* f : n -> n handles negative arguments: F(-n) = F(n)*(-1)^(n+1) *)
DEFINE f == [negative] [dup [0 swap - fib] dip odd [] [neg] branch] [fib] ifte .
(* fprint : n -> - calculates and prints F(n) *)
DEFINE fprint == dup 'd 3 0 format "th Fibonacci number is " concat putchars f .
(* main : - -> - checks the command line arguments and calls fprint *)
DEFINE main == [argc 2 =]
               [argv second 10 strtol fprint]
               ["Usage: joy f1a.joy " putchars] ifte.
main .

(* f : N -> M returns N'th Fibonacci number
   It uses ALGORITHM 2A-3: DATA STRUCTURE - SIMPLE LIST*)
DEFINE f == [1 1] swap [[[+] nullary] infra] times 1 at .
DEFINE f_print == dup 'd 3 0 format "th Fibonacci number is " concat putchars f .
45 f_print .

(* f : N -> M returns N'th Fibonacci number
   It uses ALGORITHM 2B: SIMPLE RECURSION *)
DEFINE f == [1 1] dip [small] [pop swap pop] [pred [dup [swap] dip +] dip] tailrec .
DEFINE f_print == dup 'd 3 0 format "th Fibonacci number is " concat putchars f .
45 f_print .

(* f : N -> M returns N'th Fibonacci number
   It uses ALGORITHM 2C: NON-RECURSIVE LOOP *)
(* Based on the standard library numlib.joy *)

DEFINE f == [0 1] dip [swap [+] unary] times popd .
DEFINE f_print == dup 'd 3 0 format "th Fibonacci number is " concat putchars f .
45 f_print .

"mtrlib" libload.
(* mp : M1 n -> M2  raises matrix M1 into nth power *)
DEFINE mp == 
 [small] [pop] [2 div rollup dupd]
 [dup mm-mul-m rolldown null [popd] [mm-mul-m] branch] linrec .
(* f : n1 -> n2 returns n1'th Fibonacci number
   It uses ALGORITHM 3A: MATRIX EQUATION *)
DEFINE f == [[1 1][1 0]] swap mp first first .
DEFINE f_print == dup 'd 3 0 format "th Fibonacci number is " concat putchars f .
45 f_print .

(* f : N -> M returns N'th Fibonacci number
   It uses ALGORITHM 3B: FAST RECURSION *)
DEFINE f ==
 [[[2 <][pop 1 1]] [[2 =][pop 2 1]]
  [[2 rem 1 =] [pred 2 /] [
   dupd dupd dupd dup [+ *] dip swapd dup
   [* +] dip dup * rolldown dup * + ]]
  [[2 rem 0 =] [2 / pred] [
   dupd dupd dup [+ dup dup * rolldown dup * + rotate] dip
   dupd * rollup * + ]]
 [[]] ] condlinrec pop.
DEFINE f_print == dup 'd 3 0 format "th Fibonacci number is " concat putchars f .
45 f_print .

(* f : N -> M returns N'th Fibonacci number
   It uses ALGORITHM 3C: BINET'S FORMULA *)
DEFINE f == 1 5 sqrt dup rollupd + 2 / swap succ dupd swap dupd 1 swap - swap 
		    pow rollup pow swap - swap / trunc .
DEFINE f_print == dup 'd 3 0 format "th Fibonacci number is " concat putchars f .
45 f_print .