Project Euler Problem #10

January 7, 2010

Read the details of the problem here

Summary

Calculate the sum of all the primes below two million.

Solution

Again, more of a programming challenge than a mathematical one – at least I’m unaware of a quick algebraic solution to this. I just used a simple sieve and then totalled up the primes.

def isPrime = new boolean[2000000]
Arrays.fill(isPrime, true)
isPrime[1] = false

for (int i in 2..isPrime.size()**0.5) {
    if (isPrime[i]) {
        def j = i + i
        while (j < isPrime.size()) {
            isPrime[j] = false
            j += i
        }
    }
}

def answer = 0L

for (i in 2..<isPrime.size()) {
    if (isPrime[i]) answer += i
}

This completes in 4.58 seconds with the sieve taking about 4.19 seconds (91%) of that. A BigInteger#isProbablePrime implementation takes far longer than the 15 seconds I’ve allowed for these solutions. Note that I’ve changed my sieve creation look from being a Java-like for (;;) construct that I’ve used before to a verbose while() loop. I found that the former was taking upwards of 7 seconds to run i.e. a 50% overhead for syntactic sugar. Given the runtime constraints I’ve imposed on these answers this wasn’t acceptable.

Conclusion

Groovy language features didn’t play much of a part in this solution. In fact, with the rather odd performance issue mentioned above they actually proved to be a detriment compared to a Java solution. Even at just 10 questions in, I can see that Groovy’s overheads in straight computational processing is likely to be an issue as I progress in the Euler problems – a Java implementation of this executes in 70 ms (65x faster).

Addendum

Added 26th July 2010

I don’t normally try to optimize when the runtime is comfortably within the 15 second cut off, but following on from a comment on this post I did a few more tests on speeding up the sieve generation. Here are the results:

Version Changes Normalized Runtime
1 As-Is 1.000
2 Change j=i+i to j=i*i 0.999
3 Change for-loop to while 0.965
4 Use an increment value 0.631
5 Take SQRT outside loop 0.563
6 Use LIMIT rather than isPrime.size() 0.244
7 Make JUST the LIMIT change 0.411

The change (2) to using a “j = i * i” rather than “j = i + i” make hardly any performance difference. Groovy is quite slow on multiplication compared to addition and this balances with the improvement that running fewer loops makes. The second main change (4), using a double increment after the initial pass, makes quite a difference (35%) as you’d might expect. Another big improvement (6) is using a constant (well, variable really) rather than getting the size() of the array each time. This saves 57% even after the other improvements, making a total of 76% overall. This change alone (7) saves a consistent amount (59%) when applied to the base code.

Advertisements

4 Responses to “Project Euler Problem #10”

  1. Hans Says:

    I think you can make this prime sieve much more efficient.
    E.g. look what you got after the first iteration in which all even numbers (except 2) are set to false:
    The numbers that are still set to true are:
    3,5,7,9,11,etc.
    So for the multiples of 3 you can start at 9 instead of 6.
    After sieving out the multiples of 3, you are left with:
    3,5,7,11,13,17,19,23,25, etc
    So the first multiple of 5 that has to be sieved out is 25.
    So in line 7 you can replace
    def j = i + i
    with
    def j = i*i.
    Secondly, in line 10 you write:
    j+=i.
    For i>2 this keeps sieving out even numbers that have allready been sieved out.
    So if you would a seperate loop for i=2 then for all odd primes line 10 can be replaced by j+=i+i.
    I’m sure that those two optimisations would make for a drastic increase in performance.

  2. keyzero Says:

    Hi Hans, You’re right, of course. I don’t normally bother to look for micro-optimisations if the solution runs comfortable within the 15 second limit. I’ve added something to the write up to reflect some additional possible speed-ups.

  3. ricardo Says:

    Groovy has a static version that runs equals to Java on speed, it is called Groovy++

  4. keyzero Says:

    Hi Ricardo,

    Thanks for that. I’d actually taken a look at G++ a while back but kind of discounted it as being unready. It’s not strictly a “version” of Groovy – it’s written by an independent team rather than being part of the main distribution.

    It’s an interesting project but I don’t think it’s got legs. The team are up against Scala, Clojure and, of course, Java itself in the statically typed world and I think that those languages, Scala especially, are getting significantly more traction. I’d love to be proved wrong but I suspect I won’t be.

    I’ll take a proper look at it when it gets to release 1.0 and is included in the main Groovy SDK.

    Trevor


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: