Cal11 calculator
Search calculator...

Calculate Nth Fibonacci in Log N

Reviewed by Calculator Editorial Team

The Fibonacci sequence is a series of numbers where each number is the sum of the two preceding ones, starting from 0 and 1. Calculating the nth Fibonacci number efficiently is important for computer science and mathematical applications. This guide explains how to compute Fibonacci numbers in logarithmic time complexity (O(log n)), which is significantly faster than the naive recursive approach.

What is the Fibonacci sequence?

The Fibonacci sequence is defined by the recurrence relation:

F0 = 0
F1 = 1
Fn = Fn-1 + Fn-2 for n > 1

The sequence begins: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, and so on. The Fibonacci sequence appears in nature, mathematics, and computer science, making it a fundamental concept in discrete mathematics.

Logarithmic time algorithm

Calculating the nth Fibonacci number in O(log n) time is possible using matrix exponentiation or Binet's formula. The matrix method is more efficient for programming implementations because it avoids floating-point precision issues that can occur with Binet's formula.

The key insight is that Fibonacci numbers can be represented using matrix multiplication:

| Fn Fn-1 | = | 1 1 |n-1 | F1 F0 |
| Fn-1 Fn-2 | | 1 0 | | F0 F-1 |

By raising the transformation matrix to the (n-1)th power, we can compute Fn in O(log n) time using exponentiation by squaring.

How to calculate Fibonacci in O(log n)

The algorithm involves these steps:

  1. Create a transformation matrix: [[1, 1], [1, 0]]
  2. Raise this matrix to the (n-1)th power using exponentiation by squaring
  3. Multiply the resulting matrix with the initial vector [F1, F0] = [1, 0]
  4. The top-left element of the resulting matrix is Fn

This method has O(log n) time complexity because exponentiation by squaring reduces the problem size by half with each step.

Worked example

Let's calculate F5 using this method:

  1. Transformation matrix: [[1, 1], [1, 0]]
  2. Compute [[1, 1], [1, 0]]4:
    • Square the matrix: [[2, 1], [1, 1]]
    • Square again: [[3, 2], [2, 1]]
    • Square once more: [[5, 3], [3, 2]]
  3. Multiply with [1, 0]: [5*1 + 3*0, 3*1 + 2*0] = [5, 3]
  4. F5 is the first element: 5

This matches the Fibonacci sequence: 0, 1, 1, 2, 3, 5.

FAQ

Why is O(log n) better than O(n)?
O(log n) algorithms become significantly faster as n grows large. For example, calculating F1000 with O(log n) takes about 10 matrix multiplications, while O(n) would require 1000 additions.
Can this method handle very large n?
Yes, but you need to use arbitrary-precision arithmetic to avoid integer overflow. Most programming languages have big integer support for this purpose.
Is there a simpler O(log n) method?
The matrix method is the most straightforward implementation. Binet's formula can also achieve O(log n) time but requires floating-point operations and careful precision handling.
What's the time complexity of the naive recursive approach?
The naive recursive method has O(2n) time complexity because it recalculates the same Fibonacci numbers many times. This is impractical for n > 30.