We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
* 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.
I used all those tricks including Newton's method on the inverse square root in C++. Results: case 6 in 0.96 s, case 7 in 1.68 s and case 8 and 9 time-out. Should I just hand in the Python solution or do you have a final suggestion?
Project Euler #80: Square root digital expansion
You are viewing a single comment's thread. Return to all comments →
Man, this one is tough to get in under the wire.
For C++/Java, it seems to require:
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.
I used all those tricks including Newton's method on the inverse square root in C++. Results: case 6 in 0.96 s, case 7 in 1.68 s and case 8 and 9 time-out. Should I just hand in the Python solution or do you have a final suggestion?
optimized sum of digits of google's bigint and passed testcase 9 in 0.67 seconds using C++ (see my other comment)
You are doing right. Just optimize your multiplication and division. I was able to pass all the cases with my custom bigint class.