Free Recursion lessonsRecursion · Stage 2 · Divide and conquer · Step 4

Fibonacci in a few steps

Find a huge Fibonacci number by getting the pair for half the index and doubling it. About 17 minutes.

Two formulas for doubling

Fibonacci numbers start 0, 1, 1, 2, 3, 5, 8, and each is the sum of the two before. To get the number at position one million, you could step a million times, but position 10^15 is out of reach that way.

There are two handy identities. If you know F(k) and F(k + 1), then F(2k) equals F(k) times (2·F(k + 1) minus F(k)), and F(2k + 1) equals F(k) squared plus F(k + 1) squared. With these, one pair at half the index gives the pair at the full index.

Know the pair: F(k) and F(k + 1) at half the index.

Doubling: gives F(2k) and F(2k + 1).

In code

def min_max(lo, hi):
    if lo == hi:
        return (nums[lo], nums[lo])
    mid = (lo + hi) // 2
    a, b = min_max(lo, mid)
    c, d = min_max(mid + 1, hi)
    return (min(a, c), max(b, d))

F(10) from the pair at 5, from the pair at 2, from 1, from 0.

leftright

We want F(10). It is even, so it needs the pair at 5.

Move 1 of 5

Staying modulo a prime

Fibonacci numbers grow enormously, so problems ask for the answer modulo a prime such as 1,000,000,007. Take the remainder after every multiplication and addition so numbers stay small.

Be careful with the subtraction in the first formula: 2·F(k + 1) minus F(k) can go negative after reducing, so add the prime before taking the remainder. In languages with 64-bit numbers, a product of two numbers below the prime still fits.

Subtraction: add the prime back before the remainder.

Reduce every step: so no number gets large.

In code

MOD = 1_000_000_007
big = (2 ** 100) % MOD

Quick check

How many levels of calls does it take to reach the pair at index 1,000,000?

AAbout 20, since halving 1,000,000 reaches 0 after about 20 steps
B1,000,000
CAbout 5

Show the answer

About 20, since halving 1,000,000 reaches 0 after about 20 steps. 2 to the power of 20 is about a million, so each halving brings you down quickly.

Your problem

Fibonacci in a few steps

The Fibonacci numbers are F(0) = 0, F(1) = 1, and F(i) = F(i − 1) + F(i − 2) for i ≥ 2. Return F(n) modulo 1,000,000,007.

Example

n = 10 → 55

0 ≤ n ≤ 9,000,000,000,000,000

Solve it in your browserFree account, no card. Python, C++, Java or JavaScript, with hints if you get stuck, and your progress is saved.