Introduction
Fibonacci numbers are defined as:
F(n) = F(n-1) + F(n-2) with F(1) = 1 and F(0) = 0
The recursive approach
This is the easiest, but most inefficient way to calculate Fibonacci number:
public static long getFibRecursive(int n) {
if (n == 0) return 0;
if (n == 1) return 1;
return getFibRecursive(n-1) + getFibRecursive(n-2);
}
The iterative approach
When n becomes bigger, this approach is better than the recursive approach:
public static long getFibIterative(int n) {
if (n == 0) return 0;
if (n == 1) return 1;
int first = 0;
int second = 1;
int result = 0;
for (int i = 0; i < n - 1; i++) {
result = second + first;
first = second;
second = result;
}
return result;
}
Compare running time
Test the method compareRunningtime(int n) included in the demo, the ratios of running time t1 when use recursive method and t2 when use iterative method are approximately as follow:
...
Computer becomes real slow calculating the next F(n), and is about to run out of memory.
A better approach
When we want to calculate a 'big' F(n), one way is to represent F(n) in the form of an array. Each element of this array is a corresponding digit of F(n).
With this approach, we will need a custom way to add such two arrays:
private static int[] addTwoArrays(int[] arr1, int[] arr2) {
int size = arr1.length;
int[] arrTotal = new int[size + 1];
for (int i = 0; i < size; i++) {
arrTotal[i] = 0;
}
int remaider = 0;
for (int i = size - 1; i >= 0; i--) {
int temp = arr1[i] + arr2[i] + remaider;
arrTotal[i + 1] = temp % 10;
remaider = temp / 10;
}
arrTotal[0] = remaider;
return arrTotal;
}
Now we can combine this 'array approach' and iterative approach to calculate an Fibonacci with the number of digits can be 100 or more:
private static int[] getFibArray(int n, int size) {
int[] fibArr1 = new int[size];
int[] fibArr2 = new int[size];
int[] fibResultArr = new int [size + 1];
for (int i = 0; i < size; i++) {
fibArr1[i] = fibArr2[i] = fibResultArr[i] = 0;
}
if (n == 0) {
return (addTwoArrays(fibArr1, fibArr1));
}
if (n == 1) {
fibArr2[size - 1] = 1;
return (addTwoArrays(fibArr1, fibArr2));
}
fibArr2[size - 1] = 1;
for (int i = 0; i < n - 1; i++) {
fibResultArr = addTwoArrays(fibArr1, fibArr2);
fibArr1 = fibArr2;
int[] fibArr2Temp = new int[fibArr2.length];
for (int j = 0; j < fibArr2.length; j++) {
fibArr2Temp[j] = fibResultArr[j + 1];
}
fibArr2 = fibArr2Temp;
}
return fibResultArr;
}
Extra task:
This is a program assigment asks to find the biggest number thas has less than, 100 digits, for example.
Plan: We will write a function getBiggestFib(int size) that returns a String representation of the biggest Fibonacci number that has less than size digits.
We already have the function getFibArray(int n, int size) that returns a F(n) in the form of an array with size + 1 elements. Use this returned Fibonacci number, we can transform it into a String and remove leading zeros appropriately.
Remove leading zeros:
private static String removeLeadingZeros(String s) {
if (s.length() < 2)
return s;
int i;
for (i = 0; i < s.length() - 1; i++) {
char c = s.charAt(i);
if (c != '0')
break;
}
if (i == 0) {
return s;
}
return s.substring(i);
}
All the supported functions have been finished. Now to find that 'biggest' F(n). This might not be the best way to do, but I find it easy to follow. The idea is to find the 'smallest' F(n) that has size - 1 digits and the 'smallest' F(n) that has size digits. Then find that specific F(n) in this range.
private static String getBiggestFib(int size) {
String result = "";
int n = 0;
int[] fib;
if (size == 2)
return "8";
while (true) {
fib = getFibArray(n, size - 2);
if (fib[0] != 0)
break;
n++;
}
int low = n;
int[] fibAbove;
while (true) {
fibAbove = getFibArray(n, size - 1);
if (fibAbove[0] != 0)
break;
n++;
}
int high = n;
for (int i = low; i <= high; i++) {
int[] f = getFibArray(i, size - 1);
if (getStringOfIntArrayNum(f).length() >= size) {
n = i - 1;
break;
}
}
result = getStringOfIntArrayNum(getFibArray(n, size - 1));
return result;
}
Note
This is a program assignment in the 'Design and Analysis of Algorithms' class, so related Java APIs, such as BigNum, was not used.
Source file