Question

Problem Statement

Read and understand “The Bigger Picture” section on page 337. Be ready to explain why or how the various solutions are different. After you get the code for “public class FibTester”, which starts on page 341 to work, experiment with different numbers (I recommend keeping n<=50). Copy paste your programs printed result into Excel. Use Excel to subtract the start time from the end time and calculate the time each version took. Sample is shown below. Explain how everything works step by step.

millsec n 40 millsec n-45 millsec millsec n-50 1.51181E+12 n30 2 3 fib1 832040 4 5 fib3 832040 1.51181E+12 1.51181E+12 1.51181E+12 0 fib1 102334155 0 fib1 1134903170 1 fib1 12586269025 1 1.51181E+12 1.51181E+12 1.51181E+12 1.51181E+12 0 fib3 102334155 0 fib3 1134903170 0 fib3 12586269025 1 1.51181E+12 1.51181E+12 1.51181E+12 1.51181E+12 7 fib2 832040 12 ib2 102334155 2,650 ib2 1134903170 20,824 fib2 12586269025 227,800 1.51181E+12 1.51181E+12 1.51181E+12 1.51181E+12

Answer 1

Solution:

Algo 1 explanation:

It all starts with number 1 and 2.

1 + 2 = 3 is the next fib number achieved by initializing the first 2 numbers.

Thereafter previous 2 numbers are stored in variableshighest (3) and next_highest (2)and then sum of those two will be calculated in a loop for desired number of times. 2 + 3 = 5 (next fib number).

Similary 5 + 3 = 8 (next fib number).

Here, we are making use of results of previous fib number (which are already computed) and avoiding any recomputation (except 1 addition per fib number).

Algo3 - it is a recursive version of algo1.

Algo2 (fib2), it essentially calculates fib of a number by summing up fib of previous number and fib of 2nd previous number. A point to note here is that every time it calculates fib of a number, it needs to calculate fib of previous 2 numbers which also uses the same fib alogrithm.

Suppose we want to calcualte fib(6), logic is

fib(6) = fib(5) + fib(4)

fib(5) = fib(4) + fib(3) will be calculated separately for fib(5) (1st parameter) and

for fib(4) = fib(3) + fib(2) will be calculated separately for fib(4) (2nd parameter)

Note: Even though we have computed fib(4) for 2nd parameter, it again needs to be recomputed for fib(5) as well since we are not storing any fib computation values. Now imagine this for larger numbers ! This is the reason, the time taken for larger numbers increases exponentially.