Monday, January 19, 2015

Recursive Fibonacci function in Bash

Or why you better not use recursion is Bash

First, the loop version:

function fib() {
    declare -l cur=0 next=1 final=$(($1-1)) tcur

    for ((i=0; i<final; i++)); do
        tcur=$cur
        cur=$next
        next=$((tcur+next))
    done
    rval=$cur
}

And now the recursive version. I've added caching of previously calculated values to help with performance:

unset fib_cache; declare -ia fib_cache
function fib() {
    declare -li n=$1 n_1 n_2 l

    l=${#fib_cache[*]}
    if ((n<=l)); then
        rval=${fib_cache[$n]}
        return
    fi

    if ((n<3)); then
        rval=$((n-1))
        fib_cache[$n]=$rval
        return
    fi

    fib $((n-2))
    n_2=$rval
    fib $((n-1))
    n_1=$rval

    rval=$((n_2 + n_1))
    fib_cache[$n]=$rval
    return
}

Performance

Lets test how fast Bash can crunk Fibonacci on my laptop. Here is the test script:
for i in $(seq 1000); do
    unset fib_cache; declare -ia fib_cache
    fib 93
done
I've used fib 93 - its a max Fibonacci sequence number you can store in Bash arithmetic variable before getting overflow.

I've run it 10 times and measured average time:

  • Loop version: Runs 1.19 seconds on average. I.e. it takes 1.19 seconds to calculate fib 93 thousand  times. How fast is that? Well, similar C code, compiled with -O3 runs this task in 0.0001 seconds. About 10,000 faster
  • Recursion version: Runs 10.41 seconds on average. Times 10 slower. And this is with cache. Without cache it did not complete in 15 minutes and I gave up

Conclusion

Think twice before considering recursive functions in Bash.

1 comment:

  1. Depending in your particular circumstances, you need to|you should|you have to} decide what degree of privateness you want and then decide the jurisdiction that can supply it. SustainabilityNot every jurisdiction is suited to every sort of business. While some supply gambling licenses, they may not have a great technique in place, or sufficient privateness rules, or even suitable frameworks for asset management. Some that appear to tick the right company 카지노 사이트 boxes, in turn, in all probability not|will not be} good for online gambling.

    ReplyDelete