Find Fibonacci Number at Position N in Java
Problem
The Nth Fibonacci number is the value at position N in the sequence, where each term is the sum of the two before it — this is about computing one specific term efficiently, not printing the whole sequence up to it.
Given a position N, find the Fibonacci number at that position.
Java Program
public class FibonacciAtPosition {
public static void main(String[] args) {
int n = 10;
long a = 0, b = 1;
for (int i = 0; i < n; i++) {
long next = a + b; // next term is the sum of the last two
a = b;
b = next;
}
System.out.println("Fibonacci number at position " + n + ": " + a);
}
}Output
Core Logic
Sliding a pair of variables forward one step at a time, the same technique used to print the whole sequence, still works perfectly well when only the final term at position N is actually needed.
- 1
aandbstart at0and1, the first two Fibonacci terms. - 2The loop runs exactly
ntimes, each time computingnext = a + band shifting both variables forward. - 3No intermediate terms are printed — only the final values of
aandbafter the loop matter. - 4Once the loop finishes,
aholds the Fibonacci number at positionn.
n = 10, the loop runs ten times, sliding the pair forward through every intermediate term until a lands on 55.Key Point: This is the same sliding-pair technique used to print the sequence — the only difference is that nothing gets printed until the single term at position n is reached.
Why: Each term is computed once from the previous two, which are kept in just two variables regardless of how large n is.
Key Concepts
Approach 2: Fast Doubling
public class FibonacciAtPositionFastDoubling {
// Returns {F(n), F(n+1)} using the fast doubling identities
static long[] fibPair(int n) {
if (n == 0) return new long[]{0, 1};
long[] half = fibPair(n / 2);
long a = half[0], b = half[1];
long c = a * (2 * b - a); // F(2k)
long d = a * a + b * b; // F(2k+1)
if (n % 2 == 0) {
return new long[]{c, d};
} else {
return new long[]{d, c + d};
}
}
public static void main(String[] args) {
int n = 10;
long result = fibPair(n)[0];
System.out.println("Fibonacci number at position " + n + ": " + result);
}
}
Output
Core Logic
A pair of identities lets F(2k) and F(2k+1) be computed directly from F(k) and F(k+1), so the position can be halved at every step instead of counted down one at a time — turning an O(n) climb into an O(log n) one.
- 1
fibPair(n)returns bothF(n)andF(n+1)together, so each call has everything the next level up needs. - 2It recurses on
n / 2first, then combines that smaller pair using the fast-doubling identities:F(2k) = F(k) × (2×F(k+1) − F(k))andF(2k+1) = F(k)² + F(k+1)². - 3Whether the current
nis even or odd determines which of those two combined values corresponds toF(n)and which toF(n+1). - 4The base case
n == 0returns the seed pair{0, 1}, and the recursion unwinds back up from there.
n = 10, the recursion only ever needs to compute pairs at positions 5, 2, 1, 0 — four levels deep — rather than climbing through all ten positions one at a time.Key Point: This trades a more intricate recursive formula for a dramatic speedup at large n — computing the millionth Fibonacci number this way takes roughly 20 steps instead of a million.
Why: Each call halves n and does a constant amount of arithmetic, so the recursion depth — and the total work — grows logarithmically with n.