Project Euler Problem #3

November 5, 2009

Read the details of the problem here

Summary

What is the largest prime factor of the number 600851475143?

Solution

Pretty straightforward question with a straightforward brute force answer.

The code simply uses a naïve Sieve of Eratosthenes to generate primes up to the  square root of the target number “n” and then factorises from that sieve.

long n = 600851475143L
def isPrime = new boolean[Math.sqrt(n)+1]
Arrays.fill(isPrime, true);
isPrime[1] = false

for (int i in 2..Math.sqrt(isPrime.size())) {
    if (isPrime[i]) {
        for (j = i + i; j < isPrime.size(); j += i) isPrime[j] = false
    }
}

def (answer, i) = [ 0, 2 ]
while (n > 1) {
    if ((isPrime[i]) && (n % i == 0)) {
        ( n, answer ) = [ n / i, i ]
    }
    i++
}

It’s all very quick to write but look at the explicit typing in the declaration of “n”. Without this the “n / i” calculation in the factorisation loop will assign a BigDecimal to n which will then fail on the next mod operation. It is also possible to work around this feature by casting the result but the typing approach is probably the lesser of two evils.

The script completes in 3.44 seconds, the sieve creation itself taking 3.36 seconds. This seems extremely slow. Porting this over into classic Java it returns in 32 ms with the sieve creation taking 31 ms. That’s 100 times faster.

A simpler solution, without the sieve and relying on the BigInteger#isProbablePrime method returns in 1.21 secs, whereas the Java version of this takes 0.87 secs showing only a 40% overhead (which still seems quite significant).

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.

The fact that doing calculations like this means that the developer has to be aware of the types of the variables isn’t really a big deal but does suddenly make you aware that you’re not running in a real typeless environment like Ruby or Python. The runtime error message I received, “Cannot use mod() on this number type: BigDecimal” was a bit of a surprise and emphasises how much testing is necessary with dynamically typed languages where the number types can differ in the operations they support.

It appears from this that Groovy is imposing quite a severe overhead, adding some two orders of magnitude to 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.

For the BigInteger#isProbablePrime solution (shown below), Groovy does provide for a much cleaner syntax than the Java version in which it’s obvious that the BigInteger class has been grafted on and, without operator overloading being available, is a bit of a stranger in a strange land.

def n = 600851475143L
def (answer, i) = [ 0, 2G ]
while (n > 1) {
    if (i.isProbablePrime(100) && (n % i == 0)) {
        ( n, answer ) = [ n.intdiv(i), i ]
    }
    i++
}

See how easy it is to make “i” a BigInteger simply by appending a “G” to the value assignment. So it’s still necessary to be aware of the type, but this makes it easier than having to explicitly “new” a BigInteger.

The timings for this non-sieve solution show that, for large numbers of primes to be checked it’s almost always preferable to use a sieve in Java, whereas in Groovy there’s a higher tolerance given the overhead of building that sieve.

I did also find that using Number#intdiv successfully sidesteps the explicit long definition.

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: