Author mark.dickinson juraj.sukop, mark.dickinson, rhettinger, serhiy.storchaka, stutzbach, tim.peters 2021-01-28.17:57:58 -1.0 Yes <1611856678.67.0.851462264428.issue43053@roundup.psfhosted.org>
Content
```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```
History
Date User Action Args
2021-01-28 17:57:58mark.dickinsonsetrecipients: + mark.dickinson, tim.peters, rhettinger, stutzbach, serhiy.storchaka, juraj.sukop
2021-01-28 17:57:58mark.dickinsonsetmessageid: <1611856678.67.0.851462264428.issue43053@roundup.psfhosted.org>