Project Euler #80: Square root digital expansion

  • + 3 comments

    Man, this one is tough to get in under the wire.

    For C++/Java, it seems to require:

    * BigInteger (or optimized custom class for c++)
    * Newton's method (faster than digit-by-digit calculation)
    * Strong initial guess using double-precision sqrt
    * Reducing the number of actual roots computed the long way (the final speed-up 'trick')
    

    Even so, my Java implementation barely comes in under the wire at 3.2 s for test case 9, and C++ implementation is hit-and-miss around 2 s.