Serhiy, 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?
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. Stephen Tucker. On Thu, Nov 20, 2014 at 6:00 PM, Serhiy Storchaka <storch...@gmail.com> wrote: > 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 >
-- https://mail.python.org/mailman/listinfo/python-list