Fast Doubling for Fibonacci

Fast doubling computes (Fₙ,Fₙ₊₁) together using identities for indices 2k and 2k+1. It has logarithmic depth like matrix exponentiation but uses fewer scalar operations for this particular recurrence. We derive the identities from Fibonacci addition, then provide a modular recursive implementation handling n=0 and huge indices. The method is specialized, not a universal replacement for arbitrary recurrence matrices.

Prerequisites: Matrix Exponentiation or Fibonacci addition reasoning; modular arithmetic.

Build the idea

1. 1. Return a pair with a useful invariant

   solve(n) returns exactly Fₙ and Fₙ₊₁ modulo M. The base solve(0)=(0,1) is sufficient for both odd and even branches. Recursing once on floor(n/2) gives a=F_k and b=F_k₊₁, which contain all information needed for doubling.

2. 2. Derive the even identity

   The addition identity F_(r+s)=F_r F_(s+1)+F_(r−1)F_s follows by induction on s from the Fibonacci recurrence. Put r=s=k: F_2k=F_k(F_k₊₁+F_k₋₁). Since F_k₋₁=F_k₊₁−F_k, obtain F_2k=a(2b−a). At k=0 the final polynomial identity still holds directly, so the algorithm never needs to evaluate F_−1.

   $$F_{2k}=F_k(2F_{k+1}-F_k)$$

3. 3. Derive the odd identity

   Applying the same addition identity with r=k+1,s=k gives F_2k₊₁=F_k₊₁²+F_k²=b²+a². Let c=F_2k and d=F_2k₊₁. If n is even return (c,d); if odd return (d,c+d), since the next Fibonacci term is the sum of its predecessors.

   $$F_{2k+1}=F_k^2+F_{k+1}^2$$

4. 4. Trace n=10

   The half call n=5 returns (5,8). Compute c=5(16−5)=55 and d=25+64=89. Because 10 is even, return (55,89). Earlier calls halve 10→5→2→1→0, so only a logarithmic number of pairs is built. Returning both neighbors avoids separately recomputing F_k and F_k₊₁.

5. 5. Normalize subtraction and compare methods

   The residue 2b−a may be negative, so add MOD before taking %. Products and sums are reduced in long long under MOD=1000000007. Matrix exponentiation gives the same asymptotic bound for k=2 but more multiplication machinery; fast doubling exposes closed identities particular to Fibonacci. For exact very large Fibonacci values, arbitrary-precision arithmetic changes the cost of scalar operations.

This is a complete program. Compile with C++17 and enter the input described below.

// Key idea: 1. Return a pair with a useful invariant solve(n) returns exactly Fₙ and Fₙ₊₁ modulo M.
#include<iostream>
#include<utility>
using ll=long long;
const ll MOD=1000000007;
std::pair<ll,ll>fibonacci(unsigned long long n){
    if(n==0){
        return {0,1};
    }
    auto[a,b]=fibonacci(n/2);
    ll c=a*((2*b-a+MOD)%MOD)%MOD;
    ll d=(a*a%MOD+b*b%MOD)%MOD;
    if(n%2==0){
        return {c,d};
    }
    return {d,(c+d)%MOD};
}
int main(){
    unsigned long long n;
    std::cin>>n;
    auto[current,next]=fibonacci(n);
    std::cout<<current<<' '<<next<<'\n';
}

Complexity analysis

O(log(n+1)) machine modular operations and O(log(n+1)) recursion stack. Only one half-size recursive call occurs at each level. n≤10^18 gives at most about 61 stack frames. The fixed modulus keeps intermediate products within long long.

Example input and output

Read n in 0..10^18. Print F_n and F_(n+1), each modulo 1000000007.

Input

10

Output

55 89

The pair at index 5 is (5,8); the doubling identities produce (55,89).

Practical applications

Use for isolated huge-index Fibonacci queries or when both neighboring terms are needed. Matrix exponentiation is more general for other linear recurrences. Iterative Fibonacci DP is simpler for short ranges and can produce all terms, while doubling targets a few large indices.

Check your understanding

Why return both F_n and F_(n+1)?

Put it into practice

Cross-check random indices with matrix exponentiation and small indices with linear DP.