<div dir="ltr"><div><div><div>Serhiy,<br><br></div>This looks very good indeed. As a matter of interest, is there any particular reason you have used 2*b instead of b+b? Might b+b be faster than b*2?<br><br></div>Also, in various lines, you use //2. Would >>1 be quicker? On reflection, perhaps you have had to use //2 because >>1 cannot be used in those situations.<br><br></div>Stephen Tucker.<br><br><div><br><br></div></div><div class="gmail_extra"><br><div class="gmail_quote">On Thu, Nov 20, 2014 at 6:00 PM, Serhiy Storchaka <span dir="ltr"><<a href="mailto:storchaka@gmail.com" target="_blank">storchaka@gmail.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">On 01.11.14 03:29, Steven D'Aprano wrote:<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
There is an algorithm for calculating the integer square root of any<br>
positive integer using only integer operations:<br>
</blockquote>
<br>
Here is my optimized implementation inspired by Christian's ideas.<br>
<br>
import math, sys<br>
<br>
C1 = sys.float_info.radix ** sys.float_info.mant_dig<br>
C2 = int(sys.float_info.max)<br>
C3 = C2.bit_length() - 2<br>
<br>
def isqrt(n):<br>
    if n < 0:<br>
        raise ValueError<br>
    if n == 0:<br>
        return 0<br>
    if n <= C1:<br>
        return int(math.sqrt(n))<br>
    if n <= C2:<br>
        x = int(math.sqrt(n))<br>
    else:<br>
        b = (n.bit_length() - C3) // 2<br>
        x = int(math.sqrt(n >> (2 * b))) << b<br>
    y = (x + n // x) // 2<br>
    if y == x:<br>
        return x<br>
    while True:<br>
        x = y<br>
        y = (x + n // x) // 2<br>
        if y >= x:<br>
            return x<span class="HOEnZb"><font color="#888888"><br>
<br>
<br>
-- <br>
<a href="https://mail.python.org/mailman/listinfo/python-list" target="_blank">https://mail.python.org/<u></u>mailman/listinfo/python-list</a><br>
</font></span></blockquote></div><br></div>