Click here to Skip to main content
14,971,215 members
Articles / Programming Languages / Java
Article
Posted 6 Sep 2013

Tagged as

Stats

22K views
67 downloads
3 bookmarked

Big Fibonacci numbers

Rate me:
Please Sign up or sign in to vote.
5.00/5 (1 vote)
6 Sep 2013CPOL2 min read
a look at calculations, running time, and implementation as an array of digits

Introduction

Fibonacci numbers are defined as:

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

Java
// 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:

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

Java
// 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:

Java
// 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:

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

Java
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.

Java
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

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Share

About the Author

Lộc Nguyễn
Software Developer
United States United States
while (live) {
try {
learn();
code();
food();
...
} catch (Exception ex) {
recover();
}
}

Comments and Discussions

 
-- There are no messages in this forum --