Java Programs›Numbers›Check Fibonacci Number

Check Fibonacci Number in Java

intermediate· Numbers · Number Theory

Problem

A number is a Fibonacci number exactly when 5×n²+4 or 5×n²−4 is a perfect square — a fact derived from the closed-form Fibonacci formula (Binet's formula).

Given a number, determine whether it is a Fibonacci number.

Input

8

Output

8 is a Fibonacci number: true

Java Program

Java

public class FibonacciNumberCheck {
    static boolean isPerfectSquare(long x) {
        long root = (long) Math.sqrt(x);
        // checks root+1 too, as a safety net against floating-point rounding in Math.sqrt()
        return root * root == x || (root + 1) * (root + 1) == x;
    }

    public static void main(String[] args) {
        int n = 8;
        long test1 = 5L * n * n + 4;
        long test2 = 5L * n * n - 4;
        boolean isFibonacci = isPerfectSquare(test1) || isPerfectSquare(test2);
        System.out.println(n + " is a Fibonacci number: " + isFibonacci);
    }
}

▶ Run Code

Output

8 is a Fibonacci number: true

Core Logic

Rather than generating Fibonacci numbers to check for a match, a known mathematical identity turns membership testing into a single perfect-square check.

How It Works

1isPerfectSquare(x) takes the integer square root of x and checks whether squaring it back gives x exactly.
2It actually checks both root and root + 1 squared, as a safety net against Math.sqrt()'s floating-point rounding landing just under the true root.
3test1 and test2 compute 5n² + 4 and 5n² − 4.
4n is a Fibonacci number exactly when either of those two values is a perfect square.

For 8, 5 × 64 + 4 = 324, and 324 is 18² — a perfect square — so 8 is confirmed a Fibonacci number.

💡

Key Point: This is a genuine mathematical shortcut, not an approximation — the 5n²±4 identity is a proven necessary-and-sufficient test, so there's no need to generate a single Fibonacci number to use it.

Complexity

Time Complexity: O(1)Space Complexity: O(1)

Why: The perfect-square test runs in constant time regardless of n's magnitude, needing only a square root and a couple of multiplications.

Key Concepts

perfect square testMath.sqrt()Binet's formula

Approach 2: Generate and Check

Java

public class FibonacciNumberCheckGenerate {
    public static void main(String[] args) {
        int n = 8;
        int a = 0, b = 1;
        boolean isFibonacci = (n == a);

        while (b <= n) {
            if (b == n) {
                isFibonacci = true;
                break; // found an exact match, no need to generate further
            }
            int next = a + b; // next term is the sum of the last two
            a = b;
            b = next;
        }

        System.out.println(n + " is a Fibonacci number: " + isFibonacci);
    }
}

▶ Run Code

Output

8 is a Fibonacci number: true

Core Logic

A more direct approach just generates Fibonacci numbers up to n and checks whether n shows up among them — no special identity required.

How It Works

1a and b track two consecutive Fibonacci terms, starting at 0 and 1.
2The loop keeps generating the next term as long as b hasn't yet passed n.
3If b ever equals n exactly, n is confirmed a Fibonacci number and the loop exits immediately.
4If the loop finishes because b passed n without ever matching it, n isn't a Fibonacci number.

Starting from 0, 1, the terms generated are 1, 2, 3, 5, 8 — the fifth term generated lands exactly on 8, confirming the match.

💡

Key Point: Because Fibonacci numbers grow exponentially, this never needs many iterations even for a fairly large n — but the 5n²±4 identity still answers the question in a single step, with no generation at all.

Complexity

Time Complexity: O(log n)Space Complexity: O(1)

Why: Fibonacci numbers grow exponentially, so only a logarithmic number of terms need to be generated before reaching or passing n.

Key Concepts

iterationrunning pairearly exit with break

← Previous

Check Evil Number

Check Happy Number

Related Programs

Numbersintermediate

Calculate Combination (nCr)

Numbersintermediate

Calculate Permutation (nPr)

Numbersintermediate

Calculate Power Using Recursion

Numbersbeginner

Check Abundant Number

Numbersbeginner

Check Armstrong Number