[issue43053] Speed up math.isqrt, again

[Mark Dickinson]

Mark Dickinson <dickinsm at gmail.com> 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 = 0
        for s in reversed(range(c.bit_length())):
            # Loop invariant: (a-1)**2 < (n >> 2*(c - d)) < (a+1)**2
            e = d
            d = c >> s
            a = (a << d - e - 1) + (n >> 2*c - e - d + 1) // a

becomes (again identical except for the last line):

        c = (n.bit_length() - 1) // 2
        a = 1
        d = 0
        for s in reversed(range(c.bit_length())):
            # Loop invariant: (a-1)**2 < (n >> 2*(c - d)) < (a+1)**2
            e = d
            d = c >> s
            a = (a << d - e) + ((n >> 2*c - e - d + 1) - (a*a << d - e - 1)) // a

----------

_______________________________________
Python tracker <report at bugs.python.org>
<https://bugs.python.org/issue43053>
_______________________________________