Fast Fibonacci

What they ask

The second of the two internship interviews, this time with an engineer in a US office. It starts small and escalates:

Write a function that returns the n-th Fibonacci number.

Then: make it faster. Then: faster than linear. The expected end point is O(log n) using matrix exponentiation or the equivalent fast-doubling identities, and a short discussion of what happens when the numbers get big (modular arithmetic or arbitrary precision).

Examples

• n = 10 returns 55.
• n = 90 returns 2880067194370816120, which already needs 64-bit integers.
• With modulus 10^9 + 7, n = 10^18 must still answer instantly.

Constraints

• 0 <= n <= 10^18 in the final version, with a modulus.
• Define F(0) = 0, F(1) = 1.

What they look for

• Progression you drive yourself: naive recursion, then memoisation or iteration, then the logarithmic method, each with its complexity.
• Knowing why [[1,1],[1,0]]^n gives Fibonacci numbers, and writing a clean binary exponentiation loop.
• Overflow awareness: in Python it is free, in JavaScript you need BigInt or a modulus.
• Tests: n = 0, n = 1, n = 2, a large n against a known value.

This is a question where the interviewer is measuring how you respond to "can you do better?" three times in a row, so do not jump straight to the fancy answer without showing the simpler ones.