( The word f returns n'th Fibonacci number )
( It uses ALGORITHM 1A: BINARY RECURSION   )
: f ( n -- n )
  dup 2 < if pop 1 exit then
  1 - dup 1 - f swap f +
;
( 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 )
: f1a ( -- )
  45 f_print
;

( This word reads Fibonacci numbers from a property list )
( Missing values are calculated on the spot              )
: f-get ( n -- n )
  dup intostr "fib/" swap strcat me @ swap getpropval
  dup 0 = if
    pop dup 1 - dup f-get swap 1 - f-get +
    "fib/" rot intostr strcat me @ swap "" 4 pick addprop
  else swap pop then
;
( The word f returns n'th Fibonacci number             )
( It uses ALGORITHM 2A-3: DATA STRUCTURE - SIMPLE LIST )
: f ( n -- n )
  me @ "fib/0" "" 1 addprop
  me @ "fib/1" "" 1 addprop
  f-get
;
( 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 )
: f2a ( -- )
  45 f_print
;

: 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
;