Project Euler Problem #80

January 21, 2010

Read the details of the problem here

Summary

For the first one hundred natural numbers, find the total of the digital sums of the first one hundred decimal digits for all the irrational square roots.

Solution

My initial thought on this was that Java’s BigDecimal class would offer a high-precision square root method but, but my disappointment, it didn’t. However, whenever arbitrary precision square roots come up, I always remember Newton’s method as this was something I learnt when I was interested in fractals years ago — generating Newton’s patterns as graphics on my BBC micro (which used to run for hours). From there it was a quick check on Wikipedia to remind myself of the details of Newton’s Method which I then coded as an extension to BigDecimal. Once that was done the solution was very straightforward.

BigDecimal.metaClass.sqrt() { scale ->
    def (x0, x1) = [ 0.0G, delegate ** 0.5 ]
    while (!x0.equals(x1)) {
        x0 = x1
        x1 = delegate.divide(x0, scale, BigDecimal.ROUND_HALF_UP)
                     .add(x0)
                     .divide(2.0G, scale, BigDecimal.ROUND_HALF_UP)
    }
    return x1
}

def answer = (1..100).sum {
    [1, 4, 9, 16, 25, 36, 49, 64, 81, 100].contains(it) ? 0 :
            new BigDecimal(it).sqrt(101).toString()[0,2..-3].toList()*.toInteger().sum()
}

This completed in 0.77 seconds. Slow for Java, but fine for this solution.

One little problem I had was that I didn’t read the question correctly, initially I assumed that it was the first 100 decimal digits that needed to be summed but a test against 2 ^ 0.5 showed that not to be the case. I also found that it was necessary to extend the scale a little further than might be obviously required otherwise there was a rounding error creeping in, hence the –3 for the tail index, rather than the –2 that you might expect.

Overall quite a fun little problem. Mostly programming rather than mathematical assuming that you’re aware of Newton’s Method.

Conclusion

Groovy really did make this solution quite nice to write. The ability to extend the BigDecimal class makes for a good clear syntax. The way that substring extraction can specify multiple ranges and the spread-dot operator for character conversion made this solution almost a one liner. The Java solution wouldn’t have been much more verbose but would have been a little more cryptic.

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: