Message386089
> 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. :-) |
|
Date |
User |
Action |
Args |
2021-02-01 18:57:25 | mark.dickinson | set | recipients:
+ mark.dickinson, tim.peters, rhettinger, stutzbach, serhiy.storchaka, juraj.sukop |
2021-02-01 18:57:25 | mark.dickinson | set | messageid: <1612205845.73.0.797045448053.issue43053@roundup.psfhosted.org> |
2021-02-01 18:57:25 | mark.dickinson | link | issue43053 messages |
2021-02-01 18:57:25 | mark.dickinson | create | |
|