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: NAIVE BINARY RECURSION |
/fib {dup 1 gt
{1 sub dup 1 sub fib exch fib add
} if
} def
/f {dup 0 lt
{dup neg fib exch 2 mod 0 eq {neg} if}
{fib} ifelse
} def
/mycvs { dup dup 0 eq { pop 1 }
{ dup abs log 1 add exch 0 lt {1 add} if } ifelse
cvi string cvs
} def
/main {
dup mycvs print
(th Fibonacci number is ) print
f mycvs print (\n) print
} def
|
ALGORITHM 1B: CACHED BINARY RECURSION / MEMOIZATION |
/mfib { 2 copy known
{ get }
{ 1 sub 2 copy 1 sub mfib 3 1 roll mfib add } ifelse
} def
/fib { << 0 0 1 1 >> exch mfib } def
/f {dup 0 lt
{dup neg fib exch 2 mod 0 eq {neg} if}
{fib} ifelse
} def
/mycvs { dup dup 0 eq { pop 1 }
{ dup abs log 1 add exch 0 lt {1 add} if } ifelse
cvi string cvs
} def
/main {
dup mycvs print
(th Fibonacci number is ) print
f mycvs print (\n) print
} def
|
ALGORITHM 2A: CACHED LINEAR RECURSION / RANDOM-ACCESS CONTAINER |
/fibrec {counttomark dup 2 add index gt
{counttomark 2 add 1 roll cleartomark pop }
{2 copy add fibrec } ifelse
} def
/fib { mark 0 1 fibrec } def
/f {dup 0 lt
{dup neg fib exch 2 mod 0 eq {neg} if}
{fib} ifelse
} def
/mycvs { dup dup 0 eq { pop 1 }
{ dup abs log 1 add exch 0 lt {1 add} if } ifelse
cvi string cvs
} def
/main {
dup mycvs print
(th Fibonacci number is ) print
f mycvs print (\n) print
} def
|
ALGORITHM 2B: LINEAR RECURSION WITH ACCUMULATORS |
/fibrec {
3 2 roll 1 sub dup 1 le
{ pop add }
{ 3 1 roll exch 1 index add fibrec } ifelse
} def
/fib { 0 1 fibrec } def
/f {dup 0 lt
{dup neg fib exch 2 mod 0 eq {neg} if}
{fib} ifelse
} def
/mycvs { dup dup 0 eq { pop 1 }
{ dup abs log 1 add exch 0 lt {1 add} if } ifelse
cvi string cvs
} def
/main {
dup mycvs print
(th Fibonacci number is ) print
f mycvs print (\n) print
} def
|
ALGORITHM 2C: IMPERATIVE LOOP WITH MUTABLE VARIABLES |
/fib {dup 1 gt { 1 sub 0 exch 1 exch
{ dup 3 2 roll add } repeat exch pop
} if
} def
/f {dup 0 lt
{dup neg fib exch 2 mod 0 eq {neg} if}
{fib} ifelse
} def
/mycvs { dup dup 0 eq { pop 1 }
{ dup abs log 1 add exch 0 lt {1 add} if } ifelse
cvi string cvs
} def
/main {
dup mycvs print
(th Fibonacci number is ) print
f mycvs print (\n) print
} def
|
ALGORITHM 3A: MATRIX MULTIPLICATION |
/dup-mat { dup matrix copy } def
/matrix-power {
dup 1 gt { exch dup-mat
2 index 2 idiv matrix-power
dup-mat matrix concatmatrix
3 2 roll 2 mod 1 eq { matrix concatmatrix }
{ exch pop }ifelse
} { pop } ifelse
} def
/fib { dup 0 gt
{ [ 1 1 1 0 0 0 ] exch 1 sub matrix-power 0 get cvi } if
} def
/f {dup 0 lt
{dup neg fib exch 2 mod 0 eq {neg} if}
{fib} ifelse
} def
/mycvs { dup dup 0 eq { pop 1 }
{ dup abs log 1 add exch 0 lt {1 add} if } ifelse
cvi string cvs
} def
/main {
dup mycvs print
(th Fibonacci number is ) print
f mycvs print (\n) print
} def
|
ALGORITHM 3B: FAST RECURSION |
/fib { fib-rec exch pop } def
/fib-rec {
dup 0 le {pop 0 0} {
dup 1 eq {pop 0 1} {
dup 2 mod exch 2 idiv fib-rec
2 copy add 4 3 roll
1 eq { dup 4 3 roll add 2 index mul
3 1 roll dup mul exch dup mul add }
{ exch dup 3 index 4 3 roll add mul
3 1 roll dup mul exch dup mul add exch } ifelse
} ifelse
} ifelse
} def
/f {dup 0 lt
{dup neg fib exch 2 mod 0 eq {neg} if}
{fib} ifelse
} def
/mycvs { dup dup 0 eq { pop 1 }
{ dup abs log 1 add exch 0 lt {1 add} if } ifelse
cvi string cvs
} def
/main {
dup mycvs print
(th Fibonacci number is ) print
f mycvs print (\n) print
} def
|
ALGORITHM 3C: BINET'S FORMULA WITH ROUNDING |
/fib { 5 sqrt dup 1 add 2 div 3 2 roll
exp exch div round cvi
} def
/f {dup 0 lt
{dup neg fib exch 2 mod 0 eq {neg} if}
{fib} ifelse
} def
/mycvs { dup dup 0 eq { pop 1 }
{ dup abs log 1 add exch 0 lt {1 add} if } ifelse
cvi string cvs
} def
/main {
dup mycvs print
(th Fibonacci number is ) print
f mycvs print (\n) print
} def
|
|