[issue43053] Speed up math.isqrt, again

Change by Mark Dickinson : -- resolution: -> rejected stage: patch review -> resolved status: open -> closed ___ Python tracker ___ ___

[issue43053] Speed up math.isqrt, again

Mark Dickinson added the comment: > Java's implementation of BigInteger.sqrt can't do that. :-) Well, okay, depending on your definition of "a few", actually it can, but Python is still faster. -- ___ Python tracker

[issue43053] Speed up math.isqrt, again

Change by Mark Dickinson : -- keywords: +patch pull_requests: +23229 stage: -> patch review pull_request: https://github.com/python/cpython/pull/24414 ___ Python tracker ___ _

[issue43053] Speed up math.isqrt, again

Mark Dickinson added the comment: > 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-

[issue43053] Speed up math.isqrt, again

Juraj Sukop added the comment: Mark, thank you very much for the thorough reply! I believe it is not for me to say whether the complication is worth it or not. What really huge numbers goes, if I'm not mistaken, the original `isqrt` is already "fast" and only constant speed-up is possible.

[issue43053] Speed up math.isqrt, again

Mark Dickinson added the comment: Translation of the proposal to the iterative version described here: https://github.com/python/cpython/blob/64fc105b2d2faaeadd1026d2417b83915af6622f/Modules/mathmodule.c#L1591-L1611 The main loop: c = (n.bit_length() - 1) // 2 a = 1 d

[issue43053] Speed up math.isqrt, again

Mark Dickinson added the comment: Some comments, now that I've had a chance to look properly at the suggestion. For reference, here's the "near square root" function that forms the basis of Python's isqrt algorithm. For clarity, I've written it recursively, but it's equivalent to the iterativ

[issue43053] Speed up math.isqrt, again

Juraj Sukop added the comment: The rounding down of `l` might compute more than half of the bits so that the final Heron' step in `isqrt_2` might correct the uncertain low bit if `a - (a*a > n)` is missing from `isqrt`. As it currently stands, `a - (a*a > n)` is computed both in `isqrt` and

[issue43053] Speed up math.isqrt, again

Mark Dickinson added the comment: > As it currently stands, `a - (a*a > n)` is computed both in `isqrt` and > `isqrt_2`. So I was thinking that maybe the former might be dropped. Ah, sorry; I misunderstood. Yes, I think so. I'll respond more fully later. (Sorry - real life getting in the way

[issue43053] Speed up math.isqrt, again

Mark Dickinson added the comment: > the only thing I'm not sure about is whether the final correction in the > original `isqrt` is needed Well, *some* part of the algorithm has to make use of the low-order bits of n. Otherwise we won't be able to distinguish n = 4a**2 + 4a + 1 (whose isqrt i

[issue43053] Speed up math.isqrt, again

Juraj Sukop added the comment: What the proof goes, you did most of the work already. Consider the following: l = (n.bit_length() - 1)//4 a = isqrt(n >> 2*l) a = ((a << l) + n//(a << l))//2 return a - (a*a > n) This computes the square root of the (possibly longer) upper half,

[issue43053] Speed up math.isqrt, again

Mark Dickinson added the comment: Thanks; I'll take a look at this at the weekend. Do you have a sketch of a proof of correctness available? -- assignee: -> mark.dickinson ___ Python tracker __

[issue43053] Speed up math.isqrt, again

Change by Serhiy Storchaka : -- nosy: +mark.dickinson, rhettinger, serhiy.storchaka, stutzbach ___ Python tracker ___ ___ Python-bug

[issue43053] Speed up math.isqrt, again

New submission from Juraj Sukop : This is a follow up to https://bugs.python.org/issue36887 and https://bugs.python.org/issue36957 . The new `isqrt` is remarkably simple but it does not split the number at hand optimally. Ideally one would want to have 2n/n division everywhere but since the