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)
.divide(2.0G, scale, BigDecimal.ROUND_HALF_UP)
}
return x1
}

[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.