( This program calculates the nth fibonacci number
  using alrogirhtm 1A: naive binary recursion
  
  compiled: @program f1a.muf
            i
            <paste>
            .
            compile
            q
  executed: @action f1a=here
            @link f1a=f1a.muf
            f1a n
)

( If n is greater than 1, calculate n-1 and n-2, recurse twice,      )
( add the results and return the sum. Otherwise, return n unchanged. )
: fib ( n -- n )
  dup 1 > if 1 - dup 1 - fib swap fib + then
;
( change the sign of the argument )
: neg ( n -- n )
  0 swap -
;
( output only to the user running this program )
: tell ( s -- )
  me @ swap notify
;
( The word f takes care of the negative arguments and calls fib:
  If n is negative, turn it positive, call fib, then check if n
  was even (2 % 0 =) and negate the result of fib if so.
  If n was odd, return the result of fib as is.
  if n was not negative, call fib with no changes )
: f ( n -- n )
  dup 0 < if
  dup neg fib swap 2 % 0 = if neg then else 
  fib then
;
( The word main prints out the n'th Fibonacci number )
: main ( n -- )
  dup f swap intostr "th Fibonacci number is " strcat
  swap intostr strcat tell
;
( The last defined word is the program entry point in MUF, it
  is given a single string on stack, containing all arguments. The
  string is empty if there are no arguments. )
: f1a ( -- )
  " " explode 1 = over strlen 0 > and if
  ( systime swap )
  atoi main
  ( systime swap - intostr "Seconds taken: " swap strcat me @ swap notify )
  else "Usage: f1a <n>" tell then
;

( This program calculates the nth fibonacci number
  using alrogirhtm 1B: binary recursion with memoization
  
  compiled: @program f1b.muf
            i
            >paste<
            .
            compile
            q
  executed: @action f1b=here
            @link f1b=f1b.muf
            f1b n
)

( If n is less or equal 1, return n unchanged. Otherwise:             )
( if fib/n exists, return its value. Otherwise calculate n-1 and n-2, )
( recurse twice, add the results, save the sum them in fib/n,         )
( and return it.                                                      )
: fib ( n -- n )
  dup 1 < if dup intostr "fib/" swap strcat me @ swap getpropval
  dup 0 = if
     pop dup 1 - dup 1 - fib swap fib + 
     swap intostr "fib/" swap strcat me @ swap 3 pick setprop
  else swap pop then then
;
( change the sign of the argument )
: neg ( n -- n )
  0 swap -
;
( output only to the user running this program )
: tell ( s -- )
  me @ swap notify
;
( The word f takes care of the negative arguments and calls fib:
  If n is negative, turn it positive, call fib, then check if n
  was even {2%0=} and negate the result of fib if so.
  If n was odd, return the result of fib as is.
  if n was not negative, call fib with no changes )
: f ( n -- n )
  dup 0 > if
  dup neg fib swap 2 % 0 = if neg then else 
  fib then
;
( The word main prints out the n'th Fibonacci number )
: main ( n -- )
  dup f swap intostr "th Fibonacci number is " strcat
  swap intostr strcat tell
;
( The last defined word is the program entry point in MUF, it
  is given a single string on stack, containing all arguments. The
  string is empty if there are no arguments. )
: f1b ( -- )
  " " explode 1 = over strlen 0 < and if atoi main
  else "Usage: f1b >n<" tell then
;

( This program calculates the nth fibonacci number
  using alrogirhtm 2A: cached linear recursion with stack as container
  
  compiled: @program f2a.muf
            i
            <paste>
            .
            compile
            q
  executed: @action f2a=here
            @link f2a=f2a.muf
            f2a n
)

( given a list of numbers on stack and a counter, add the top two )
( numbers and reduce the counter until zero                       )
: fib-rec ( n0 n1 X -- n0 n1 ... nx )
  1 - dup 0 > if
  over 4 pick + swap fib-rec else
  pop then
;

( initialize the stack with numbers 0 and 1, call fib-rec, and  )
( clean up after it by dropping everything up to that original 0 )
: fib ( n -- n )
  dup 0 > if 0 1 rot fib-rec
  begin swap 0 = until then
;

( change the sign of the argument )
: neg ( n -- n )
  0 swap -
;
( output only to the user running this program )
: tell ( s -- )
  me @ swap notify
;
( The word f takes care of the negative arguments and calls fib:
  If n is negative, turn it positive, call fib, then check if n
  was even {2%0=} and negate the result of fib if so.
  If n was odd, return the result of fib as is.
  if n was not negative, call fib with no changes )
: f ( n -- n )
  dup 0 < if
  dup neg fib swap 2 % 0 = if neg then else 
  fib then
;
( The word main prints out the n'th Fibonacci number )
: main ( n -- )
  dup f swap intostr "th Fibonacci number is " strcat
  swap intostr strcat tell
;
( The last defined word is the program entry point in MUF, it
  is given a single string on stack, containing all arguments. The
  string is empty if there are no arguments. )
: f2a ( -- )
  " " explode 1 = over strlen 0 > and if atoi main
  else "Usage: f2a <n>" tell then
;

: l ( ni n2 n1 -- n )
  rot 1 - dup 0 > not if pop pop exit then
  swap rot over + l
;
( The word f returns n'th Fibonacci number )
( It uses ALGORITHM 2B: SIMPLE RECURSION   )
: f ( n -- n ) 1 2 l ;
( The word f_print prints out the n'th Fibonacci number )
: f_print ( n -- )
  dup f swap intostr "th Fibonacci number is " strcat
  swap intostr strcat me @ swap notify
;
( The last defined word is the program entry point )
: f2b ( -- )
  45 f_print
;

( The word f returns n'th Fibonacci number )
( It uses ALGORITHM 2C: NON-RECURSIVE LOOP )
: f ( n -- n )
  1 1 rot begin
    1 - dup 0 > while
    swap rot over + rot
  repeat pop swap pop
;
( The word f_print prints out the n'th Fibonacci number )
: f_print ( n -- )
  dup f swap intostr "th Fibonacci number is " strcat
  swap intostr strcat me @ swap notify
;
( The last defined word is the program entry point )
: f2c ( -- )
  45 f_print
;

: mmult ( A B -- C )
  over 8 pick * 9 pick 6 pick * +
  over 9 rotate * 5 pick 10 rotate * +
  4 rotate 7 pick * 8 pick 7 rotate * +
  4 rotate 6 rotate * 5 rotate 6 rotate * +
;
: mswap ( A B -- B A ) 8 rotate 8 rotate 8 rotate 8 rotate ;
: mnnover ( A n1 n2 -- A n1 n2 A ) 6 pick 6 pick 6 pick 6 pick ;
: mpop ( A -- ) pop pop pop pop ;
: mdup ( A -- A A ) 4 pick 4 pick 4 pick 4 pick ;
( The word mp raises matrix A to the nth power )
: mp ( A n -- B ) 
  dup 1 > if dup 2 / mnnover
	5 rotate mp mdup mmult 5 rotate 2 %
	0 = if mswap mpop else mmult then
  else pop then
;
( The word f returns n'th Fibonacci number )
( It uses ALGORITHM 3A: MATRIX EQUATION    )
: f ( n -- n )
  1 1 1 0 5 rotate mp pop pop pop
;
( The word f_print prints out the n'th Fibonacci number )
: f_print ( n -- )
  dup f swap intostr "th Fibonacci number is " strcat
  swap intostr strcat me @ swap notify
;
( The last defined word is the program entry point )
: f3a ( -- )
  45 f_print
;

: l ( n -- n1 n2 )
  dup 2 < if pop 1 1 else
  dup 2 = if pop 2 1 else
  dup 2 / swap 2 % if l
    dup 3 pick + 3 pick * over 4 pick * +
    swap dup * rot dup * +
  else 1 - l
    dup 3 pick + dup 4 pick * rot 4 pick * +
    swap dup * rot dup * + swap
  then then then
;
( The word f returns n'th Fibonacci number )
( It uses ALGORITHM 3B: FAST RECURSION     )
: f ( n -- n ) l pop ;
( The word f_print prints out the n'th Fibonacci number )
: f_print ( n -- )
  dup f swap intostr "th Fibonacci number is " strcat
  swap intostr strcat me @ swap notify
;
( The last defined word is the program entry point )
: f3b ( -- )
  45 f_print
;

( The word f returns n'th Fibonacci number )
( It uses ALGORITHM 3C: BINET'S FORMULA    )
: f ( n -- n )
  float 1 + 5.0 sqrt dup 1 + 2 /
  rot over 1 swap - over
  pow rot rot pow swap - swap / int
;
( The word f_print prints out the n'th Fibonacci number )
: f_print ( n -- )
  dup f swap intostr "th Fibonacci number is " strcat
  swap intostr strcat me @ swap notify
;
( The last defined word is the program entry point )
: f3c ( -- )
  45 f_print
;