Skip to main content
Mathematica

You are not logged in. Your edit will be placed in a queue until it is peer reviewed.

We welcome edits that make the post easier to understand and more valuable for readers. Because community members review edits, please try to make the post substantially better than how you found it, for example, by fixing grammar or adding additional resources and hyperlinks.

Required fields*

6
  • 1
    $\begingroup$ I am impressed by the performance of this approach -- it's really in the same ballpark as GMP's integer square root performance (0.022417 seconds on my system for this vs 0.016856 seconds for GMP). The fact that the result passes through an evaluation that depends on precision is slightly unnerving, though. $\endgroup$ Commented Feb 2, 2018 at 19:21
  • 1
    $\begingroup$ It seems from here that the isqrt() in Python also uses finite precision. Check the use of hbc (which is slightly larger than half the bit length) in the main loop for isqrt_fast_python $\endgroup$ Commented Feb 2, 2018 at 20:19
  • 1
    $\begingroup$ Nice find, curious! I made a C implementation of the same calculation using just GMP functions, and it also executes in 16.8 ms. It could be that GMP also does something similar. $\endgroup$ Commented Feb 2, 2018 at 21:39
  • 1
    $\begingroup$ It seems GMP uses an integer method due to Paul Zimmermann: gmplib.org/manual/Square-Root-Algorithm.html $\endgroup$ Commented Feb 2, 2018 at 21:57
  • $\begingroup$ It's quite remarkable that those methods show identical performance. $\endgroup$ Commented Feb 3, 2018 at 21:30