Using Java

The Fibonacci number sequence is set up so that it starts with the numbers 1 and 1, and every number after that is the sum of its two immediate predecessors. Therefore, the sequence is: 1,1,2,3,5,8,13, . . .

The sequence is said to occur in various stages of nature, for example in counting the number of ancestors of a male bee, in the spacing of planets, in the arrangement of leaves on many plant stems, and in other applications.

Your programming assignment has three main parts. In the first two parts, youll write programs to calculate the nth number in the Fibonacci sequence using two different approaches. For example, if the user enters the number 4, youll return 3 since that is the 4^th number (after 1, 1, and 2). For both approaches, youll measure how long it takes the program to perform the calculation, and in the third part, youll record those measurements for comparison.

(Note that once the answer is above about 2 billion, an int cant hold the correct value. Youll instead get wildly wrong answers (maybe very negative or quite positive). For this assignment thats just fine, since were only measuring the amount of time it takes.)

Measuring Program Time

You should measure the time between starting the calculation and getting the answer. Make sure you dont start the clock until after getting the users input: you dont want to measure how fast or slow the user is at typing in the information. Youll then display the calculation time in milliseconds.

In Java, use the method System.currentTimeMillis(). This returns the number of milliseconds since 1970. By getting the number from the start and then the end, you can subtract the two to calculate the duration.

Part I

Code the Java program to use a recursive algorithm to compute the Nth Fibonacci term for a user. For example, note that the 5^th number in the sequence can be computed based on the 3^rd number and the 4^th number. Each number should be computed recursively, down until any base case(s). Name this program with your first Initial and last name, then Fib1.

Part II

Code the Java program to use an iterative loop, rather than recursion. This should start with the first two numbers and calculate forward until the desired index is reached. Name this program with your first Initial and last name, then Fib2

Part III

Test out both programs with the following inputs: 5, 10, 50, 100, 500, 1000 (if you dont get a result in roughly one minute, stop the program rather than waiting for it to complete). What durations are displayed?