cubbi.com: fibonacci numbers in PostScript

cubbi.com: fibonacci numbers in postscript

serious stuff
  www.cubbi.com
personal
programming
  fibonacci numbers
    algorithms
    benchmarks
    forth examples
    postscript examples
    muf examples
    joy examples
    j examples
    scheme examples
    hope examples
    ocaml examples
    haskell examples
    prolog examples
    c++ examples
    java examples
    assembly language examples
    fortran examples
    c examples
    sh examples
    awk examples
    perl examples
    tcl examples
  asmix
  hacker test
  resume
science
martial arts
fun stuff
  www.cubbi.org

PostScript
Date: 1982
Type: Concatenative language
Usage: PostScript-printers, PostScript interpreters, any graphical programs that can read or write PostScript files

ALGORITHM 1A: BINARY RECURSION

% Function f returns the n'th Fibonacci number
% It uses ALGORITHM 1A: BINARY RECURSION
/f {dup 1 le {pop 1} {1 sub dup 1 sub f exch f add} ifelse} def
% Function f_print prints n'th Fibonacci number
/f_print {/Times-Roman findfont 20 scalefont setfont newpath 72 72 moveto
          dup 2 string cvs show (th Fibonacci number is ) show
          f 10 string cvs show showpage
         } def
% Entry point
45 f_print

ALGORITHM 2A-3: DATA STRUCTURE - SIMPLE LIST

% Function f returns n'th Fibonacci number
% It uses ALGORITHM 2A-3: DATA STRUCTURE - SIMPLE LIST
/f {dup 0 ne
      { dup 1 add array dup 0 1 put dup 1 1 put exch 2 exch 1 sub
       { dup 3 2 roll dup 3 2 roll 1 sub get 1 index 3 index 2 sub get
         add 1 index exch 3 index exch put exch 1 add
       } repeat 1 sub get
      } {pop 1} ifelse
} def
% Function f_print prints n'th Fibonacci number
/f_print {/Times-Roman findfont 20 scalefont setfont newpath 72 72 moveto
          dup 2 string cvs show (th Fibonacci number is ) show
          f 10 string cvs show showpage
         } def
% Entry point
45 f_print

ALGORITHM 2B: SIMPLE RECURSION

% Function f returns n'th Fibonacci number
% It uses ALGORITHM 2B: SIMPLE RECURSION
/f {1 2 l} def
/l {3 -1 roll 1 sub dup 0 le {pop pop}
    {3 1 roll dup 3 2 roll add l} ifelse
   } def
% Function f_print prints n'th Fibonacci number
/f_print {/Times-Roman findfont 20 scalefont setfont newpath 72 72 moveto
          dup 2 string cvs show (th Fibonacci number is ) show
          f 10 string cvs show showpage
         } def
% Entry point
45 f_print

ALGORITHM 2C: NON-RECURSIVE LOOP

% Function f returns n'th Fibonacci number
% It uses ALGORITHM 2C: NON-RECURSIVE LOOP
/f {dup 0 gt {1 sub} if 1 1 3 2 roll {dup 3 2 roll add} repeat exch pop} def
% Function f_print prints n'th Fibonacci number
/f_print {/Times-Roman findfont 20 scalefont setfont newpath 72 72 moveto
          dup 2 string cvs show (th Fibonacci number is ) show
          f 10 string cvs show showpage
         } def
% Entry point
45 f_print

ALGORITHM 3A: MATRIX EQUATION

% Function f returns n'th Fibonacci number
% It uses ALGORITHM 3A: MATRIX EQUATION
/f {1 1 1 0 5 -1 roll mp pop pop pop} def
% Function mp raises a matrix into nth power
/mp {dup 1 gt {dup -1 bitshift
      5 index 5 index 5 index 5 index
      5 -1 roll mp mdup mm 5 -1 roll 2 mod 0 eq {
       mswap pop pop pop pop} {mm} ifelse
     } {pop} ifelse
    } def
/mswap { 8 -1 roll 8 -1 roll 8 -1 roll 8 -1 roll } def
/mdup { 3 index 3 index 3 index 3 index } def
% Function mm multiplies two 2x2 matrices represented as 4-element lists
/mm {1 index 7 index mul 8 index 5 index mul add
     1 index 9 -1 roll mul 4 index 10 -1 roll mul add
     4 -1 roll 6 index mul 7 index 7 -1 roll mul add
     4 -1 roll 6 -1 roll mul 5 -1 roll 6 -1 roll mul add
    } def
% Function f_print prints n'th Fibonacci number
/f_print {/Times-Roman findfont 20 scalefont setfont newpath 72 72 moveto
          dup 2 string cvs show (th Fibonacci number is ) show
          f 10 string cvs show showpage
         } def
% Entry point
45 f_print

ALGORITHM 3B: FAST RECURSION

% Function f returns n'th Fibonacci number
% It uses ALGORITHM 3B: FAST RECURSION
/f {l pop} def
/l { dup 1 le {pop 1 1} {
    dup 2 eq {pop 2 1} {
     dup 2 mod 1 eq {
      1 sub -1 bitshift l
      dup dup dup mul 4 -1 roll
      dup dup dup dup mul 5 -1 roll
      add exch 5 -1 roll add 3 -1 roll
      mul 4 -2 roll mul add exch
     } {
      -1 bitshift 1 sub l
      dup 3 -1 roll dup dup dup dup
      6 -1 roll add dup dup mul
      4 -2 roll mul add 5 -2 roll mul
      4 -2 roll mul add
     } ifelse
    } ifelse
   } ifelse
  } def
% Function f_print prints n'th Fibonacci number
/f_print {/Times-Roman findfont 20 scalefont setfont newpath 72 72 moveto
          dup 2 string cvs show (th Fibonacci number is ) show
          f 10 string cvs show showpage
         } def
% Entry point
45 f_print

ALGORITHM 3C: BINET'S FORMULA

% Function f returns n'th Fibonacci number
% It uses ALGORITHM 3C: BINET'S FORMULA
/f {1 add 5 sqrt dup 1 add 2 div 1 1 index sub
	3 index exp swap 4 -1 roll exp swap sub swap div
   } def
/swap {2 -1 roll} def
% Function f_print prints n'th Fibonacci number
/f_print {/Times-Roman findfont 20 scalefont setfont newpath 72 72 moveto
          dup 2 string cvs show (th Fibonacci number is ) show
          f 15 string cvs show showpage
         } def
% Entry point
45 f_print