Optimizing Fibonacci Sequence Calculation
Matrix Exponentiation
Another efficient way to calculate the Fibonacci sequence is by using matrix exponentiation. The Fibonacci sequence can be represented using a 2x2 matrix, and the nth Fibonacci number can be calculated by raising this matrix to the power of n.
Here's an example implementation in Python:
def fibonacci(n):
if n <= 0:
return 0
elif n == 1:
return 1
else:
return matrix_fibonacci(n)[0][0]
def matrix_fibonacci(n):
if n == 0:
return [[1, 0], [0, 1]]
elif n == 1:
return [[1, 1], [1, 0]]
else:
A = matrix_fibonacci(n // 2)
if n % 2 == 0:
return matrix_multiply(A, A)
else:
return matrix_multiply(matrix_multiply(A, A), [[1, 1], [1, 0]])
def matrix_multiply(A, B):
n = len(A)
m = len(B[0])
C = [[0 for _ in range(m)] for _ in range(n)]
for i in range(n):
for j in range(m):
for k in range(len(A[0])):
C[i][j] += A[i][k] * B[k][j]
return C
In this implementation, the matrix_fibonacci() function calculates the 2x2 matrix representation of the Fibonacci sequence up to the nth term. The matrix_multiply() function is used to perform matrix multiplication, which is then used to efficiently calculate the nth Fibonacci number.
The time complexity of this approach is O(log n), which is significantly better than the recursive and iterative approaches.
Another way to calculate the Fibonacci sequence is by using Binet's formula, which provides a closed-form expression for the nth Fibonacci number:
import math
def fibonacci(n):
if n <= 0:
return 0
elif n == 1:
return 1
else:
phi = (1 + math.sqrt(5)) / 2
return round((phi ** n - (-phi) ** (-n)) / math.sqrt(5))
In this implementation, we use the mathematical formula to directly calculate the nth Fibonacci number without the need for iterative or recursive calculations. This approach has a constant time complexity, making it very efficient for large values of n.
To compare the performance of the different approaches, we can run some benchmarks on an Ubuntu 22.04 system:
import timeit
## Recursive approach
recursive_setup = "def fibonacci(n):\n if n <= 0:\n return 0\n elif n == 1:\n return 1\n else:\n return fibonacci(n-1) + fibonacci(n-2)"
recursive_stmt = "fibonacci(40)"
recursive_time = timeit.timeit(recursive_stmt, setup=recursive_setup, number=1)
print(f"Recursive approach: {recursive_time:.6f} seconds")
## Iterative approach
iterative_setup = "def fibonacci(n):\n if n <= 0:\n return 0\n elif n == 1:\n return 1\n else:\n a, b = 0, 1\n for i in range(2, n+1):\n c = a + b\n a, b = b, c\n return b"
iterative_stmt = "fibonacci(40)"
iterative_time = timeit.timeit(iterative_stmt, setup=iterative_setup, number=1)
print(f"Iterative approach: {iterative_time:.6f} seconds")
## Memoization approach
memoization_setup = "def fibonacci(n, memo={}):\n if n <= 0:\n return 0\n elif n == 1:\n return 1\n elif n in memo:\n return memo[n]\n else:\n memo[n] = fibonacci(n-1, memo) + fibonacci(n-2, memo)\n return memo[n]"
memoization_stmt = "fibonacci(40, {})"
memoization_time = timeit.timeit(memoization_stmt, setup=memoization_setup, number=1)
print(f"Memoization approach: {memoization_time:.6f} seconds")
## Matrix exponentiation approach
matrix_setup = """
def fibonacci(n):
if n <= 0:
return 0
elif n == 1:
return 1
else:
return matrix_fibonacci(n)[0][0]
def matrix_fibonacci(n):
if n == 0:
return [[1, 0], [0, 1]]
elif n == 1:
return [[1, 1], [1, 0]]
else:
A = matrix_fibonacci(n // 2)
if n % 2 == 0:
return matrix_multiply(A, A)
else:
return matrix_multiply(matrix_multiply(A, A), [[1, 1], [1, 0]])
def matrix_multiply(A, B):
n = len(A)
m = len(B[0])
C = [[0 for _ in range(m)] for _ in range(n)]
for i in range(n):
for j in range(m):
for k in range(len(A[0])):
C[i][j] += A[i][k] * B[k][j]
return C
"""
matrix_stmt = "fibonacci(40)"
matrix_time = timeit.timeit(matrix_stmt, setup=matrix_setup, number=1)
print(f"Matrix exponentiation approach: {matrix_time:.6f} seconds")
## Binet's formula approach
binet_setup = "import math\n\ndef fibonacci(n):\n if n <= 0:\n return 0\n elif n == 1:\n return 1\n else:\n phi = (1 + math.sqrt(5)) / 2\n return round((phi ** n - (-phi) ** (-n)) / math.sqrt(5))"
binet_stmt = "fibonacci(40)"
binet_time = timeit.timeit(binet_stmt, setup=binet_setup, number=1)
print(f"Binet's formula approach: {binet_time:.6f} seconds")
The output of this benchmark on an Ubuntu 22.04 system might look like this:
Recursive approach: 0.002729 seconds
Iterative approach: 0.000001 seconds
Memoization approach: 0.000001 seconds
Matrix exponentiation approach: 0.000001 seconds
Binet's formula approach: 0.000001 seconds
As you can see, the recursive approach is the slowest, while the iterative, memoization, matrix exponentiation, and Binet's formula approaches are all significantly faster, with the latter three being the most efficient.
The choice of the best approach depends on the specific requirements of your use case, such as the range of Fibonacci numbers you need to calculate, the available memory, and the required performance characteristics.
