Computing huge Fibonacci numbers in Java

Question

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?

Answer 1

Your biggest problem that you use char. If you replace it to byte you can save lot of work on converting.

Next performance problem is List. If you use array it will work lot faster.

Next you work in base 10. Try base 256 it will save you lot of work again (but make conversion to string more complex).

And one more thing to mention: you using not most effective algorithm to compute Fibonacci number. Look at this It is a lot of math in explanation but actual algorithm is pretty simple.

Here is code example for fast Fibonacci available.

Answer 2

    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();

Lots of fancy comments. Let's take em out so I can look at the actual code.

    StringBuilder sb;

    if (fromAtoB) {
        sb = new StringBuilder(listA.size());

        for (int i = listA.size() - 1; i >= 0; --i) {
            sb.append(listA.get(i));
        }
    } else {
        sb = new StringBuilder(listB.size());

        for (int i = listB.size() - 1; i >= 0; --i) {
            sb.append(listB.get(i));
        }
    }

    return sb.toString();

Seems all you do here is getting a string... from either listA or listB. I'd recommend putting this in a separate function...

public static String convertDigitListToString(List<Character> list){
    StringBuilder sb = new StringBuilder(list.size());

    for (int i = list.size() - 1; i >= 0; --i) {
        sb.append(list.get(i));
    }
    return sb.toString();
}

And then you can simplify your code a bit.

if (fromAtoB) {
    return convertDigitListToString(listA);
} else {
    return convertDigitListToString(listB);
}

Maybe even a ternary? I dunno about that, though. It's shorter, but a bit more harder to read.

return convertDigitListToString(fromAtoB ? listA : listB);

The real reason it's hard to read is because fromAtoB is a pretty bad description... in this case, you're looking for something like lastListUsed... but that doesn't really fit the description either.

---

    if (n < 0) {
        throw new IllegalArgumentException("n = " + n);
    }

You might want to give a more descriptive message, like "n must be positive", or "expected positive n, got ".