Fall 2024 - P2
Big Idea 3 | .1 | .2 | .3 | .4 | .5 | .6 | .7 | .8 | .10 |
3.3.4 Mathematical Expressions (P2)
Student led teaching on Mathematical Expressions. Learn how mathematical expressions involve using arithmetic operators (like addition, subtraction, multiplication, and division) to perform calculations
Challenge: Try to implement more than one algorithm for the Fibonacci sequence
#Python: Fibonacci Using Matrix Exponentiation
import numpy as np
import logging
import sys
# Configure logging
logging.basicConfig(level=logging.INFO, format='%(levelname)s:%(message)s')
def matrix_multiply(A, B):
"""
Perform matrix multiplication between two numpy arrays A and B.
"""
logging.debug(f"Multiplying matrices:\n{A}\n{B}")
return np.dot(A, B)
def matrix_power(M, power):
"""
Raise matrix M to the specified power using binary exponentiation.
"""
if power < 0:
raise ValueError("Power must be a non-negative integer.")
result = np.identity(len(M), dtype=object)
logging.debug(f"Initial identity matrix:\n{result}")
while power > 0:
if power % 2 == 1:
result = matrix_multiply(result, M)
logging.debug(f"Result after multiplying by M:\n{result}")
M = matrix_multiply(M, M)
logging.debug(f"Matrix M squared:\n{M}")
power = power // 2
logging.debug(f"Power reduced to: {power}")
return result
def fibonacci_matrix(n):
"""
Calculate the nth Fibonacci number using matrix exponentiation.
"""
if not isinstance(n, int):
raise TypeError("Input must be an integer.")
if n < 0:
raise ValueError("Fibonacci number is not defined for negative integers.")
elif n == 0:
return 0
elif n == 1:
return 1
F = np.array([[1, 1],
[1, 0]], dtype=object)
result = matrix_power(F, n-1)
logging.info(f"Matrix raised to power {n-1}:\n{result}")
return result[0][0]
def validate_input(user_input):
"""
Validate the user input to ensure it's a non-negative integer.
"""
try:
value = int(user_input)
if value < 0:
raise ValueError
return value
except ValueError:
raise ValueError("Please enter a valid non-negative integer.")
def main():
"""
Main function to execute the Fibonacci calculation.
"""
try:
user_input = input("Enter the position of the Fibonacci number you want to calculate: ")
n = validate_input(user_input)
fib_n = fibonacci_matrix(n)
print(f"Fibonacci number at position {n} is: {fib_n}")
except ValueError as ve:
logging.error(ve)
except Exception as e:
logging.error(f"An unexpected error occurred: {e}")
sys.exit(1)
if __name__ == "__main__":
main()
INFO:Matrix raised to power 3:
[[3 2]
[2 1]]
Fibonacci number at position 4 is: 3
%%javascript
2. Java: Fibonacci Using Dynamic Programming
public class FibonacciDP {
// Method to calculate Fibonacci using dynamic programming with optimized space
public static long fibonacci(int n) {
// Base cases for Fibonacci
if (n == 0) return 0;
if (n == 1) return 1;
// Variables to store previous two Fibonacci numbers
long prev1 = 1, prev2 = 0;
long current = 0;
// Iteratively calculate Fibonacci
for (int i = 2; i <= n; i++) {
current = prev1 + prev2;
prev2 = prev1;
prev1 = current;
}
return current;
}
// Efficient matrix exponentiation approach (O(log n))
public static long fibonacciMatrix(int n) {
if (n == 0) return 0;
long[][] F = { { 1, 1 }, { 1, 0 } };
power(F, n - 1);
return F[0][0];
}
// Helper method to perform matrix exponentiation
private static void power(long[][] F, int n) {
if (n == 0 || n == 1) return;
long[][] M = { { 1, 1 }, { 1, 0 } };
power(F, n / 2);
multiply(F, F); // Square the matrix
if (n % 2 != 0) multiply(F, M); // Multiply by M if n is odd
}
// Matrix multiplication helper
private static void multiply(long[][] F, long[][] M) {
long x = F[0][0] * M[0][0] + F[0][1] * M[1][0];
long y = F[0][0] * M[0][1] + F[0][1] * M[1][1];
long z = F[1][0] * M[0][0] + F[1][1] * M[1][0];
long w = F[1][0] * M[0][1] + F[1][1] * M[1][1];
F[0][0] = x;
F[0][1] = y;
F[1][0] = z;
F[1][1] = w;
}
public static void main(String[] args) {
int n = 50;
// Using dynamic programming with optimized space
System.out.println("Fibonacci number at position " + n + " using DP is: " + fibonacci(n));
// Using matrix exponentiation (O(log n))
System.out.println("Fibonacci number at position " + n + " using Matrix Exponentiation is: " + fibonacciMatrix(n));
}
}
<IPython.core.display.Javascript object>