Project Euler 25 - 1000-digit Fibonacci Number

I translated the given C# code to Java, and timed it on my machine using the Unix time command. It ran in 0.161 seconds. Your original code ran in 1.023 seconds. Here's the Java translation of the C# code:

import java.math.BigInteger; public class Euler25 { public static void main(String[] args) { int i = 0; int cnt = 2; BigInteger limit = (new BigInteger("10")).pow(999); BigInteger[] fib = new BigInteger[3]; fib[0] = BigInteger.ONE; fib[2] = BigInteger.ONE; while ((fib[i]).compareTo(limit) < 0) { i = (i + 1) % 3; cnt++; fib[i] = fib[(i + 1) % 3].add(fib[(i + 2) % 3]); } System.out.printf("Fibonacci %d has 1000 digits\n", cnt); } } 

Not to be excessively negative, but the solution in the C# code is much cleaner than the one you implemented. No shame in that; it happens to all of us. But I assume you wanted some advice on making the code you have run faster, because if you just wanted to copy that C#, you easily could have. So that's the direction I'll go with the rest of the answer.

It honestly puzzles me that this code is so much faster than yours. I would have expected the BigInteger math to be the really slow part, but this code does the same amount of BigInteger math as your original code.

Your code does take quite a bit more memory, since it stores all the Fibonacci numbers it calculates, whereas this code only stores what it needs to calculate the next one, and uses an integer to count how many Fibonacci numbers it's seen so far. An array list is backed by an array, so actually accessing the items shouldn't be much slower than with a plain array, but there might be some kind of cache or memory allocation effect. With this code, the compiler can block out a single, static chunk of memory. In the original code, the ArrayList that stores Fibonacci numbers keeps on expanding, so the backing array might have to be reallocated several times. Every time the array is reallocated, everything stored in it has to be moved over to the new storage space, which is pretty slow if you have a big list. If that turns out to be the problem, you can try passing the ArrayList constructor a guess for big you think the list might get (the default size is ten).

If I were you, I would profile the code and look for some issue like that. Dig into the ArrayList implementation and see if it's spending a lot of time reallocating. Just see where the code is spending its time, and try to figure out why that's where it's spending its time. If you don't already have a profiler you like, Netbeans has a pretty good one built in, and I'm sure Eclipse and other Java IDEs also have them. If you profile and post some of your numbers, we can probably give you better help with diagnosing performance issues.

EDIT: @ChrisHayes discovered why the code is so much slower: it's the toString call. I took the original code and just replaced the toString call with a check against a limit of \$10^999\$ as the C# code does. Still used the array list, still stored all the Fibonacci numbers. As Chris Hayes observed, this reduced the runtime from about 900ms to about 13ms. The author of this blog post also found that BigInteger.toString() was quite slow. An answer on this page implies that BigIntegers are stored in a way that makes it easier to implement the BigInteger.toString(radix) method that lets you convert a BigInteger into other bases, like hexadecimal or ternary. One could apparently implement BigInteger in a more specific way that makes it quick to convert into a base-10 string, but difficult or impossible to convert into strings in other bases, but the standard library implementers chose a representation which was more general, but slower to convert into a string.

See the end of the answer for my final version of the code, including modifications I made to get rid of toString.

[/EDIT]

Aside from the performance issues, I had some readability issues—not that your code was unreadable, just that it was harder to read than it had to be, and that contributed a little to the confusion that we had over where the number 4872 was coming from. The biggest one is the variable x. Unless you're working with coordinate axes, please don't call variables x. The C# code gives the analogous variable the name cnt, which is better, since you can tell it's probably some kind of counter. In general, that C# code is quite clean, so it's a good model to learn from, though I'd probably just go all the way and call it count. n could also work, since it's traditional to index the Fibonacci numbers with n. (This is another reason why x is confusing; if I'm reading a program about Fibonacci numbers, I can process F_n or the like pretty easily, but F_x is just strange.)

I also found your use of the do-while loop with a boolean flag confusing. A for or while loop with a break statement would have been better, but I think the best would be to let the do-while work for you, and write something like this:

do { tempAns = fibonacciNumbers.get(n-1).add(fibonacciNumbers.get(n-2)); fibonacciNumbers.add(tempAns); n++; } while (tempAns.toString().length() < 1000); 

which takes advantage of the fact that tempAns gets initialized before the loop condition is checked.

The BigInteger class has built-in constants for zero and one, since they're so common. So you can initialize your array list like this:

fibonacciNumbers.add(BigInteger.ONE); fibonacciNumbers.add(BigInteger.ONE); 

It's a bit shorter than BigInteger.valueOf(1). (I like Java well enough, but it sure can get long.)

Here's the entire code sample with my suggested changes, including the one that eradicates toString and boosts performance that Chris Hayes suggested:

import java.util.ArrayList; import java.math.BigInteger; public class ProjectEuler25 { public static void main(String [] args) { long start = System.nanoTime(); ArrayList<BigInteger> fibonacciNumbers = new ArrayList<BigInteger>(); int n = 2; // Index of current Fibonacci number. BigInteger tempAns = null; BigInteger limit = new BigInteger("10").pow(999); // First 1000-digit number. fibonacciNumbers.add(BigInteger.ONE); fibonacciNumbers.add(BigInteger.ONE); do { tempAns = fibonacciNumbers.get(n-1).add(fibonacciNumbers.get(n-2)); fibonacciNumbers.add(tempAns); n++; } while (tempAns.compareTo(limit) <= 0); Long stop = System.nanoTime(); System.out.println("The first term in the Fibonacci sequence " + " to contain 1,000 digits is term: " + fibonacciNumbers.size()); System.out.println("Execution time: " + ((stop - start) / 1e+6) + " ms"); } }