euler.sh

#!/bin/bash
# this is a fun little script to compute euler's number using bash.
# It attempts to produce n digits of e when invoked as: ./euler.sh n
# There's a well known taylor series for approximating e:
# e = sum from 1 to infinity of 1/n!
# unfortunately bash doesn't support fractions, just integers.
# so we basically fake a rational number data structure, storing the numerator
# and denominator as integers. At that point we have to deal with the fact
# that bash integers are finite precision, so large numerator and large denominators
# overflow very fast. We constantly have to reduce the fraction to shrink the numerator
# and denominator. I use euclid's method for finding the gcd because it's extremely efficient.
# this script gives you about 9 digits max.

function numerator() {
    local __resultvar=$1
    local fraction=$2
    if [[ $fraction =~ (.*)/.* ]] ; then
        eval $__resultvar="'${BASH_REMATCH[1]}'"
    fi
}
function denominator() {
    local __resultvar=$1
    local fraction=$2
    if [[ $fraction =~ .*/(.*) ]] ; then
        eval $__resultvar="'${BASH_REMATCH[1]}'"
    fi
}
function multiply() {
    local __resultvar=$1
    local fraction1=$2
    local fraction2=$3
    local n
    local d
    numerator a $fraction1
    denominator b $fraction1
    numerator c $fraction2
    denominator d $fraction2
    let "n=a*c"
    let "d=b*d"
    eval $__resultvar="$n/$d"

}
function sum() {
    local __resultvar=$1
    local fraction1=$2
    local fraction2=$3

    #a/b+c/d is
    #(ad+bc)/bd
    numerator a $fraction1
    denominator b $fraction1
    numerator c $fraction2
    denominator d $fraction2
    let "sum_n=a*d+b*c"
    let "sum_d=b*d"
    eval $__resultvar="$sum_n/$sum_d"

}
function to_dec {
    local __resultvar=$1
    local r
    local accum
    numerator n $2
    denominator d $2
    let r=n/d
    let n=n-r*d
    let n=n*10
    let precision=0
    accum="${r}."
    while [[ $precision -lt 12 ]];do
        let r=n/d
        let n=n-r*d
        accum="${accum}${r}"
        let n=n*10
        let precision=precision+1
    done
    
    eval $__resultvar="$accum"

}
common_prefix() {
  local n=0
  while [[ "${1:n:1}" == "${2:n:1}" ]]; do
    ((n++))
  done
  echo $n
}

function euler() {
    local accum=1/1
    local term=1/1
    local numer
    local denom
    local result
    local new_result
    for n in $(seq 1 13);do
        multiply term $term 1/$n
        sum accum $accum $term
        #reduce
        numerator numer $accum
        denominator denom $accum
        gcd common $numer $denom
        let numer=numer/common
        let denom=denom/common
        accum=$numer/$denom
        to_dec new_result $accum
        if [[ $(common_prefix $new_result $result) -ge $(($1+2)) ]]; then
            echo $result
            return
        fi
        result=$new_result
    done
    echo "Couldn't get that many digits. Sorry"
}
function gcd() {
    local __resultvar=$1    

    local tmp
    local num1=$2
    local num2=$3
    while [[ $num1 -gt 0 ]];do
        let "tmp=num1"
        let "num1=num2%num1"
        let "num2=tmp"    
    done
    eval $__resultvar="$num2"
    
}
euler $1