Fibonacci by Fast Doubling

Problem

Return the n-th Fibonacci number with F(0) = 0 and F(1) = 1 using fast doubling in O(log n) time.

Use the identities F(2k) = F(k) * (2 * F(k+1) - F(k)) and F(2k+1) = F(k)^2 + F(k+1)^2, which let a recursive pair of values halve n on each call. Assume n is a non-negative integer.

Hint

The recursive helper returns the pair (F(k), F(k+1)), and the two identities build the pair for k doubled or doubled plus one.

Test cases

case 1

in: [0]

expected: 0

case 2

in: [1]

expected: 1

case 3

in: [10]

expected: 55

case 4

in: [50]

expected: 12586269025

case 5

in: [60]

expected: 1548008755920

Starter codePython

def fib_fast(n):
    # Your code here
    pass

5 test cases · run your code against them in the editor