## 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:

// function getFib(n) returns a Fibonacci number at index n: F(n) 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:

// r = t2/t1 = 1 when n = 4 // r = t2/t1 = 2 when n = 8 // r = t2/t1 = 9 when n = 12 // r = t2/t1 = 490 when n = 20 // r = t2/t1 = 2753 when n = 30 // r = t2/t1 = 204865 when n = 40 // r = t2/t1 = 336496 when n = 41 ... 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:

// Add two arrays of the same size (size) // Each array is a representation of a natural number // The returned array will have the size of (size + 1) elements 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) { // Return F(n) in the form of an array, with (size + 1) elements int[] fibArr1 = new int[size]; int[] fibArr2 = new int[size]; int[] fibResultArr = new int [size + 1]; // Initially set up for (int i = 0; i < size; i++) { fibArr1[i] = fibArr2[i] = fibResultArr[i] = 0; } if (n == 0) { // return fibArr1; return (addTwoArrays(fibArr1, fibArr1)); } if (n == 1) { fibArr2[size - 1] = 1; // return fibArr2; return (addTwoArrays(fibArr1, fibArr2)); } /* // Do the Recursive way fibResultArr = addTwoArrays(getFibArray(n - 1, size - 1), getFibArray(n - 2, size - 1)); */ // Do the Iterative way 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) { // "0" returns "0", "0012" returns "12" 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) { // Return the biggest F(n) that has less than (size) character. String result = ""; int n = 0; // could have started with a 'near' value, such as 400 int[] fib; // getFibArray(n, size) has (size + 1) = 99 digits if (size == 2) return "8"; while (true) { fib = getFibArray(n, size - 2); if (fib[0] != 0) break; n++; } int low = n; // System.out.println("Low index is: " + low); // low = 472 = min F(n) that has 99 digits int[] fibAbove; while (true) { fibAbove = getFibArray(n, size - 1); if (fibAbove[0] != 0) break; n++; } int high = n; // System.out.println("High index is: " + high); // high = 477 = min F(n) that has 100 digits for (int i = low; i <= high; i++) { int[] f = getFibArray(i, size - 1); if (getStringOfIntArrayNum(f).length() >= size) { n = i - 1; // right before i that makes F(n) 100 digits 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.