Fibonacci at the interview

The calculation of the Fibonacci series is a classical algorithmic problem, because it is often given at interviews when they want to verify that the candidate in principle can at least somehow know how to use algorithms. Suppose you are the same candidate. You have been given a task: in JavaScript, write the function fib(n) , which returns an unlimited Fibonacci number. We assume that the zero Fibonacci number is zero. Validation of the argument is not required. What options do you have?

1. To be easier, and people will reach for you.

The simplest solution is a banal loop.

 const fib = n => { let prev = 0, next = 1; while(n-- && (next = prev + (prev = next))); return prev; } 

Joke. Of course, you don’t need to write like that - unless, of course, you are not interviewed for the position of a regular obfuscator.
')

 const fib = n => { let prev = 0, next = 1; for(let i = 0; i < n; i++){ next = prev + next; prev = next - prev; } return prev; } 

Do you run out of coupons for variables? cypok

Okay, okay, for even more readability we will write this:

 const fib = n => { let prev = 0, next = 1; for(let i = 0; i < n; i++){ let temp = next; next = prev + next; prev = temp; } return prev; } 

This is a classic, simple and elegant version. But perhaps you want to demonstrate your knowledge of some other concepts? For example…

2. To understand recursion, you need to understand recursion.

For example, yes, you can demonstrate that you are able to recursion. For example:

 const fib = n => { if(n <= 1){ return n; }else{ return fib(n - 1) + fib(n - 2); } } 

Remember this option. So do not. It does not follow. It is impossible. Never. This is worse than kicking puppies, and is comparable to a small holocaust.

You may ask why. In this case, simply run this code and try to calculate, say, the fiftieth Fibonacci number. I guess you will feel some kind of delay. Joke. I suppose if you run this code not on a supercomputer, then simply do not wait for the result. Given that the simple, non-recursive code from the previous examples will calculate the fiftieth member of the Fibonacci sequence faster than you can say the word "fifty" or any syllable.

In the crude language of the O-notation, this solution has the time complexity O (e ⁿ ). That is, the execution time of this function grows exponentially with increasing n. That is, when n is increased by , the execution time is increased in . Roughly speaking, if fib(45) you had to wait an hour, then fib(46) you will wait two hours, fib(47) - 4 hours, and so on. I chew in such detail that every reader, even the coder, who first tried his hand at writing scripts, could realize the horror of the situation.

This is correct, but too rude. You can get a more accurate estimate of the number of the function call ~ (1 + sqrt (5)) fib (n) and the nice remark “To calculate the Fibonnachin number by the recurrent method, you need function calls 3.2 times larger than the Fibonnachi number itself”. Taus

And we get another method to calculate it. You just need to run the naive recursive method, count the number of function calls and divide by 3.2! Cerberuser

If you are required to have a recursive solution to this task at your interview, this is most likely a trap. “Correct” recursion that works in linear time may look like this:

 const fib2 = n => { if(n == 0){ return [0, 1]; }else{ const [prev, next] = fib2(n - 1); return [next, prev + next]; } } const fib = n => fib2(n)[0]; 

Summing up: despite the fact that the Fibonacci numbers are a classic, textbook example of recursion, in reality this is not the most convenient case for applying recursion. But you can try to flash some more knowledge.

3. Memo function

There is a magical way of turning a monstrously inefficient solution from the last paragraph into a potentially very fast (although not without problems). His name is memoization. And if to speak in Russian - we just remember the results of previous calls instead of re-calculating them.

In principle, we can even change nothing inside that solution - just add the wrapper function memoize . Here, for clarity, I use its simplified version for a function with a single argument.

 //   ,       ,     const oldFib = n => { if(n <= 1){ return n; }else{ return oldFib(n - 1) + oldFib(n - 2); } } const memoize = f => { const cache = {}; return arg => cache[arg] || (cache[arg] = f(arg)); } const fib = memoize(oldFib); 

Voila! Now the fib function has access to the cache object through the closure. If it is called with an argument that was not previously encountered, the calculated value is stored in the cache . With new function calls with the same argument, the value will not have to be recalculated, it will just be taken from the cache. The main problem with the “bad” old function of fib was that the same values ​​in it were re-evaluated several times. For example, to calculate fib(45) it was necessary to calculate f(44) once, f(43) twice, f(42) three times, f(42) five times, and so on.


So, now the previous values ​​will be calculated once, and when they are re-requested - just taken from the cache. Can you imagine how many times faster we can now calculate the forty-fifth Fibonacci number? Seriously, what do you think, what time?

In fact - a little slower. I deliberately made a classic mistake, often made during memoization of recursive functions. When calling fib(45) “under the hood”, oldFib(45) is called, which for its needs causes oldFib(44) and oldFib(43) ... Do you feel the catch? Hereinafter there are already calls to the usual, non-memosized function. Of course, when you call fib(45) again, we instantly get the result from the cache — however, the first call did not accelerate at all. To fix this, you still have to get oldFib under the bottom with a wrench:

 const oldFib = n => { if(n <= 1){ return n; }else{ return fib(n - 1) + fib(n - 2); } } const memoize = f => { const cache = {}; return arg => cache[arg] || (cache[arg] = f(arg)); } const fib = memoize(oldFib); 

Wonderful! Now the first call to fib(45) run at a speed comparable to the loop version. And further calls in general will work for a constant time ... Oops! Again deceived. Obtaining the value of an object's property by key is an operation that is fast, but still O (1) is only on average, in the worst case, it can degrade to O (n). To make it quite good, in our case, we can change the type of cache from an object to an array.

Of course, one should not forget that memoryization requires memory. And while we reduce the time complexity, the memory complexity increases from O (1) to O (n).

How else can we show off? For example, by demonstrating your deep knowledge of mathematics

4. Mr Binet

There is a special excellent science about how to turn recurrence relations into explicit formulas. Here we will not go into its details. Let us just say that for Fibonacci numbers with the help of fairly simple reasoning, we can derive the following formula, known as the Binet formula:

$$

$$F_n = \ frac {\ left (\ frac {1 + \ sqrt5} {2} \ right) ^ n - \ left (\ frac {1 - \ sqrt5} {2} \ right) ^ n} {\ sqrt5}$$

However, quite the language of mathematics, we write this in JavaScript:

 const fib = n => { const a = (1 + 5 ** 0.5) / 2; const b = (1 - 5 ** 0.5) / 2; return (a ** n - b ** n) / 5 ** 0.5; } 

Drive on the first few numbers. Remarkably, everything seems to work. Here are 13, here 21, here 34, here ... 54.99999999999999?

Yes, of course, this result is logical. Binet's formula is mathematically exact, but the computer operates on fractions of finite precision, and an error can accumulate during operations on them, which is what happened in this case. However, we can fix it. Knowing that the deductible in the numerator will always be small in absolute value, we can simplify the formula to the following state:

$$

$$F_n = \ left \ lfloor \ frac {\ left (\ frac {1 + \ sqrt5} {2} \ right) ^ n} {\ sqrt5} \ right \ rceil$$

Here, strange unfinished square brackets mean the nearest integer, that is, rounding. Rewrite our code:

 const fib = n => { const a = (1 + 5 ** 0.5) / 2; return Math.round(a ** n / 5 ** 0.5); } 

Yes, so much better. We can see both 55 and 89, and even my favorite Fibonacci number is 144 (which I love for being equal to twelve in a square). Everything will be fine until the number behind number 76. Which should be equal to 3416454622906707, and our function will calculate 3416454622906706. Because the problem of limited precision of fractional numbers has not disappeared, we simply pushed it deeper and hoped that it would not pop up. As this example shows, they hoped in vain.

In fact, we can do something else to save this method. But more on that below. For now - jokes aside. Let's talk about the method of harsh, hardcore and brutal.

5. Follow the white rabbit.

They say that if you have a problem and the idea occurred to you that you can solve it with regular expressions, now you have two problems. Matrices are regular expressions in reverse. Many problems, if they are reformulated in the language of matrices, are solved simply by themselves.

As for the Fibonacci numbers, for them in the matrix language we can write this obvious identity:

$$

$$\ begin {pmatrix} 0 & 1 \\ 1 & 1 \ end {pmatrix} \ begin {pmatrix} F_ {n - 1} \\ F_n \ end {pmatrix} = \ begin {pmatrix} F_n \\ F_ {n +1} \ end {pmatrix}$$

That is, if you take a couple of Fibonacci numbers in a row and multiply them by such a straightforward matrix, we get the next pair. And from here the conclusion follows logically: if we take a pair of zero and first Fibonacci numbers, that is, zero and ones, and multiply them by this matrix to the nth power, we get a pair of nth and en plus Fibonacci numbers. That is, speaking humanly:

$$

$$\ begin {pmatrix} 0 & 1 \\ 1 & 1 \ end {pmatrix} ^ n \ begin {pmatrix} 0 \\ 1 \ end {pmatrix} = \ begin {pmatrix} F_n \\ F_ {n + 1} \ end {pmatrix}$$

You can simplify this a bit more by dropping vectors. In fact, all the necessary values ​​are contained in the matrix itself:

$$

$$\ begin {pmatrix} 0 & 1 \\ 1 & 1 \ end {pmatrix} ^ n = \ begin {pmatrix} F_ {n-1} & F_ {n} \\ F_ {n} & F_ {n + 1 } \ end {pmatrix}$$

Great, isn't it? It remains to understand, what for the ass harmony, if he is not a philharmonic. In the sense - why such difficulties on an even place. And the answer is simple - quick exponentiation.

How many elementary multiplications need to be done to calculate, say, 2 ¹⁰ ? A normal person will say nine. Two by two is four. Twice four - eight. Twice eight is sixteen. And so on. A cunning person will say four.

$$

$$2 \ cdot 2 = 4 \\ 4 \ cdot 4 = 16 \\ 2 \ cdot 16 = 32 \\ 32 \ cdot 32 = 1024$$

The programmer will say. that he remembers this number by heart, and nothing needs to be multiplied. However, we considered the issues of memoization above.

So, quick exponentiation is applicable to matrices, and thus allows us to reduce the asymptotic time complexity of our function from O (n) to O (log n). And this is very cool - unless, of course, this complexity is really so important to us. Let's write the code:

 //    ,          const mul = ( [ [a1, a2], [a3, a4] ], [ [b1, b2], [b3, b4] ]) => [ [a1 * b1 + a2 * b3, a1 * b2 + a2 * b4], [a3 * b1 + a4 * b3, a3 * b2 + a4 * b4] ]; const matrix = [ [0, 1], [1, 1] ]; // ,   const id = [ [1, 0], [0, 1] ] const fib = n => { let result = id; const bits = n.toString(2); //        for(const bit of bits){ result = mul(result, result); if(bit == "1"){ result = mul(result, matrix); } } return result[1][0]; } 

So we got the fastest algorithm in the Wild West. And he, unlike most of the previous ones, can be ironically demonstrated at the interview. And in some math-capacious places, it is him who will be waiting for you.

PS

I promised a remark about how to save the method based on the Binet formula. The answer lies here in this my article. There, for the needs of the national economy, I wrote a special class of root-of-five-rational numbers, which can, without loss of accuracy, store the results of arithmetic operations on integers and a root of five. You can take this class, add it to the rounding method and use it to search for Fibonacci numbers using the Binet formula. And then inject nitrous oxide using a quick exponentiation.

And what is most interesting: if you carefully look at which numbers will be obtained in the process, which operations will be performed, it becomes clear that this method is the same matrix multiplication, only under a different facade. The only difference is that we store numbers in two-dimensional arrays or in fields of an object of a special class.

That's all. If you think that I have missed some interesting ways to find the useless numbers, be sure to write about it in the comments.

There is also such a method as fast doubling . Works like matrix multiplication in O (log), but with a smaller constant in the asymptotics (and in practice). In short, two formulas are used there, based on which you can quickly recursively roll back to twice as small indices:

F _2n = F _n * (2 * F _{n + 1} - F _n )
F _{2n + 1} = F _n ² + F _{n + 1} ²

The implementation, by the way, is quite compact.

Comparison of the speed of different methods

just_maksim