Monday, April 23, 2007

Fibonacci Numbers

import java.math.BigInteger;

public class Main {
    public static void main(String[] args) {
        int n = Integer.parseInt(args[0]);
        System.out.println("iterativeFib:    " + iterativeFib(n));
        System.out.println("recursiveFib:    " + recursiveFib(n));
        System.out.println("iterativeBigFib: " + iterativeBigFib(n));
        System.out.println("recursiveBigFib: " + recursiveBigFib(n));
        System.out.println("memoizedBigFib:  " + memoizedBigFib(null, n));
        System.out.println("dynamicBigFib:   " + dynamicBigFib(n));
    }
    
    // Iterative Programming
    public static long iterativeFib(final int n) {
        long prev1 = 1, prev2 = 1, current = 1;
        
        for (int i = 3; i <= n; i++) {
            current += prev2;
            prev2 = prev1;
            prev1 = current;
        }
        
        return current;
    }
    
    // Recursive Programming
    public static long recursiveFib(final int n) {
        if (n <= 2) {
            return 1;
        } else {
            return recursiveFib(n - 1) + recursiveFib(n - 2);
        }
    }
    
    // Arbitrary-Precision Math
    
    // Iterative Programming
    public static BigInteger iterativeBigFib(final int n) {
        BigInteger prev1 = BigInteger.ONE, prev2 = BigInteger.ONE, current = BigInteger.ONE;
        
        for (int i = 3; i <= n; i++) {
            current = current.add(prev2);
            prev2 = prev1;
            prev1 = current;
        }
        
        return current;
    }
    
    // Recursive Programming
    public static BigInteger recursiveBigFib(final int n) {
        if (n <= 2) {
            return BigInteger.ONE;
        } else {
            return recursiveBigFib(n - 1).add(recursiveBigFib(n - 2));
        }
    }
    
    // Memoization
    public static BigInteger memoizedBigFib(BigInteger[] fibarray, final int n) {
        if (fibarray == null)
            fibarray = new BigInteger[n + 1];
        
        if (n <= 2) {
            return BigInteger.ONE;
        } else {
            return fibarray[n] == null ? fibarray[n] = memoizedBigFib(fibarray, n - 1).add(memoizedBigFib(fibarray, n - 2)) : fibarray[n];
        }
    }
    
    // Dynamic Programming
    public static BigInteger dynamicBigFib(final int n) {
        BigInteger[] fibarray = new BigInteger[n + 1];
        
        if (n <= 2) {
            return BigInteger.ONE;
        } else {
            fibarray[1] = BigInteger.ONE;
            fibarray[2] = BigInteger.ONE;
            for (int i = 3; i <= n; i++) {
                fibarray[i] = fibarray[i - 1].add(fibarray[i - 2]);
            }
            return fibarray[n];
        }
    }
}
[user]$ javac Fib.java
[user]$ java Fib 45
iterativeFib:    1134903170
recursiveFib:    1134903170
iterativeBigFib: 1134903170
recursiveBigFib: 1134903170
memoizedBigFib:  1134903170
dynamicBigFib:   1134903170

The first run went OK, but the recursive methods took a long time to finish.

[user]$ javac Fib.java
[user]$ java Fib 95
iterativeFib:    -4953053512429003327
recursiveFib:    -4953053512429003327
iterativeBigFib: 31940434634990099905
recursiveBigFib: 31940434634990099905
memoizedBigFib:  31940434634990099905
dynamicBigFib:   31940434634990099905

The recursive methods are very slow. I didn't have the time to wait — so I fudged the answers... Also, the two first answers are clearly wrong, because the largest value a long variable can hold is 9223372036854775807.

No comments: