Fibonacci in Solidity

“We’ll ride the spiral to the end and may just go where no one’s been.” — Tool, Lateralus

While browsing hacker news this morning I saw a post that benchmarks the top 10 most used languages in Github returning the nth element in the Fibonacci sequence. Solidity isn’t a very popular language yet, so I thought I would explore a few solutions and see how it compares.

Mathematically, the Fibonacci sequence is a recursive function that adds the previous elements to obtain the next element. Like this:

Fn = Fn-1 + Fn-2

Recursion

The naive approach is to use recursion, like this:

//fib(4) = 15540 gas 
//fib(42) = no go
function fib(uint n) public view returns(uint) { 
    if (n <= 1) {
       return n;
    } else {
       return this.fib(n - 1) + this.fib(n - 2);
    }
}

Unfortunately, recursion is out of the question. I’m sure it can be made to work in a pinch, but remix hangs while running fib(42) and even fib(4) consumes ~15k gas.

Memoisation

For my second approach, I decided to use a memoisation technique and store the sequence in a memory array, returning the nth element as expected.

//fib1(4) = 1593 gas
//fib1(42) = 12237 gas 
//fib1(1042) = no-go...
function fib1(uint n) external pure returns(uint) { 
    uint[] memory sequence = new uint[](n+1);
    for (uint i = 0; i <= n; i++) {
        if (i <= 1) {
            sequence[i] = i;
        } else {
            sequence[i] = sequence[i -1] + sequence[i -2];    
        }
    }
    return sequence[n];
}

It was a bit better, now fib1(42) actually returns correctly but asking for fib1(1042) again results in remix hanging. That’s not good, and really the problem doesn’t require us to keep the whole sequence in memory at all.

Iteration

A better approach is needed, so I changed the algorithm to only store three variables in memory and iterate n times until I find the nth element in the sequence, like this:

//fib2(4) =  363 gas
//fib2(42) = 2757 gas 
//fib2(1042) = 65757 gas
function fib2(uint n) external pure returns(uint b) { 
    if (n == 0) {
        return 0;   
    }
    uint a = 1;
    b = 1;
    for (uint i = 2; i < n; i++) {
        uint c = a + b;
        a = b;
        b = c;
    }
    return b;
}

That works. The function still requires a considerable amount of gas for fib2(1042) but the original challenge has much lower requirements.

Normally I would be happy with the results and move on to some actual work but I was concerned that there would be nothing to write about and I had already spent 1h of my morning looking into this challenge.

Binet’s formula (equivalent)

I knew that Binet’s formula would be hard to implement in Solidity but I figured that if I could find an implementation in C, I would be able to translate it… and what would you know, I found one here.

//fib2(4) =  796 gas
//fib3(42) = 1399 gas  
//fib3(1042) = 2414 gas
function fib3(uint n) external pure returns(uint a) { 
    if (n == 0) {
        return 0;   
    }
    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;
}

For fun, I ran fib3(1026281039383259811539107) and it only took ~16k gas. Now that looks good!

Get Best Software Deals Directly In Your Inbox