Author mark.dickinson
Recipients juraj.sukop, mark.dickinson, rhettinger, serhiy.storchaka, stutzbach, tim.peters
Date 2021-01-28.17:57:58
SpamBayes Score -1.0
Marked as misclassified Yes
Message-id <1611856678.67.0.851462264428.issue43053@roundup.psfhosted.org>
In-reply-to
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>
2021-01-28 17:57:58mark.dickinsonlinkissue43053 messages
2021-01-28 17:57:58mark.dickinsoncreate