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
|
awk
Date: 1978 (standardized in POSIX 1003.1)
Type: Imperative text-processing language
Usage: Text processing and general-purpose shell scripts in UNIX systems.
ALGORITHM 1A: NAIVE BINARY RECURSION |
BEGIN {
if(ARGC==2 && 0+ARGV[1]!=0 || ARGV[1]=="0")
fib_print(ARGV[1])
else
print "Usage: awk -f f1a.awk <n>"
}
function fib_print(n) {
printf "%dth Fibonacci number is %d\n",n,f(n)
}
function f(n) {
if(n<0)
return n%2 ? fib(-n) : -fib(-n)
else
return fib(n)
}
function fib(n) {
return n<2 ? n : fib(n-1) + fib(n-2)
}
|
ALGORITHM 2A-3: DATA STRUCTURE - SIMPLE LIST |
BEGIN {
fl[0]=fl[1]=1
f_print(77)
}
function f_print(n) {
printf "%dth Fibonacci number is %u\n",n,f(n)
}
function f(n) {
if(fl[n]==0) fl[n]=f(n-1)+f(n-2)
return fl[n]
}
|
ALGORITHM 2B: SIMPLE RECURSION |
BEGIN {
f_print(77)
}
function f_print(n) {
printf "%dth Fibonacci number is %u\n",n,f(n)
}
function f(n) {
return l(1,1,n)
}
function l(n1,n2,n) {
return n<2 ? n1 : l(n1+n2,n1,n-1)
}
|
ALGORITHM 2C: NON-RECURSIVE LOOP |
BEGIN {
f_print(77)
}
function f_print(n) {
printf "%dth Fibonacci number is %u\n",n,f(n)
}
function f(n) {
n1=n2=1
for(i=1;i<=n;i++) {
tmp=n1+n2
n1=n2
n2=tmp
}
return n1
}
|
ALGORITHM 3A: MATRIX EQUATION |
BEGIN {
f_print(77)
}
function f_print(n) {
printf "%dth Fibonacci number is %u\n",n,f(n)
}
function f(n) {
a[1]=2; a[2]=1; a[3]=1; a[4]=1
b[1]=1; b[2]=0; b[3]=0; b[4]=1
nh=int(n/2)
if (nh%2) for(i in a) b[i]=a[i]
while(0 < nh) {
mmultaaa()
nh=int(nh/2)
if(nh%2 == 1) mmultabb()
}
if(n%2) return b[1]+b[2]
else return b[1]
}
function mmultabb() {
c[1]=a[1]*b[1]+a[2]*b[3]
c[2]=a[1]*b[2]+a[2]*b[4]
c[3]=a[3]*b[1]+a[4]*b[3]
c[4]=a[3]*b[2]+a[4]*b[4]
for(i in c) b[i]=c[i]
}
function mmultaaa() {
c[1]=a[1]*a[1]+a[2]^2
c[2]=a[1]*a[2]+a[2]*a[4]
c[3]=a[3]*a[1]+a[4]*a[3]
c[4]=a[3]*a[2]+a[4]^2
for(i in c) a[i]=c[i]
}
|
ALGORITHM 3B: FAST RECURSION |
BEGIN {
f_print(77)
}
function f_print(n) {
printf "%dth Fibonacci number is %u\n",n,f(n)
}
function f(n,k1,k2) {
if(n<2) return 1
if(n==2) return 2
if((n%2)==1) {
k1=f((n-1)/2)
k2=f2((n-1)/2)
return k1*(k1+2*k2)
} else {
k1=f((n/2)-1)
k2=f2((n/2)-1)
return (k1+k2)^2 + k1^2
}
}
function f2(n,k1,k2) {
if(n<=2) return 1
if((n%2)==1) {
k1=f((n-1)/2)
k2=f2((n-1)/2)
return k1^2 + k2^2
} else {
k1=f((n/2)-1)
k2=f2((n/2)-1)
return k1*(k1+2*k2)
}
}
|
ALGORITHM 3C: BINET'S FORMULA |
BEGIN {
f_print(70)
}
function f_print(n) {
printf "%dth Fibonacci number is %u\n",n,f(n)
}
function f(n) {
if(n<2) return 1
phi = (1+sqrt(5))/2
return ( phi^(n+1) - (1-phi)^(n+1) ) / sqrt(5)
}
|
|