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
--
https://mail.python.org/mailman/listinfo/python-list
