% This program calculates the nth fibonacci number
% using alrogirhtm 1A: naive binary recursion
% 
% compiler: N/A
% executed: echo "n main" | gs -q f1a.ps -
% 
% Naive binary recursion: F(n) = F(n-1) + F(n-2)
% 
/fib {dup 1 gt
        {1 sub dup 1 sub fib exch fib add
        } if
     } def

% The word f takes care of the negative arguments and calls fib
/f {dup 0 lt
        {dup neg fib exch 2 mod 0 eq {neg} if}
        {fib} ifelse
   } def

% convert to string: first calculates the number of characters
% necessary to represent the number, which equals
% 1+log(n), and plus 1 more for the negatives, then creates the string
% of this size and converts.
% ( n -- s )
/mycvs { dup dup 0 eq { pop 1 } 
             { dup abs log 1 add exch 0 lt {1 add} if } ifelse
         cvi string cvs
       } def

% Function main prints n'th Fibonacci number to stdout
% (remove the "print" statements and uncomment the other lines below to print to paper)
/main { %/Times-Roman findfont 20 scalefont setfont newpath 72 72 moveto
          dup mycvs print % show
          (th Fibonacci number is ) print % show
          f mycvs print (\n) print % show showpage
      } def

% This program calculates the nth fibonacci number
% using alrogirhtm 1B: binary recursion with memoization
% 
% compiler: N/A
% executed: echo "n main" | gs -q f1b.ps -
% 

% if n is found in dict, return the value from the dictionary
% otherwise recurse on n-2, recurse on n-1, add the results
% mfib ( dict n  -- f )
/mfib { 2 copy known
               { get }
               { 1 sub 2 copy 1 sub mfib 3 1 roll mfib add } ifelse
     } def

% initialize the memoization dictionary and call mfib
/fib { << 0 0 1 1 >> exch mfib } def

% The word f takes care of the negative arguments and calls fib
/f {dup 0 lt
        {dup neg fib exch 2 mod 0 eq {neg} if}
        {fib} ifelse
   } def

% convert to string: first calculates the number of characters
% necessary to represent the number, which equals
% 1+log(n), and plus 1 more for the negatives, then creates the string
% of this size and converts.
% ( n -- s )
/mycvs { dup dup 0 eq { pop 1 } 
             { dup abs log 1 add exch 0 lt {1 add} if } ifelse
         cvi string cvs
       } def

% Function main prints n'th Fibonacci number to stdout
% (remove the "print" statements and uncomment the other lines below to print to paper)
/main { %/Times-Roman findfont 20 scalefont setfont newpath 72 72 moveto
          dup mycvs print % show
          (th Fibonacci number is ) print % show
          f mycvs print (\n) print % show showpage
         } def

% This program calculates the nth fibonacci number
% using alrogirhtm 2A: cached linear iteration with operand stack as container
% 
% compiler: N/A
% executed: echo "n main" | gs -q f2a.ps -

% fibrec sums the top two values on stack and pushes the sum until
% the length of stack up to mark equals N+1. Cleans up when done. 
% fibrec ( N mark 0 1 ... f1 f2 -- f(N) )
/fibrec {counttomark dup 2 add index gt
            {counttomark 2 add 1 roll cleartomark pop }
            {2 copy add fibrec } ifelse
        } def

% marks the stack, loads up the first two values, and calls fibrec
/fib { mark 0 1 fibrec } def

% The word f takes care of the negative arguments and calls fib
/f {dup 0 lt
        {dup neg fib exch 2 mod 0 eq {neg} if}
        {fib} ifelse
   } def

% convert to string: first calculates the number of characters
% necessary to represent the number, which equals
% 1+log(n), and plus 1 more for the negatives, then creates the string
% of this size and converts.
% ( n -- s )
/mycvs { dup dup 0 eq { pop 1 } 
             { dup abs log 1 add exch 0 lt {1 add} if } ifelse
         cvi string cvs
       } def

% Function main prints n'th Fibonacci number to stdout
% (remove the "print" statements and uncomment the other lines below to print to paper)
/main { %/Times-Roman findfont 20 scalefont setfont newpath 72 72 moveto
          dup mycvs print % show
          (th Fibonacci number is ) print % show
          f mycvs print (\n) print % show showpage
         } def

% This program calculates the nth fibonacci number
% using alrogirhtm 2B: linear recursion with accumulators
% 
% compiler: N/A
% executed: echo "n main" | gs -q f2b.ps -

% fibrec calculates F(n) by linear recursion, keeping two 
% accumulators: f(n-1) and f(n-2)
% fibrec ( n f(n-2) f(n-1) -- f )
/fibrec {
        3 2 roll 1 sub dup 1 le
             { pop add  } % if n<=1, drop n and add the accumulators 
             { 3 1 roll exch 1 index add fibrec } ifelse
        } def

% loads up the first two values, and calls fibrec
/fib { 0 1 fibrec } def

% The word f takes care of the negative arguments and calls fib
/f {dup 0 lt
        {dup neg fib exch 2 mod 0 eq {neg} if}
        {fib} ifelse
   } def

% convert to string: first calculates the number of characters
% necessary to represent the number, which equals
% 1+log(n), and plus 1 more for the negatives, then creates the string
% of this size and converts.
% ( n -- s )
/mycvs { dup dup 0 eq { pop 1 } 
             { dup abs log 1 add exch 0 lt {1 add} if } ifelse
         cvi string cvs
       } def

% Function main prints n'th Fibonacci number to stdout
% (remove the "print" statements and uncomment the other lines below to print to paper)
/main { %/Times-Roman findfont 20 scalefont setfont newpath 72 72 moveto
          dup mycvs print % show
          (th Fibonacci number is ) print % show
          f mycvs print (\n) print % show showpage
         } def

% This program calculates the nth fibonacci number
% using alrogirhtm 2C: imperative loop with mutable variables
% 
% compiler: N/A
% executed: echo "n main" | gs -q f2c.ps -

% if N>1, take 0,1 and repeat addition N-1 times and return the last sum
% otherwise just return N
/fib {dup 1 gt { 1 sub 0 exch 1 exch
                    { dup 3 2 roll add } repeat exch pop
                } if
     } def

% The word f takes care of the negative arguments and calls fib
/f {dup 0 lt
        {dup neg fib exch 2 mod 0 eq {neg} if}
        {fib} ifelse
   } def

% convert to string: first calculates the number of characters
% necessary to represent the number, which equals
% 1+log(n), and plus 1 more for the negatives, then creates the string
% of this size and converts.
% ( n -- s )
/mycvs { dup dup 0 eq { pop 1 } 
             { dup abs log 1 add exch 0 lt {1 add} if } ifelse
         cvi string cvs
       } def

% Function main prints n'th Fibonacci number to stdout
% (remove the "print" statements and uncomment the other lines below to print to paper)
/main { %/Times-Roman findfont 20 scalefont setfont newpath 72 72 moveto
          dup mycvs print % show
          (th Fibonacci number is ) print % show
          f mycvs print (\n) print % show showpage
         } def

% This program calculates the nth fibonacci number
% using alrogirhtm 3A: martix multiplication
% 
% compiler: N/A
% executed: echo "n main" | gs -q f3a.ps -

% deep copy of a matrix
% ( m -- m m )
/dup-mat { dup matrix copy } def

% raises matrix to n'th power using exponentiation by squaring
% ( matrix N -- matrix )
/matrix-power {
       dup 1 gt { exch dup-mat % b = a
                  2 index 2 idiv matrix-power % a=a^n/2
                  dup-mat matrix concatmatrix % a=a*a
                  3 2 roll 2 mod 1 eq { matrix concatmatrix } % if n%2==1 a=a*b
                  { exch pop }ifelse
                } { pop } ifelse % for n <= 1, return matrix unchanged
     } def

% raise the matrix (1, 1) (1, 0) to n-1'st power and return the top left 
% corner (or return 0 if n == 0)
% (note that postscript matrix is 6 numbers: a00, a01, a10, a11, a20, a21,
%  with the third column pre-set to 0 0 1. Which is fine for this purpose)
% (also note, postscript matirix contains real numbers, hence cvi)
/fib { dup 0 gt
       { [ 1 1 1 0 0 0 ] exch 1 sub matrix-power 0 get cvi } if
     } def

% The word f takes care of the negative arguments and calls fib
/f {dup 0 lt
        {dup neg fib exch 2 mod 0 eq {neg} if}
        {fib} ifelse
   } def

% convert to string: first calculates the number of characters
% necessary to represent the number, which equals
% 1+log(n), and plus 1 more for the negatives, then creates the string
% of this size and converts.
% ( n -- s )
/mycvs { dup dup 0 eq { pop 1 } 
             { dup abs log 1 add exch 0 lt {1 add} if } ifelse
         cvi string cvs
       } def

% Function main prints n'th Fibonacci number to stdout
% (remove the "print" statements and uncomment the other lines below to print to paper)
/main { %/Times-Roman findfont 20 scalefont setfont newpath 72 72 moveto
          dup mycvs print % show
          (th Fibonacci number is ) print % show
          f mycvs print (\n) print % show showpage
         } def

% This program calculates the nth fibonacci number
% using alrogirhtm 3b: fast recursion 
% 
% compiler: N/A
% executed: echo "n main" | gs -q f3b.ps -

% calls the recursive function
/fib { fib-rec exch pop } def
% calculate a pair of fibonacci numbers according to
% the recurrent relationship: 
%  F(2n-1) = F(n-1)^2 + F(n)^2
%  F(2n) = (2F(n-1) + F(n))F(n)
%  
%  here f1 = F(n-1), f2 = F(n), f3 = F(n+1)
% ( n -- n1 n2) 
/fib-rec {
    dup 0 le {pop 0 0} {
    dup 1 eq {pop 0 1} {
    dup 2 mod exch 2 idiv fib-rec % recurse on n/2, obtaining f1 f2
    2 copy add 4 3 roll % f3 = f1+f2, bring n%2 down
    1 eq { dup 4 3 roll add 2 index mul % f2 f3 (f1+f3)*f2
           3 1 roll dup mul exch dup mul add } % (f1+f3)*f2 f3^2+f2^2
         { exch dup 3 index 4 3 roll add mul % f1 f2 (f1+f3)*f2
           3 1 roll dup mul exch dup mul add exch } ifelse % f1^2+f2^2, (f1+f3)*f2
    } ifelse
    } ifelse
} def

% The word f takes care of the negative arguments and calls fib
/f {dup 0 lt
        {dup neg fib exch 2 mod 0 eq {neg} if}
        {fib} ifelse
   } def

% convert to string: first calculates the number of characters
% necessary to represent the number, which equals
% 1+log(n), and plus 1 more for the negatives, then creates the string
% of this size and converts.
% ( n -- s )
/mycvs { dup dup 0 eq { pop 1 } 
             { dup abs log 1 add exch 0 lt {1 add} if } ifelse
         cvi string cvs
       } def

% Function main prints n'th Fibonacci number to stdout
% (remove the "print" statements and uncomment the other lines below to print to paper)
/main { %/Times-Roman findfont 20 scalefont setfont newpath 72 72 moveto
          dup mycvs print % show
          (th Fibonacci number is ) print % show
          f mycvs print (\n) print % show showpage
         } def

% This program calculates the nth fibonacci number
% using alrogirhtm 3C: Binet's formula with rounding
% 
% compiler: N/A
% executed: echo "n main" | gs -q f3c.ps -

% This word calculates the nth fibonacci number
% as floor( phi^n/sqrt(5) + 1/2), where phi = (1+sqrt(5.0))/2;
/fib { 5 sqrt dup 1 add 2 div 3 2 roll % sqrt(5) phi n
       exp exch div round cvi
     } def

% The word f takes care of the negative arguments and calls fib
/f {dup 0 lt
        {dup neg fib exch 2 mod 0 eq {neg} if}
        {fib} ifelse
   } def

% convert to string: first calculates the number of characters
% necessary to represent the number, which equals
% 1+log(n), and plus 1 more for the negatives, then creates the string
% of this size and converts.
% ( n -- s )
/mycvs { dup dup 0 eq { pop 1 } 
             { dup abs log 1 add exch 0 lt {1 add} if } ifelse
         cvi string cvs
       } def

% Function main prints n'th Fibonacci number to stdout
% (remove the "print" statements and uncomment the other lines below to print to paper)
/main { %/Times-Roman findfont 20 scalefont setfont newpath 72 72 moveto
          dup mycvs print % show
          (th Fibonacci number is ) print % show
          f mycvs print (\n) print % show showpage
         } def