[issue36957] Speed up math.isqrt

Mark Dickinson added the comment: Calling this done for now. -- resolution: -> fixed stage: patch review -> resolved status: open -> closed ___ Python tracker ___ ___

[issue36957] Speed up math.isqrt

Mark Dickinson added the comment: New changeset 5c08ce9bf712acbb3f05a3a57baf51fcb534cdf0 by Mark Dickinson in branch 'master': bpo-36957: Speed up math.isqrt (#13405) https://github.com/python/cpython/commit/5c08ce9bf712acbb3f05a3a57baf51fcb534cdf0 -- __

[issue36957] Speed up math.isqrt

Serhiy Storchaka added the comment: New changeset a5119e7d75c9729fc36c059d05f3d7132e7f6bb4 by Serhiy Storchaka in branch 'master': bpo-36957: Add _PyLong_Rshift() and _PyLong_Lshift(). (GH-13416) https://github.com/python/cpython/commit/a5119e7d75c9729fc36c059d05f3d7132e7f6bb4 -- _

[issue36957] Speed up math.isqrt

Serhiy Storchaka added the comment: I have also some ideas about algorithmic optimizations (they need to be tested). In classic formula $a_{i+1} = a_i + (n - a_i^2)/(2*a_i)$ we can calculate $n - a_i^2$ as $(n - a_{i-1}^2) - (a_i^2 - a_{i-1})^2 = (n - a_{i-1}^2) - (a_i^2 - a_{i-1})*(a_i^2 +

[issue36957] Speed up math.isqrt

Serhiy Storchaka added the comment: It is possible to get yet 10-20% by avoiding to create temporary Python integers for right arguments of shift operations. PR 13416 adds two private functions _PyLong_Rshift() and _PyLong_Lshift() which take the second argument as C size_t instead of Python

[issue36957] Speed up math.isqrt

Change by Serhiy Storchaka : -- pull_requests: +13327 ___ Python tracker ___ ___ Python-bugs-list mailing list Unsubscribe: https:/

[issue36957] Speed up math.isqrt

Mark Dickinson added the comment: > Did you try the floating point implementation? The aim here was to use exactly the same algorithm, but speed it up by working with C integers where possible; that's a fairly simple change. Using floating-point would require more complex changes. Again, the

[issue36957] Speed up math.isqrt

Serhiy Storchaka added the comment: Did you try the floating point implementation? -- nosy: +serhiy.storchaka ___ Python tracker ___ __

[issue36957] Speed up math.isqrt

Mark Dickinson added the comment: > introduce in GH-36887 Sorry, that should have been: introduced in GH-13244. #36887 was the corresponding b.p.o. issue. -- ___ Python tracker

[issue36957] Speed up math.isqrt

Change by Mark Dickinson : -- keywords: +patch pull_requests: +13316 stage: needs patch -> patch review ___ Python tracker ___ ___ P

[issue36957] Speed up math.isqrt

New submission from Mark Dickinson : The `math.isqrt` algorithm introduce in GH-36887 currently works entirely with Python long integers. That's unnecessarily inefficient for small inputs. For n < 2**64, `math.isqrt(n)` can be computed, via exactly the same algorithm, using entirely C integer