Mark Dickinson <dicki...@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 <rep...@bugs.python.org> <https://bugs.python.org/issue43053> _______________________________________ _______________________________________________ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
