12+ ways to Fibonacci

#javascript #solidity #computerscience

This morning I came across a great little paper showing twelve algorithms to compute Fibonacci numbers in Python. I had to share!

Calculating fibonacci numbers recursively is used to benchmark computer languages and sometimes by interviewers trying to impress job seekers. More importantly, it inspired one of the greatest songs ever so it's worth remembering a few of these algorithms and spiral out :o)

Not to repeat the python examples from the paper, let's instead look at four ways to compute the fibonacci number of N in Javascript.

//ES6

// using recursion
const fibonacci = n => n <= 2 ? 1 : fibonacci(n - 1) + fibonacci(n - 2);

// using cache
const fibCached = (n, cache = {1: 1, 2: 1}) => cache[n] ? cache[n] : cache[n] = fibCached(n - 1, cache) + fibCached(n - 2, cache);

// using tail recursion
const fibTailRecursed = (n, sum = 1, prev = 1) => n <= 2 ? sum : fibTailRecursed(n - 1, sum + prev, sum);

// using Binet's formula
const fibBinet = n => Math.floor( (((1 + Math.sqrt(5)) / 2 ) ** n) / Math.sqrt(5) + 0.5);

This very interesting formula discovered by Binet had caught my eye a few years ago when I found out it could be used in Solidity smart contracts.

The Ethereum Virtual Machine is a resource constrained environment where every operation is metered and payed for, which discourages using recursion or iteration, but understanding it in depth does make one a better programmer imho.

//Solidity v0.5+

function fibBinet(uint n) external pure returns(uint a) { 
    if (n <= 2) return 1;   

    uint h = n / 2; 
    uint mask = 1;

    // find highest set bit in n
    while(mask <= h) mask <<= 1;

    mask >>= 1;
    a = 1;
    uint b = 1;
    uint c;

    while(mask > 0) {
        c = a * a + b * b;          
        if (n & mask > 0) {
            b = b * (b + 2 * a);  
            a = c;                
        } else {
            a = a * (2 * b - a);  
            b = c;                
        }
        mask >>= 1;
    }
    return a;
}