0

I am working on a seemingly typical task for an interview - to calculate a Fibonacci number by an index of that number. But the difficulty of the task is that the index can be up to 2000000. I have encountered several problems and I do not understand why they happen.

First the code:

function fib(number) {  
  const left = Math.pow((1 + Math.sqrt(5)) / 2, number);
  const right = Math.pow((1 - Math.sqrt(5)) / 2, number);
  const result = Math.round((left - right) / Math.sqrt(5));
  
  console.log(result); // 
  return BigInt(result); // 
}

Problems:

  1. BigInt differs from a number
fib(96);
console.log(result) // -> 51680708854858490000
BigInt(result) // 51680708854858489856
  1. Wrong answer. I think it is related to the previous problem
fib(96);
// Must return 51680708854858323072
// But return BigInt 51680708854858489856
Vania Kycher
  • 173
  • 1
  • 1
  • 8
  • 2
    I do not code in javascript by my bet is that `Math.pow` and `Math.round` are both float or double so you lose precision long before you cast it into bigint ... – Spektre Jun 02 '21 at 20:11
  • @Spektre make sense, ty. But I don't know how to solve this problem without third-party libraries =) – Vania Kycher Jun 02 '21 at 20:18
  • 1
    To compute large fibonacci numbers exactly [this](https://en.wikipedia.org/wiki/Fibonacci_number#Matrix_form) is usually the best way. – President James K. Polk Jun 02 '21 at 23:47
  • 1
    @PresidentJamesK.Polk yes [2x2 matrix form](https://www.nayuki.io/page/fast-fibonacci-algorithms) + [power by squaring](https://stackoverflow.com/a/30962495/2521214) is the way as it uses only bigint `+,*` operations – Spektre Jun 03 '21 at 05:26

1 Answers1

5

Javascript numbers are by default stored as floats, which means they're stored in scientific notation in memory (unless you're using BigInt), and they can only hold a limited amount of precision. So, a large number is represented somewhat like this: 1.2345 * 10^12, and there's a limit to the number of digits after the . that is stored in memory. You're dealing with some really large numbers, and are overflowing the amount of precision a single floating-point number can hold, which is why your computations end up wrong. BigInt is the solution to this, as it does not store numbers in scientific notation, and can hold an arbitrary amount of digits. However, you have to use BigInt all the way through your calculation - you can't just convert the scientific notation number to a BigInt at the end and expect the extra precision to pop out of nowhere.

So, to make it work properly, ensure you pass a BigInt into your fib function as a parameter (or convert it to one after it's passed in), and make sure each numeric literal is a BigInt literal (e.g. use 2n instead of 2). There is one caveat - a BigInt has to be an integer, it can not hold decimal values. This may require some adjustments to your algorithm.

If you want to learn more about the specific details of floats, and how much precision they can hold, take a look at this Wikipedia article.

Scotty Jamison
  • 10,498
  • 2
  • 24
  • 30
  • I get it, thank you. Do you have some ideas on how to do pow and sqrt operations without 3rd party libraries with BigInt? – Vania Kycher Jun 02 '21 at 20:24
  • BigInt supports the power operator "**". You can not do sqrt, because BigInt must always be an integer. Unfortunately, there may not be a way to achieve your specific algorithm - what you're asking for is a way to store very large amounts of precision in memory - a feature many programming languages don't provide. Why? Well, how do you tell the language how _much_ precision you need? Some floats require infinite precision to accuratly represent them, and that's not possible. – Scotty Jamison Jun 02 '21 at 20:29
  • Got it. Thank you! – Vania Kycher Jun 02 '21 at 20:31
  • If you're careful, there are sometimes ways to continue to use floats, and to rearrange an algorithm, such that little precision gets lost, but I can't see any easy way to do that with your algorithm at the moment. – Scotty Jamison Jun 02 '21 at 20:33
  • I used the Golden Ratio formula. Is there any other way to get the result I need, given the requirements with a maximum index of 200000? – Vania Kycher Jun 02 '21 at 20:43
  • It'll unfortunately be slower, but you can always iterate and calculate the next digit one at a time. A computer should be able to handle 200,000 iterations in a fairly good amount of time (computers are fast). If the performance is needed, there may be some other mathematical formula to achieve this also, but I certainly don't know one off the top of my head. – Scotty Jamison Jun 02 '21 at 20:49
  • For example, I just threw together this algorithm, and it took it one second to run with index 200,000: `parts = [1n, 1n]; for (let i = 0n; i < 200000n; ++i) parts = [parts[1], parts[0]+parts[1]];` – Scotty Jamison Jun 02 '21 at 20:54
  • I don't really know what you're talking about) Can you provide full code? Maybe gist or jsbin – Vania Kycher Jun 02 '21 at 20:59
  • There's not much more than what I provided, but here it is, wrapped up in a function: `fib = endIndex => { parts = [0n, 1n]; for (let i = 0n; i < BigInt(endIndex); ++i) { parts = [parts[1], parts[0]+parts[1]]; } return parts[0]; }` – Scotty Jamison Jun 02 '21 at 21:03