fibonacci

import java.math.BigInteger;

public class Fibonacci{

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		long startTime = System.currentTimeMillis();
		System.out.println(RecFeb(129));
//		System.out.println(IteFib(229));

		long endTime = System.currentTimeMillis();
		double elapsedSeconds = (endTime-startTime)/1000.0;
		System.out.println("elapsed time: " + elapsedSeconds);
	}

	static BigInteger RecFeb(int n){
		if(n==1) {
			return BigInteger.ONE;
		}else if(n==2) {
			return BigInteger.ONE;
		}else {
			BigInteger result = BigInteger.ZERO;
			result = result.add(RecFeb(n-1)).add(RecFeb(n-2));
			return result;
		}
	}

	static BigInteger IteFib(int n) {
        BigInteger result = BigInteger.ONE;
        BigInteger n1 = BigInteger.ONE;
        BigInteger n2 = BigInteger.ONE;

        for (int i = 3; i <= n; i++) {
        	result = n1.add(n2);
        	n1 = n2;
        	n2 = result;
        }

        return result;

	}
}