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>