# 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