Big Fibonacci numbers

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.

Source file