Message385873
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 |
|
Date |
User |
Action |
Args |
2021-01-28 17:57:58 | mark.dickinson | set | recipients:
+ mark.dickinson, tim.peters, rhettinger, stutzbach, serhiy.storchaka, juraj.sukop |
2021-01-28 17:57:58 | mark.dickinson | set | messageid: <1611856678.67.0.851462264428.issue43053@roundup.psfhosted.org> |
2021-01-28 17:57:58 | mark.dickinson | link | issue43053 messages |
2021-01-28 17:57:58 | mark.dickinson | create | |
|