Transcript Problem Set 5: Problem 2

Problem Set 5: Problem 2
22C:021 Computer Science
Data Structures
What needs to be done?
•
Implement a Fibonacci Number Generator
–
•
Implement an optimized Fibonacci number
generator
–
•
A naive Fibonacci number generator
That remembers results of sub-problems already solved
Evaluate Performance
Fibonacci Number Generator:
Naive
public static int fibonacci(int n)
{
if((n == 1) || (n == 2))
return 1;
else
return fibonacci (n-1) + fibonacci (n-2);
}
Fibonacci Number Generator:
Optimized
•
We need:
–
–
An array “answers” that stores results of solved subproblems
A type that can handle large numbers
●
–
–
Fibonacci numbers grow fast, integers and longs run out of
range
A way to check if a sub-problem has already been
solved
Only need to recurse when necessary
The BigInteger Data Type
•
•
Available under java.util namespace
Can store really large values
–
Check Java Documentation for more Details about this
type
●
http://java.sun.com/j2se/1.4.2/docs/api/java/math/BigInteger.
html
The “answers” array
•
What should be the size of the “answers” array
–
–
The size n of this array should be equal to the
Fibonacci number we've been asked to generate
This array stores the nth Fibonacci number at n-1th
Location
private static BigInteger[] answers;
Initialize the “answers” array
// Initializing answers
int number = <fibonacci number to generate>;
answers = new BigInteger[number];
// The first two numbers in series are 1
answers[0] = new BigInteger("1");
answers[1] = new BigInteger("1");
// Set all others to zeros to mark them as
// not-computed
for(int i = 2; i < number; i++)
answers[i] = new BigInteger("0");
Optimized Fibonacci Number
Generator
public static BigInteger fastFibonacci(int n)
{
if((n == 1) || (n == 2))
return answers[0];
if(answers[n-1].compareTo(zero) != 0)
return answers[n-1];
if(answers[n-2].compareTo(zero) == 0)
answers[n-2] = fastFibonacci(n-1);
if(answers[n-3].compareTo(zero) == 0)
answers[n-3] = fastFibonacci(n-2);
return answers[n-2].add(answers[n-3]);
}
Optimized Fibonacci Number
Generator
•
When asked to generate a number
–
–
–
–
–
We check if the number requested has already been
computed and return it if it has been.
Then, we check if the required numbers have already
been computed (n – 1 and n - 2)
If they have, we straightaway use their values
If they haven't, we call the generator number on each
of the missing required numbers
Once we have both the value, we add them and return
the sum
Performance Comparisons
•
How fast is the optimized version?
–
To generate the 46th Fibonacci Number
●
●
The unoptimized version takes 885490.7 ms = Approx 15
minutes
The optimized version takes 0.145 ms
Performance Comparison
1e+07
Naive
Optimized
1e+06
100000
10000
1000
100
10
1
0.1
0.01
5
10
15
20
25
30
Fibonacci Number
35
40
45
50
Other Performance Stats
•
The Optimized version takes
–
–
•
For 100th Number: 0.329 ms
For 1000th Number: 5.172 ms
The Naive version takes
–
So long that I did not evaluate ...