Is it possible to calculate isFibonacci() in constant time?

Question

It is possible to create a fast "give n-th fibonacci number" function as described here. Is there a way to write a isFibonacci(int i) function that perform in O(1)?

I could precalculate values. But the calculation last O(n) and I cant do it for big numbers.

Phenomenal One · Accepted Answer · 2019-03-01T13:07:11.770

4

A number is Fibonacci if and only if one or both of (5*n² + 4) or (5*n² – 4) is a perfect square.

bool isFibonacci(int n) 
{ 
    // n is Fibinacci if one of 5*n*n + 4 or 5*n*n - 4 or both 
    // is a perferct square 
    return isPerfectSquare(5*n*n + 4) || 
           isPerfectSquare(5*n*n - 4); 
}

edited Mar 01 '19 at 13:07

answered Mar 01 '19 at 12:46

Phenomenal One

2,501
4
19
29

2

(how) can `isPerfectSquare` be implemented in constant time? – harold Mar 01 '19 at 13:18
@harold `return round(sqrt(n))^2 == n;` – DIBits Mar 01 '19 at 13:25
@harold or something like `return isInteger(sqrt(n))` – DIBits Mar 01 '19 at 13:30
@DIBits But that ain't constant time. It is `sqrt(n)`. – nice_dev Mar 01 '19 at 14:15

Is it possible to calculate isFibonacci() in constant time?

1 Answers1