#!/bin/bash

# This program calculates the nth fibonacci number
#  using alrogirhtm 1A: naive binary recursion
#
# compiled: N/A
# executed: ./f1a.sh n
#

# Naive binary recursion: F(n) = F(n-1) + F(n-2)
fib () {
  if test $1 -lt 2; then
    echo $1
  else
    echo $(($(fib $(($1-2)))+$(fib $(($1-1)))))
  fi
}

# f handles the negative arguments: F(-n) = F(n)*(-1)^(n+1)
f () {
  if test $1 -lt 0; then
     if test $(($1%2)) -eq 0; then
         echo $((0-$(fib $((0-$1)))))
     else
         echo $(fib $((0-$1)))
     fi
  else
     echo $(fib $1)
  fi
}
# Function main checks the number of command line arguments, calls f()
# and prints the results
main () {
  if [ "$#" -ne 1 ]; then
      echo "Usage: $0 <n>"
  else
     RET=$(f $1)
     echo $1 "th Fibonacci number is" $RET
  fi
}
# entry point
main $1

#!/usr/local/bin/zsh
# Function f calculates n'th Fibonacci number
# It uses ALGORITHM 2A-3: DATA STRUCTURE - SIMPLE LIST
f () {
  eval A='$'F$1
  if test x$A != x; then
    return $A
  else
    eval A='$'F$(($FL-1))
    eval B='$'F$(($FL))
    FL=$(($FL+1))
    eval F$FL=$(($A+$B))
    f $1
  fi
}
F0=1
F1=1
FL=1
# Function f_print prints out n'th Fibonacci number
f_print () {
  f $1
  echo $1 "th Fibonacci number is" $?
}
f_print 45

#!/usr/local/bin/zsh
# Function f calculates n'th Fibonacci number
# It uses ALGORITHM 2B: SIMPLE RECURSION
f () {
  if test $1 -le 1; then
    return $2
  else
    f $(($1-1)) $(($2+$3)) $2
  fi
}
# Function f_print prints out n'th Fibonacci number
f_print () {
  f $1 1 1
  echo $1 "th Fibonacci number is" $?
}
f_print 45

#!/usr/local/bin/zsh
# Function f calculates n'th Fibonacci number
# It uses ALGORITHM 2C: NON-RECURSIVE LOOP
f () {
  N1=1
  N2=1
  I=1
  while test $I -lt $1; do
    I=$(($I+1))
    TMP=$(($N1+$N2))
    N2=$N1
    N1=$TMP
  done
  return $N1
}
# Function f_print prints out n'th Fibonacci number
f_print () {
  f $1
  echo $1 "th Fibonacci number is" $?
}
f_print 45

#!/usr/local/bin/zsh
# Function f calculates n'th Fibonacci number
# It uses ALGORITHM 3A: MATRIX EQUATION

# Since sh does not allow function to return a matrix,
# traditional recursive matrix power had to be rewritten as
# a loop in this example.   
f () {
 A11=2; A12=1; A21=1; A22=1
 B11=1; B12=0; B21=0; B22=1
 NH=$(($1/2))
 BIT=1
 if test $(($BIT & $NH)) -ne 0; then
   B11=$A11; B12=$A12; B21=$A21; B22=$A22
 fi
 while test $BIT -lt $NH; do
   BIT=$((2*$BIT))
   mmultaaa
   if test $(($BIT & $NH)) -ne 0; then
     mmultabb
   fi
 done
 if test $(($1%2)) -ne 0; then
  return $(($B11+$B12))
 else
  return $B11
 fi
}
mmultaaa () {
 C11=$(($A12*$A21+$A11*$A11))
 C12=$(($A11*$A12+$A12*$A22))
 C21=$(($A21*$A11+$A22*$A21))
 C22=$(($A21*$A12+$A22*$A22))
 A11=$C11; A12=$C12; A21=$C21; A22=$C22
}
mmultabb () {
 C11=$(($A12*$B21+$A11*$B11))
 C12=$(($A11*$B12+$A12*$B22))
 C21=$(($A21*$B11+$A22*$B21))
 C22=$(($A21*$B12+$B22*$A22))
 B11=$C11; B12=$C12; B21=$C21; B22=$C22
}
# Function f_print prints out n'th Fibonacci number
f_print () {
  f $1
  echo $1 "th Fibonacci number is" $?
}
f_print 45

#!/usr/local/bin/zsh
# Function f calculates n'th Fibonacci number
# It uses ALGORITHM 3B: FAST RECURSION
f () {
  if test $1 -lt 2; then
    return 1
  elif test $1 -eq 2; then
    return 2
  elif test $(($1%2)) -eq 1; then
    return $(($(f $((($1-1)/2));echo $?)*($(f $((($1-1)/2));echo $?)
           +2*$(l $((($1-1)/2));echo $?))))
  else
    return $((($(f $(($1/2-1));echo $?)+$(l $(($1/2-1));echo $?))
            *($(f $(($1/2-1));echo $?)+$(l $(($1/2-1));echo $?))
            +$(f $(($1/2-1));echo $?)*$(f $(($1/2-1));echo $?)))
  fi
}
l () {
  if test $1 -le 2; then
    return 1
  elif test $(($1%2)) -eq 1; then
    return $(($(f $((($1-1)/2));echo $?)*$(f $((($1-1)/2));echo $?)
            +$(l $((($1-1)/2));echo $?)*$(l $((($1-1)/2));echo $?)))
  else
    return $(($(f $(($1/2-1));echo $?)*($(f $(($1/2-1));echo $?)
           +2*$(l $(($1/2-1));echo $?))))
  fi
}
# Function f_print prints out n'th Fibonacci number
f_print () {
  f $1
  echo $1 "th Fibonacci number is" $?
}
f_print 45

#!/usr/local/bin/zsh
# Function f calculates n'th Fibonacci number
# It uses ALGORITHM 3C: BINET'S FORMULA
f () {
  N=$((1+$1))
  S5=2.2360679775
  PHI=$(( (1+S5)/2 ))
  PHI2=$((1-PHI))
  return $(( ($PHI ** $N - $PHI2 ** $N)/$S5 ))
}
# Function f_print prints out n'th Fibonacci number
f_print () {
  f $1
  echo $1 "th Fibonacci number is" $?
}
f_print 45