///// Implement Fibonacci Sequence /////

package main.java;

import java.math.BigInteger;

public class Fibonacci { // naive public static long recursiveFibonacci(int n) { // if n < 0: throw new Exception

// if (n < = 1);

// return n

// return naive(n-1) + naive(n-2) return -1; }

// efficient public static long arrayFibonacci(int n) { // if n < 0: throw new Exception // if n <= 1;

// return n

// arr[0] = 0

// arr[1] = 1

// for i from 2 to n:

// arr[i] = arr[i-1] + arr[i-2]

// End for

// Return arr[n]

return -1; }

public static void main(String[] args) { int startingNumber = 43; for (int i = 0; i < 6; i++) { System.out.println("--------n = " + (startingNumber+i) + "--------"); long start = System.nanoTime(); long fib = recursiveFibonacci(startingNumber+i); long stop = System.nanoTime(); long timeElapsed = (stop - start) / 1_000_000_000; System.out.println(" naive: " + timeElapsed + "seconds");

long start2 = System.nanoTime(); long fib2 = arrayFibonacci(startingNumber+i); long stop2 = System.nanoTime(); long timeElapsed2 = (stop2 - start2) / 1_000; System.out.println(" efficient: " + timeElapsed2 + "microseconds");

if (fib == fib2) { System.out.println(" fibonacci number: " + fib); } else { System.err.println("!!!! The naive algorithm and the efficient algorithm produced two different numbers: " + fib + " and " + fib2); System.exit(1); }

System.out.println("----------------------"); }

} }