Faster Fibonacci

I was introduced with a challenge to make a function that calculates Fibonacci sequence in flutter and dart and a initial solution was given as a function for Fibonacci :

static int fib(int n) {
  if (n < 2) return n;
  return fib(n - 1) + fib(n - 2);
}

And i was supposed to make this more optimized

So I began to search for a way to optimize it. And of course there is no better way to do this than to

“Google it”

And there was quite good answers for start and the first try for this was this function:

int function(int n) {
    var fib = [0, 1];
    var data = [];
    for (int i = 2; i <= n; i++) {
      fib[i] = fib[i - 1] + fib[i - 2];
      data.add(fib[i]);
    }
    return data[data.length - 1];
  }

What this function does and how it works, is that it uses loops instead of the recursion solution that is presented in the given function above which faster in most ways due to many reasons for example loops in assembly looks like this:

mov loopcounter,i
dowork:/do work
dec loopcounter
jmp_if_not_zero dowork

Whilst the recursion looks like this:

start_subroutine:
pop parameter1
pop parameter2
dowork://dowork
test something
jmp_if_true done
push parameter1
push parameter2
call start_subroutine
done:ret

more about this in the answer in this link

Back to the subject…

Even though that solve most of the performance it was needed more improvements so the function was after a couple of tries became like this:

int function(int n) {
    if (n < 2) return n;
    var data = [0, 1];
    for (var i = 2; i < n + 1; i++) {
      data.add(data[i - 1] + data[i - 2]);
    }
    return data[data.length -1];
}

But despite the fact that is faster(a lot) there was space for improvement, and that is done through the equation of golden ration

Some Math Here

So the golden ratio is a unique mathematical relationship. Two numbers are in the golden ratio if the ratio of the sum of the numbers (a b) divided by the larger number (a) is equal to the ratio of the larger number divided by the smaller number (a/b).

In this case all the Fibonacci numbers.

So if you take any two Fibonacci numbers and done the operation above, the result will quite equal to 1.618…

And there is another way of getting the golden ratio and that is through an equation:

φ = 1/2 + √5/2

And if we used the golden ration equation to find a Fibonacci number the result will be much like this:

fibonacci = (1/2 + √5/2)^n / √5

n being the nth number in the Fibonacci sequence.

And frankly this solution is so fast that no other function or solution can compute with it

And coding it feels more satisfying than any other solution:

int function(int n) {
    return (pow(1.61803399, n) / sqrt(5)).round(); 
}

But…

It has a flaw
If the ratio was not accurate well… the answer also won’t

So if the ratio between 5 and 3 is 1.666666666666667

And the ratio between 317811 and 196418 is 1.618033988738303

So the number differs and if you go further in the calculations the result will also differs and it is noticeable in the higher numbers like 50 or 100.

So in conclusion…

If you want a very fast solution use the function with golden ratio

But if you want accurate and fast solution use the function with loops

References

10.4: Fibonacci Numbers and the Golden Ratio

Golden Ratio

Why are loops faster than recursion?

Fibonacci Sequence