Challenge: optimizing isqrt

[Serhiy Storchaka]

On 01.11.14 03:29, Steven D'Aprano wrote:
> There is an algorithm for calculating the integer square root of any
> positive integer using only integer operations:

Here is my optimized implementation inspired by Christian's ideas.

import math, sys

C1 = sys.float_info.radix ** sys.float_info.mant_dig
C2 = int(sys.float_info.max)
C3 = C2.bit_length() - 2

def isqrt(n):
     if n < 0:
         raise ValueError
     if n == 0:
         return 0
     if n <= C1:
         return int(math.sqrt(n))
     if n <= C2:
         x = int(math.sqrt(n))
     else:
         b = (n.bit_length() - C3) // 2
         x = int(math.sqrt(n >> (2 * b))) << b
     y = (x + n // x) // 2
     if y == x:
         return x
     while True:
         x = y
         y = (x + n // x) // 2
         if y >= x:
             return x