Project Euler Problem #12

January 27, 2010

Read the details of the problem here

Summary

What is the value of the first triangle number to have over five hundred divisors?

Solution

This one gave me problems. Not so much from a programming a suitable solution, but in getting adequate performance from Groovy to meet my 15 second deadline. The algorithm I first came up with was a simple brute force one, with the only slight optimisation being to only check up to the square root of the number and compensate for the off-by-one error in the event that the number is itself a perfect square.

def (answer, triangle_num, i) = [ 0, 0, 0 ]

while (answer == 0) {
    i++
    triangle_num += i
    def ( sqrt_num, divisors ) = [ (int)(triangle_num ** 0.5), 0 ]
    for (j in 1..sqrt_num) {
        if (triangle_num % j == 0) divisors += 2
    }
    if (sqrt_num ** 2 == triangle_num) divisors -= 1
    if (divisors > 500) answer = triangle_num
}

This ran in 54.6 seconds spending most of its time, as you might expect, in the inner loop. Dreadful. An equivalent Java version runs in 6.44 seconds using Longs, 4.67 seconds using longs and 0.84 seconds using ints, so it can be argued that, for this purpose, Groovy is anything between 8.5-65x slower than native Java code depending on how charitable one is feeling.

Note that it is possible to rewrite that inner loop as a one-liner using Groovy’s listops (as shown below) but this pushes the runtime out to a frighteningly poor 214 seconds (4x slower) so the least said about that probably the better.

divisors = (1..sqrt_num).sum { triangle_num % it == 0 ? 2 : 0 }

Replacing the inner for-in loop with a while-loop pushed the runtime out to 96.2 seconds, nearly doubling it. That’s pretty dreadful too! There’s no way that such a change should have such a significant impact on the performance. (Unfortunately changing the outer loop to a for-in and then breaking out of it, only had a neglible benefit.)

My algorithm wasn’t good enough for Groovy’s limitations. The problem was that I was spending far too much time in the inner loop. Although I was only checking up to the square-root of the number, for the magnitude of numbers here, that was still quite significant. So, back to first principles – I had to try to factor smaller numbers.

The Nth triangle number are created using the formula n*(n+1)/2. As n and n+1 won’t have any factors in common I can just factorize the two components and then multiply their results together. I don’t want to factorize any fractional numbers, so I need to take the /2 onto the even element of either n or n+1 and factorize either n/2 & n+1, for even values of n, or n & (n+1)/2, for odd values of n. As these values should be much smaller than the triangular numbers I was factorizing before, it should be much faster.

def divisors(num) {
    def count = 0
    def sqrt_num = (int)(num ** 0.5)
    for (i in 1..sqrt_num) {
        if (num % i == 0) count += 2
    }
    if (sqrt_num ** 2 == num) count -= 1
    return count
}

def (answer, i) = [ 0, 0 ]

while (answer == 0) {
    i++
    if ( ((i % 2 == 0) ? divisors(i.intdiv(2)) * divisors(i + 1)
                       : divisors(i) * divisors((i + 1).intdiv(2))) > 500)
        answer = (i * (i + 1)).intdiv(2)
}

Note the intdiv() function calls to make sure that results don’t get inadvertently converted to BigDecimals which would cause the mod function in the divisors() method to fail.

This ran in 2.18 seconds so completely within my 15 second target. I went on to memoize the divisors() function, though this was really unnecessary in this case, and the runtime dropped to 1.3 seconds. A Java version of this (based on ints) provides the answer in 53 ms, a memoized version in 37ms – Java remaining 35x-40x faster than the Groovy “equivalent”.

Conclusion

Groovy just isn’t any good at these problems that require significant computational resource, so you just have to try and reduce the amount of calculation you’re trying to get it to do! It’s tempting to use the language features of Groovy to get the code down quickly but, for truly performant code, sometimes it’s best not to rush into it. In this case, if I’d gone the Java route immediately and abandoned Groovy I’d have ended up with a solution that, at 840ms, was still 20x slower than the 37ms Java version that I ended up with here.

Advertisements

2 Responses to “Project Euler Problem #12”


  1. […] me dire que 4 minutes 30, c’est beaucoup. C’est vrai. Surtout en comparaison de cet exemple qui met, lui, 54 secondes pour faire le même boulot. Seulement, si vous regardez mon code, là […]


  2. […] qu'ailleurs sur internet, d'autres ont trouvé la solution – en groovy – en moins d'une minute. Surtout (enfin) quand je sais (toujours grâce à ce collègue) que la solution est 76576500. Et […]


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: