Project Euler 25 - 1000-digit Fibonacci Number

Question

I have recently completed problem 25 from the project Euler site.

The Fibonacci sequence is defined by the recurrence relation:

\$\qquad F_n = F_{n−1} + F_{n−2}\,ドル where \$F_1 = 1\$ and \$F_2 = 1\$.

Hence the first 12 terms will be:

\$\qquad F_1 = 1\$

\$\qquad F_2 = 1\$

\$\qquad F_3 = 2\$

\$\qquad F_4 = 3\$

\$\qquad F_5 = 5\$

\$\qquad F_6 = 8\$

\$\qquad F_7 = 13\$

\$\qquad F_8 = 21\$

\$\qquad F_9 = 34\$

\$\qquad F_{10} = 55\$

\$\qquad F_{11} = 89\$

\$\qquad F_{12} = 144\$

The 12th term, \$F_{12}\,ドル is the first term to contain three digits.

What is the first term in the Fibonacci sequence to contain 1000 digits?

I have solved this problem in Java, however, the execution time is fairly slow, and, I am looking for ways to improve it; below is my code, as well as the output given:

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>();
 boolean validNo = true;
 int x = 2;
 BigInteger tempAns = null;
 fibonacciNumbers.add(BigInteger.valueOf(1));
 fibonacciNumbers.add(BigInteger.valueOf(1));
 do {
 tempAns = fibonacciNumbers.get(x-1).add(fibonacciNumbers.get(x-2));
 fibonacciNumbers.add(tempAns);
 x++;
 if(tempAns.toString().length() >= 1000) {
 validNo = false;
 }
 } while (validNo == true);
 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");
 }
}

Output:

The first term in the Fibonacci sequence to contain 1,000 digits is term: 4782

Execution time: 220.858659 ms

I know that it is possible to solve this problem in C# in 2ms. I have provided the code for this solution below:

int i = 0;
int cnt = 2;
BigInteger limit = BigInteger.Pow(10, 999);
BigInteger[] fib = new BigInteger[3];
fib[0] = 1;
fib[2] = 1;
while (fib[i] <= limit) {
 i = (i + 1) % 3;
 cnt++;
 fib[i] = fib[(i + 1) % 3] + fib[(i + 2) % 3];
}

C# code sourced from here.

From looking at the C# code, the one thing which stands out to me, is maybe there is a better way to store the previous numbers than using an ArrayList?

• 200_success: The C# solution would also work in Java with very little modification. Why don't you do that instead?
• twohundredping: I have a few concerns about this question. Either the code or the output has been misrepresented in my opinion. I am not a Java coder but I can't imagine that tempAns.toString().length() >= 1000 does anything other than convert an integer to a string and then use the string length to determine the number of digits in the number. However, the output suggests the OP changed this value to 4 instead of 1000. The C# limit variable will overflow so I can't say that the output there was intentionally misrepresented.
• tsleyson: @twohundredping If I'm reading it correctly, it's saying that the 4872nd Fibonacci number is the first one that contains 1000 digits, not that 4872 is a Fibonacci number containing over 1000 digits. It prints the size of the list of Fibonacci numbers computed so far.
• twohundredping: And that's why I need to research before commenting on languages I don't use. I see now the max size of BigInteger is apparently \$(2^{32})^{Integer.MAX_VALUE}\$ which is more than big enough to compute 1000 digits. I just kind of assumed he was hitting an overflow and didn't bother to scroll over to see what was actually being printed. I'll leave my previous erroneous comment for shame and posterity.
• Raziman T V: As usual, the way to obtain quick solution for PE is to find a mathematical shortcut. Here what would help is the fact that $F_n \approx \frac{\phi^n}{\sqrt{5}}$. Using this, it is easy to find the solution without computing the Fibonacci numbers themselves

Answer 1

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");
 }
}

• Chris Hayes: Using time is troublesome because you include the virtual machine's startup time and things like class loading. That said, the huge issue with this code is the toString call. Getting rid of that - and not changing anything else - reduced my run from 550ms to 15ms. As usual, strings suck for performance.
• tsleyson: @ChrisHayes Yeah, it was somewhat crude to use time, but I just wanted to get a quick relative measurement; I wouldn't use it for a serious benchmark. I almost mentioned toString()--it seemed like there was something uncool there, but I didn't know enough about toString() on BigIntegers to explain what, so I refrained.