I have this small Java program for computing particurly large Fibonacci numbers (10000th Fibonacci number is computed in about 220 milliseconds). The key idea here is to use lists of digits, which is exactly what is done in java.math.BigInteger
, yet I wanted to implement a simple digit list addition on my own.
import java.util.ArrayList;
import java.util.List;
public class Main {
public static String fibonacci(int n) {
if (n < 0) {
throw new IllegalArgumentException("n = " + n);
}
switch (n) {
case 0:
return "0";
case 1:
return "1";
}
List<Character> listA = new ArrayList<>();
List<Character> listB = new ArrayList<>();
listA.add('0');
listB.add('1');
boolean fromAtoB = true;
for (int i = 0; i < n; ++i, fromAtoB = !fromAtoB) {
if (fromAtoB) {
add(listA, listB);
} else {
add(listB, listA);
}
}
StringBuilder sb;
if (fromAtoB) {
// It looks like the result is in the listB. However, as the boolean
// fromAtoB was flipped after the last add(list1, list2), the result
// is actually in list A.
sb = new StringBuilder(listA.size());
// For efficiency, we grow the digit string such that the least
// significant digits are in the lowest array positions. That way
// we make sure that adding a new (most significant digit) always
// runs in amortized constant time.
for (int i = listA.size() - 1; i >= 0; --i) {
sb.append(listA.get(i));
}
} else {
// Result is in listB.
sb = new StringBuilder(listB.size());
for (int i = listB.size() - 1; i >= 0; --i) {
sb.append(listB.get(i));
}
}
return sb.toString();
}
// Adds the number represented by digit list 'from' to the number
// represented by digit list 'to'.
private static void add(List<Character> from, List<Character> to) {
// The carry flag.
boolean carry = false;
if (to.size() < from.size()) {
// Extend the target digit list so that it can accommodate most of
// the digits of the sum of the two Fibonacci numbers.
to.add('0');
}
for (int i = 0; i < from.size(); ++i) {
int digit = charToInt(from.get(i)) +
charToInt(to.get(i)) +
(carry ? 1 : 0);
if (digit > 9) {
digit -= 10;
carry = true;
} else {
carry = false;
}
to.set(i, intToChar(digit));
}
if (carry) {
to.add('1');
}
}
private static int charToInt(char c) {
return (int)(c - '0');
}
private static char intToChar(int i) {
return (char)(i + '0');
}
public static void main(String[] args) {
Integer i = -1;
if (args.length > 0) {
try {
i = Integer.parseInt(args[0]);
} catch (NumberFormatException ex) {
}
}
long startTime = System.currentTimeMillis();
String number = fibonacci(i >= 0 ? i : 10);
long endTime = System.currentTimeMillis();
System.out.println(number);
System.out.println((endTime - startTime) + " milliseconds.");
}
}
So what do you think?