Fibonacci With Complexity | Dataford Interview Questions

CAE engineering simulation workflows may request sequence values at extremely large indices. Implement fibonacci(n, mod) to return the nth Fibonacci number modulo mod, using an algorithm that remains efficient when n is as large as 10^18.

The Fibonacci sequence is defined as F(0) = 0, F(1) = 1, and F(n) = F(n - 1) + F(n - 2) for n >= 2.

Formal Specification

Input: Two integers, n and mod.
Output: An integer equal to F(n) % mod.
Use fast doubling identities to avoid constructing all preceding Fibonacci values.
The input satisfies n >= 0 and mod >= 2.

Constraints

0 <= n <= 10^18
2 <= mod <= 10^9
The result must equal F(n) modulo mod
The algorithm must run in O(log n) time
Do not generate all Fibonacci values up to n

Function Signature

def fibonacci(n, mod):

Your question is Fibonacci With Complexity. Start with the requirements in the Question tab.

Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.

Problem