Fibonacci

Fibonacci Sequence Implementation using Dynamic Programming

The Fibonacci sequence is a series of numbers where each number is the sum of the two preceding ones, starting from 0 and 1: F(0) = 0, F(1) = 1, F(n) = F(n-1) + F(n-2) for n > 1

This module implements multiple approaches to compute Fibonacci numbers:

Naive recursive approach (exponential time)
Memoized recursive approach (top-down DP)
Tabulated iterative approach (bottom-up DP)
Space-optimized approach (O(1) space)
Matrix exponentiation approach (logarithmic time)

Time Complexities:

Recursive: O(2^n) - exponential
Memoized: O(n) - linear with O(n) space
Tabulated: O(n) - linear with O(n) space
Space Optimized: O(n) - linear with O(1) space
Matrix: O(log n) - logarithmic

`fibonacci_matrix(n)`

Compute the nth Fibonacci number using matrix exponentiation.

This approach uses the mathematical property that:

[F(n+1)]   [1 1]^n   [1]
[F(n)  ] = [1 0]   * [0]

By using fast matrix exponentiation, we can compute this in O(log n) time.

Time Complexity: O(log n) - using fast exponentiation

Space Complexity: O(log n) - due to recursion in matrix exponentiation

Parameters:

Name	Type	Description	Default
`n`	`int`	Non-negative integer position in Fibonacci sequence	required

Returns:

Type	Description
`int`	The nth Fibonacci number

Raises:

Type	Description
`ValueError`	If n is negative

Examples:

>>> fibonacci_matrix(0)
0
>>> fibonacci_matrix(1)
1
>>> fibonacci_matrix(20)
6765

`fibonacci_memoized(n, memo=None)`

Compute the nth Fibonacci number using memoization (top-down dynamic programming).

This approach uses recursion but stores previously computed results in a dictionary to avoid redundant calculations. This is a classic example of top-down dynamic programming.

Time Complexity: O(n) - each subproblem computed once Space Complexity: O(n) - for memoization table and recursion stack

Parameters:

Name	Type	Description	Default
`n`	`int`	Non-negative integer position in Fibonacci sequence	required
`memo`	`Dict[int, int]`	Dictionary to store computed results (internal use)	`None`

Returns:

Type	Description
`int`	The nth Fibonacci number

Raises:

Type	Description
`ValueError`	If n is negative

Examples:

>>> fibonacci_memoized(0)
0
>>> fibonacci_memoized(1)
1
>>> fibonacci_memoized(50)
12586269025

`fibonacci_recursive(n)`

Compute the nth Fibonacci number using naive recursion.

This is the most straightforward implementation but also the least efficient due to redundant calculations. Each call spawns two more recursive calls, leading to exponential time complexity.

Time Complexity: O(2^n) - exponential Space Complexity: O(n) - due to recursion stack

Parameters:

Name	Type	Description	Default
`n`	`int`	Non-negative integer position in Fibonacci sequence	required

Returns:

Type	Description
`int`	The nth Fibonacci number

Raises:

Type	Description
`ValueError`	If n is negative

Examples:

>>> fibonacci_recursive(0)
0
>>> fibonacci_recursive(1)
1
>>> fibonacci_recursive(10)
55

`fibonacci_sequence(n, method='space_optimized')`

Generate the first n Fibonacci numbers using the specified method.

Parameters:

Name	Type	Description	Default
`n`	`int`	Number of Fibonacci numbers to generate	required
`method`	`str`	Algorithm to use ("recursive", "memoized", "tabulated", "space_optimized", or "matrix")	`'space_optimized'`

Returns:

Type	Description
`List[int]`	List containing the first n Fibonacci numbers

Raises:

Type	Description
`ValueError`	If n is negative or method is invalid

Examples:

>>> fibonacci_sequence(10)
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34]

>>> fibonacci_sequence(5, "memoized")
[0, 1, 1, 2, 3]

`fibonacci_space_optimized(n)`

Compute the nth Fibonacci number using space-optimized dynamic programming.

Since we only need the two previous values to compute the current one, we can optimize space complexity to O(1) by using just two variables instead of an entire array.

Time Complexity: O(n) - single loop through all values Space Complexity: O(1) - constant extra space

Parameters:

Name	Type	Description	Default
`n`	`int`	Non-negative integer position in Fibonacci sequence	required

Returns:

Type	Description
`int`	The nth Fibonacci number

Raises:

Type	Description
`ValueError`	If n is negative

Examples:

>>> fibonacci_space_optimized(0)
0
>>> fibonacci_space_optimized(1)
1
>>> fibonacci_space_optimized(1000)
43466557686937456435688527675040625802564660517371780402481729089536555417949051890403879840079255169295922593080322634775209689623239873322471161642996440906533187938298969649928516003704476137795166849228875

`fibonacci_tabulated(n)`

Compute the nth Fibonacci number using tabulation (bottom-up dynamic programming).

This approach builds up the solution iteratively from the base cases, storing all intermediate results in a table. This is a classic example of bottom-up dynamic programming.

Time Complexity: O(n) - single loop through all values Space Complexity: O(n) - for the tabulation array

Parameters:

Name	Type	Description	Default
`n`	`int`	Non-negative integer position in Fibonacci sequence	required

Returns:

Type	Description
`int`	The nth Fibonacci number

Raises:

Type	Description
`ValueError`	If n is negative

Examples:

>>> fibonacci_tabulated(0)
0
>>> fibonacci_tabulated(1)
1
>>> fibonacci_tabulated(100)
354224848179261915075

`is_fibonacci_number(num)`

Check if a given number is a Fibonacci number.

A positive integer is a Fibonacci number if and only if one of (5n^2 + 4) or (5n^2 - 4) is a perfect square.

Parameters:

Name	Type	Description	Default
`num`	`int`	Number to check	required

Returns:

Type	Description
`bool`	True if the number is a Fibonacci number, False otherwise

Examples:

>>> is_fibonacci_number(13)
True
>>> is_fibonacci_number(14)
False
>>> is_fibonacci_number(0)
True