Fibonacci interview

The calculation of the Fibonacci series is a classic algorithmic task, because it is often given at interviews when they want to verify that the candidate, in principle, is at least somehow able in algorithms. Suppose you are the same candidate. You were given the task: in JavaScript, write a function fib(n)that returns the nth Fibonacci number. We consider 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 cycle.

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 full-time obfuscator.

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

Are you running out of variable coupons? cypok

Okay, okay, for even greater readability, let's 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 option. But perhaps you want to demonstrate your knowledge of some other concepts? For instance…

2. To understand recursion, you must understand recursion

For example, yes, you can demonstrate that you can do recursion. For example, like this:

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

Remember this option. This is not worth doing. Do not do it. It is impossible. Never. This is worse than kicking puppies, and is comparable to a small holocaust.

You may ask why. In this case, just run this code and try to calculate, say, the Fifty Fibonacci number. I think you will feel a certain delay. Joke. I believe that if you run this code not on a supercomputer, then you simply won’t wait for the result. Despite the fact that the simple, non-recursive code from the previous examples will count the fiftieth member of the Fibonacci sequence faster than you have time to say the word “fifty” or any syllable.

Expressed in the rough language of O-notation, such a solution has a time complexity of O (e ⁿ) That is, the execution time of this function grows exponentially with increasing n. That is - when n increases to , 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 a typesetter 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 calls to the function ~ (1 + sqrt (5)) fib (n) and the beautiful remark “To calculate the Fibonacci number using a naive recursive method, you need 3.2 times more function calls than the Fibonacci number itself.” Taus

And we get another method for calculating 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 recursively solve this problem during an interview, this is most likely a trap. A “correct” recursion working in linear time might look, for example, 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];

To summarize: despite the fact that 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 show off some more knowledge.

3. Memorial function

There is a magical way that turns a monstrously ineffective solution from the last paragraph into a potentially very quick one (although not without problems). His name is memoization. And if you speak Russian - we just remember the results of previous calls instead of calculating them again.

Basically, we can not even change anything inside that solution - just add a 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 function fibhas access to the object through the closure cache. If it is called with an argument that has not previously been encountered, the calculated value is stored in cache. With new function calls with the same argument, the value does not have to be re-calculated, it will simply be taken from the cache. The main problem of the “bad” old function fibwas that the same values ​​in it were recalculated several times. For example, to calculate fib(45)it was necessary to calculate once f(44), two times - f(43), three times - f(42), five times - f(41), 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 much faster we can now calculate the forty-fifth Fibonacci number? Seriously, what time do you think?

In fact - a little slower. I deliberately made a classic mistake, often made when memoizing recursive functions. When called fib(45)“under the hood”, it is called oldFib(45), which calls for its needs oldFib(44)and oldFib(43)... Do you feel a catch? Hereinafter, there are already calls to a regular, non-memoized function. Of course, when you call again, fib(45)we instantly get the result from the cache - however, the first call did not speed up at all. To fix this, you still have to get oldFibunder 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 will fib(45)work at a speed comparable to the version with a loop. And further challenges will generally work in constant time ... Oops! Again deceived. Obtaining the value of an object’s property by key is a quick operation, but still O (1) is only on average, in the worst case it can degrade to O (n). In order to become completely good, in our case we can change the type cachefrom an object to an array.

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

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

4. Mr. Binet

There is a special, wonderful science on how to transform recurrence relationships into explicit formulas. Here we will not go into its details. We will only say that for Fibonacci numbers, using fairly simple arguments, we can derive the following formula, known as the Binet formula:

$$

However, it’s quite a mathematical language, we write it 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;
}

Let's drive on the first few numbers. Great, everything seems to work. Here are 13, here are 21, here are 34, here ... 54.9999999999999999?

Yes, of course, such a result is logical. The Binet formula is mathematically accurate, but the computer operates with fractions of finite accuracy, and errors can accumulate during operations with them, which happened in this case. However, we can fix it. Knowing that the subtracted in the numerator will always be small in magnitude, we can simplify the formula to the following state:

$$

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, that’s much better. We can see both 55 and 89, and even my favorite Fibonacci number is 144 (which I love because it equals twelve squared). Everything will be fine until the number 76. Which should be equal to 3416454622906707, and our function will calculate 3416454622906706. Because the problem of the limited accuracy of fractional numbers has not gone away, we just pushed it deeper and hoped that it would not come up. As this example shows, they hoped in vain.

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

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 on the contrary. Many problems, if reformulated in the language of matrices, are solved simply by themselves.

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

$$

That is, if we take a pair of consecutive Fibonacci numbers and multiply them by such a straightforward matrix, we get the following pair. And the logical conclusion follows from this: if we take a pair of zero and first Fibonacci numbers, that is, zero and one, and multiply them by this matrix to an nth power, we get a pair of nth and en plus the first Fibonacci. That is, speaking humanly:

$$

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

$$

Great, isn't it? It remains to understand, what for ass harmony, if he is not a philharmonic. I mean - why are such difficulties out of the blue. And the answer is simple - rapid exponentiation.

How many elementary multiplications does it take to calculate, say, 2 ¹⁰ ? A normal person will say nine. Two by two is four. Twice four - eight. Twice eight is sixteen. Etc. A cunning person will say that four.

$$

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

So, a quick exponentiation is also 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 it, unlike most of the previous ones, can be demonstrated non-ironically at an interview. And in some mathematical-capacious places it will be expected from you.

PS

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

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

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

There is also such a method as fast doubling . It works like matrix multiplication in O (log), but with a smaller constant in asymptotics (and in practice). In short, two formulas are used there, relying on which one can quickly roll back to half the 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