Ashot Tarumyan - 16 days ago 6

Javascript Question

Is there an efficient way to check if number belongs to Fibonacci sequence?

I've seen many examples with a loop that creates the sequence in an array and checks every time if newly generated number of the sequence is equal to the input number. Is there another way?

Answer

http://www.geeksforgeeks.org/check-number-fibonacci-number/

This link details that there is a special quality about fibonacci numbers that means that a number is Fibonacci if and only if one or both of (5*n2 + 4) or (5*n2 – 4) is a perfect square.

So,

```
function (num) {
if (isSquare(5*(num*num)-4) || isSquare(5*(num*num)+4) {
return true;
} else { return false; }
}
```

Then isSquare would just be a simple checking function.

Edit: Worth noting that while this is a much more efficient and easy way to find fibonacci numbers, it does have an upper bound. At about the 70th Fibonacci number and above, you may see issues because the numbers are too large.

Source (Stackoverflow)

Comments