C++: Check if a Number is Fibonacci Number

Hey guys! In this tutorial, we will learn how to check if a number is a Fibonacci number in C++ using 3 different methods and compare their use cases.

Let's dive in right now!

Contents

• Method 1: Using the Perfect Square Formula
• Method 2: Generating Fibonacci Numbers Until the Given Number is Reached
• Method 3: Using an Unordered Set
• Comparison
• Conclusion

Method 1: Using the Perfect Square Formula

A number n is a Fibonacci number if and only if one of the following conditions is true:

1. 5n^2 + 4 is a perfect square
2. 5n^2 - 4 is a perfect square

We will turn this formula into a C++ function to check if a number is a Fibonacci number.

#include <stdc++.h>
 
using namespace std;
 
bool isPerfectSquare(int n) {
    int root = sqrt(n);
    return root * root == n;
}
 
bool isFibonacci(int n) {
    return isPerfectSquare(5 * n * n + 4) || isPerfectSquare(5 * n * n - 4);
}
 
int main() {
    int n;
    cout << "Enter a number: ";
    cin >> n;
 
    if (isFibonacci(n)) {
        cout << n << " is a Fibonacci number." << '\n';
    } else {
        cout << n << " is not a Fibonacci number." << '\n';
    }
 
    return 0;
}

In this example, we define two helper functions: isPerfectSquare and isFibonacci.

• The isPerfectSquare function checks if a number is a perfect square by comparing the square of its square root with the original number.
• The isFibonacci function uses the formula mentioned above to check if a number is a Fibonacci number.

The result when running the above code:

Enter a number: 5
5 is a Fibonacci number.

I highly recommend using this formula as it is very simple and effective. However, for large numbers, there may be some precision issues when using the sqrt function. So, be careful when using this method.

Method 2: Generating Fibonacci Numbers Until the Given Number is Reached

Another way to check if a number is Fibonacci is by generating Fibonacci numbers until we find a number greater than or equal to the given number. If the generated number is equal to the given number, then it is a Fibonacci number.

Below is the C++ code to implement the described method:

#include <stdc++.h>
 
using namespace std;
 
bool isFibonacci(int n) {
    int a = 0;
    int b = 1;
 
    while (b < n) {
        int temp = b;
        b = a + b;
        a = temp;
    }
 
    return b == n;
}
 
int main() {
    int n;
    cout << "Enter a number: ";
    cin >> n;
 
    if (isFibonacci(n)) {
        cout << n << " is a Fibonacci number." << '\n';
    } else {
        cout << n << " is not a Fibonacci number." << '\n';
    }
 
    return 0;
}

In this example, we use a while loop to generate the Fibonacci series till we reach a number greater than or equal to the given number. Then, if the generated number is equal to the given number, we return true, otherwise, we return false.

The time complexity of this method is O(n), where n is the given number.

From my perspective, this method is very inefficient when n is a large number, i.e. greater than 10^6. So I don't recommend using it.

Method 3: Using an Unordered Set

The third method is similar to the previous one by generating Fibonacci numbers, but we store the generated numbers in a set and check if the given number is in the set.

Let's implement this method in C++:

#include <stdc++.h>
 
using namespace std;
 
int64_t MAX_N = 1e18;
unordered_set<int64_t> fibonacciSet;
 
void precomputeFibonacci() {
    int64_t a = 0;
    int64_t b = 1;
 
    while (b <= MAX_N) {
        fibonacciSet.insert(b);
        int64_t temp = b;
        b = a + b;
        a = temp;
    }
}
 
bool isFibonacci(int n) {
    return fibonacciSet.count(n);
}
 
int main() {
    precomputeFibonacci(fibonacciSet);
 
    int n;
    cout << "Enter a number: ";
    cin >> n;
 
    if (isFibonacci(n)) {
        cout << n << " is a Fibonacci number." << '\n';
    } else {
        cout << n << " is not a Fibonacci number." << '\n';
    }
 
    return 0;
}

We defined a maximum number MAX_N and precomputed all Fibonacci numbers less than or equal to MAX_N and store them in a set. Then, we can check if the given number is in the set.

This method is useful when we have multiple queries asking if a number is a Fibonacci number.

For example, the code below add one more variable q to ask for the number of queries and then ask for q numbers to check if they are Fibonacci numbers:

#include <stdc++.h>
 
using namespace std;
 
int64_t MAX_N = 1e18;
unordered_set<int64_t> fibonacciSet;
 
void precomputeFibonacci() {
    int64_t a = 0;
    int64_t b = 1;
 
    while (b <= MAX_N) {
        fibonacciSet.insert(b);
        int64_t temp = b;
        b = a + b;
        a = temp;
    }
}
 
bool isFibonacci(int n) {
    return fibonacciSet.count(n);
}
 
int main() {
    precomputeFibonacci(fibonacciSet);
 
    int q;
    cout << "Enter the number of queries: ";
    cin >> q;
 
    while (q--) {
        int n;
        cout << "Enter a number: ";
        cin >> n;
 
        if (isFibonacci(n)) {
            cout << n << " is a Fibonacci number." << '\n';
        } else {
            cout << n << " is not a Fibonacci number." << '\n';
        }
    }
 
    return 0;
}

Comparison

Here is a comparison of the 3 methods:

Each method is appropriate for different situations. The perfect square formula is the most efficient method, while the other two methods are useful in more complex scenarios.

Remember that there is no one-size-fits-all solution. You should choose the method that best fits your specific problem.

Conclusion

In this tutorial, we have learned 3 different ways to check if a number is a Fibonacci number in C++:

1. Using the perfect square formula
2. Generating Fibonacci numbers
3. Using a set

I hope you find this tutorial useful and interesting.