cubbi.com: fibonacci numbers in awk

cubbi.com: fibonacci numbers in awk

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
Type: Imperative text-processing language
Usage: Text processing and general-purpose shell scripts in UNIX systems.
Note: These examples print the largest Fibonacci number which can be calculated correctly with GNU awk in each case. If you are using the One True awk from Brian Kernighan, change these examples to print out the 46th number.

ALGORITHM 1A: BINARY RECURSION

# The BEGIN block in awk is the first thing to be executed
BEGIN {
    f_print(77)
}
# Function f_print(n) prints the n'th Fibonacci number
function f_print(n) {
    printf "%dth Fibonacci number is %u\n",n,f(n)
}
# Function f(n) returns the n'th Fibonacci number
# It uses ALGORITHM 1A: BINARY RECURSION
function f(n) {
	return n<2 ? 1 : f(n-1)+f(n-2)
}

ALGORITHM 2A-3: DATA STRUCTURE - SIMPLE LIST

# The BEGIN block in awk is the first thing to be executed
BEGIN {
    fl[0]=fl[1]=1
    f_print(77)
}
# Function f_print(n) prints the n'th Fibonacci number
function f_print(n) {
    printf "%dth Fibonacci number is %u\n",n,f(n)
}
# Function f(n) returns the n'th Fibonacci number
# It uses ALGORITHM 2A-3: DATA STRUCTURE - SIMPLE LIST
function f(n) {
    if(fl[n]==0) fl[n]=f(n-1)+f(n-2)
    return fl[n]
}

ALGORITHM 2B: SIMPLE RECURSION

# The BEGIN block in awk is the first thing to be executed
BEGIN {
    f_print(77)
}
# Function f_print(n) prints the n'th Fibonacci number
function f_print(n) {
    printf "%dth Fibonacci number is %u\n",n,f(n)
}
# Function f(n) returns the n'th Fibonacci number
# It uses ALGORITHM 2B: SIMPLE RECURSION
function f(n) {
    return l(1,1,n)
}
# Function l(n1,n2,n) calculates f(n) using parameters n1 and n2
# to store the two previously calculated Fibonacci numbers
function l(n1,n2,n) {
    return n<2 ? n1 : l(n1+n2,n1,n-1)
}

ALGORITHM 2C: NON-RECURSIVE LOOP

# The BEGIN block in awk is the first thing to be executed
BEGIN {
    f_print(77)
}
# Function f_print(n) prints the n'th Fibonacci number
function f_print(n) {
    printf "%dth Fibonacci number is %u\n",n,f(n)
}
# Function f(n) returns the n'th Fibonacci number
# It uses ALGORITHM 2C: NON-RECURSIVE LOOP
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

# The BEGIN block in awk is the first thing to be executed
BEGIN {
    f_print(77)
}
# Function f_print(n) prints the n'th Fibonacci number
function f_print(n) {
    printf "%dth Fibonacci number is %u\n",n,f(n)
}
# Function f(n) returns the n'th Fibonacci number
# This function uses ALGORITHM 3A: MATRIX EQUATION
# Since awk does not allow function to return a matrix,
# traditional recursive matrix power had to be rewritten as
# a loop in this example.
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 multabb multiplies 2x2 matrices a and b and write the result to b
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 multaaa squares the 2x2 matrix a and writes the result to a
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

# The BEGIN block in awk is the first thing to be executed
BEGIN {
    f_print(77)
}
# Function f_print(n) prints the n'th Fibonacci number
function f_print(n) {
    printf "%dth Fibonacci number is %u\n",n,f(n)
}
# Function f(n) returns the n'th Fibonacci number
# It uses ALGORITHM 3B: FAST RECURSION
# Because in awk a function cannot return a pair of values,
# two functions are used: f, returning the first value and f2,
# returning the second.
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

# The BEGIN block in awk is the first thing to be executed
BEGIN {
    f_print(70)
}
# Function f_print(n) prints the n'th Fibonacci number
function f_print(n) {
     printf "%dth Fibonacci number is %u\n",n,f(n)
}
# Function f(n) returns the n'th Fibonacci number
# It uses ALGORITHM 3C: BINET'S FORMULA
function f(n) {
    if(n<2) return 1
    phi = (1+sqrt(5))/2
    return ( phi^(n+1) - (1-phi)^(n+1) ) / sqrt(5)
}