Fibonacci Sequence - Faster method?

Question

Just decided to make a quickie Fibonacci Sequence via jQuery and I was wondering if anybody can think of a faster way to interpret it? I can type pretty much any number in and it returns in a fraction of a second.

Can anybody think of a quicker method to calculate a specific Fibonacci number?

http://jsfiddle.net/st9sgrcx/1/

$(function(){
	var counter = 1,
 fibo = [0,1],
 temp = 0,
 whichOne = prompt("Which fibonnaci number do you want?");
 function fib(prev, cur){
 temp = prev + cur;
 fibo.push(temp);
 counter = temp;
 temp = cur;
 }
 for(var i=0; i<whichOne; i++){
 fib(temp, counter);
 }
 alert(temp);
});

<script src="https://ajax.googleapis.com/ajax/libs/jquery/1.9.1/jquery.min.js"></script>

• Nicholas Hazel: I suppose I could ignore the array and just keep the current and temp numbers as a suggestion?

Answer 1

"fibonnaci" is a misspelling.

There really isn't any need for jQuery here.

As you have already observed, there is also no need to keep the entire array, unless you wanted to modify the code to reuse the memoized results for multiple calculations.

If you want the fastest way to calculate a specific Fibonacci number, even when the number is large, then go for the closed-form formula instead:

$$ F_n = \frac{\phi^n - \psi^n}{\sqrt{5}} $$ ... where \$\phi = \dfrac{1 + \sqrt{5}}{2}\$ and \$\psi = \dfrac{1 - \sqrt{5}}{2}\$.

• Dair: I would, in some cases, recommend raising ((1 1) (1 0))^n to get the nth fib. sqrt(5) needs more and more precision as F_n gets larger, and therefore it is more computationally expensive to calculate sqrt(5) at those sizes of F_n.