Project Euler Problem #2

October 16, 2009

Read the details of the problem here

Summary

Find the sum of all the even-valued terms in the Fibonacci sequence which do not exceed four million.

Solution

Remember that the Fibonacci sequence, whereby the next number in the sequence is the sum of the previous two elements, gives this series:

x, y, x + y, x + 2y, 2x + 3y, 3x + 5y, …

I need to capture the even-valued elements, i.e. every third element, where the summed multipliers of x & y is even…or I can just add the two previous elements and skip every third element. In the sequence above the “x+y” element would get missed out.

def (x, y, answer) = [ 1, 1, 0 ]

while (y < 4000000) {
  answer += (x + y)
  (x, y) = [ x + 2*y, 2*x + 3*y ]
}

This runs in 0.33 seconds. Again really not as fast as I might expect, in fact, pretty slow. So I tried it out in straight Java…a similar solution coded in Java (and using a temporary variable rather than the multiple assignment syntax available in Groovy) runs in 0.0000006 seconds (0.6 microseconds). Interesting.

I could have just generated Fibonacci sequence normally and used "element & 1” or “element % 2” to see if it was even. A solution like that is fractionally quicker at 0.30 secs in Groovy as there’s less math going on.

Conclusion

Groovy didn’t actually add much to this solution apart from removing the boilerplate class code that Java required (and that IDEs generate automatically so it’s not much of a saving). The multiple assignment syntax was nice but nothing that I couldn’t have done without.

It appears from this that Groovy is imposing quite a severe overhead around numerical processing. If I need to do any real number crunching it’ll be best to create a proper Java helper class and use it from the Groovy script.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: