Author mark.dickinson
Recipients juraj.sukop, mark.dickinson, rhettinger, serhiy.storchaka, stutzbach, tim.peters
Date 2021-02-01.18:57:25
SpamBayes Score -1.0
Marked as misclassified Yes
Message-id <1612205845.73.0.797045448053.issue43053@roundup.psfhosted.org>
In-reply-to
Content
> the complication probably amounts to no more than 10-20 extra lines of C code

A net difference of 16 lines of code, as it turns out. The branch is here: https://github.com/mdickinson/cpython/tree/isqrt-performance

Informal not-very-scientific timings more-or-less confirm what I expected: I _do_ get a speedup approaching a factor of 2 for huge n: getting a million digits of sqrt(2) via `n = 2*10**10**6; x = isqrt(n)` takes around 9 seconds on master and 5 seconds with this branch, on my machine. But for values with 20 digits or so, the overhead of the extra operations means that the algorithm is around 20% slower. The cutoff for me seems to be somewhere between 200 and 1000 digits.

So I'm afraid I'm going to leave this as is: if speed were all we cared about then there are all sorts of things we could try, but I'd rather keep the simplicity. And it's nice that it's still *possible* to compute a million digits of sqrt(2) in a few seconds. Java's implementation of BigInteger.sqrt can't do that. :-)
History
Date User Action Args
2021-02-01 18:57:25mark.dickinsonsetrecipients: + mark.dickinson, tim.peters, rhettinger, stutzbach, serhiy.storchaka, juraj.sukop
2021-02-01 18:57:25mark.dickinsonsetmessageid: <1612205845.73.0.797045448053.issue43053@roundup.psfhosted.org>
2021-02-01 18:57:25mark.dickinsonlinkissue43053 messages
2021-02-01 18:57:25mark.dickinsoncreate