# This program calculates the nth fibonacci number
# using alrogirhtm 1A: naive binary recursion
#
# compiled: N/A
# executed: awk -f f1a.awk n
#
# The BEGIN block in awk is the first thing to be executed
# This block prints out usage information if the wrong number of
# command-line arguments were supplied, or if the argument is a
# non-numeric string: for such strings, explicit string->number conversion
# (performed by adding zero in awk) turns them into zero.
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) prints the n'th Fibonacci number
function fib_print(n) {
    printf "%dth Fibonacci number is %d\n",n,f(n)
}
# Function f(n) handles the negative arguments: F(-n) = F(n)*(-1)^(n+1)
function f(n) {
    if(n<0)
        return n%2 ? fib(-n) : -fib(-n)
    else
        return fib(n)
}
# Naive binary recursion: F(n) = F(n-1) + F(n-2)
function fib(n) {
    return n<2 ? n : fib(n-1) + fib(n-2)
}

# 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]
}

# 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)
}

# 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
}

# 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]
}

# 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)
    }
}

# 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)
}