package javahomework;

import javax.swing.JOptionPane;

public class HW02 {

	/**
	 * @param args
	 */
	public static void main(String args[]) {
		JOptionPane.showMessageDialog(null, "The Number bigger than 100000 is "
				+ fib_slow(100000) + "th");
		JOptionPane.showMessageDialog(null, "The Number bigger than 100000 is "
				+ fib_quick(100000) + "th");
	}

	/**
	 * FIB use recursive
	 * 
	 * @param big_number
	 * @return big than big_number is
	 */
	public static int fib_slow(long big_number) {
		long f = 1;
		int ans = 0;
		for (long i = 0; f < big_number; i++) {
			f = fib(i);
			ans++;
		}
		return ans;
	}

	public static long fib(long n) {
		if (n == 0 || n == 1)
			return n;
		else
			return (fib(n - 2) + fib(n - 1));
	}

	/**
	 * FIB not use recursive
	 * 
	 * @param number
	 * @return big than big_number is
	 */
	public static int fib_quick(long number) {
		long a, b, c;
		/* A[0]=0,A[1]=1 has been count in first time, so ans=2*/
		int ans = 2;
		a = 0;
		b = 1;
		c = a + b;
		while (c < number) {
			/* A[n+2]=A[n]+A[n+1]; */
			c = a + b;
			/* next ...., let A be a=A[n+1],b=A[n+2] */
			a = b;
			b = c;
			ans++;
		}
		return ans;
	}

}