19/02/05 12:28:40.98 aE6b0ZPr.net
>>35 結局 整数のsqrt を作って、範囲の中に納まる最小最大の整数のsqrt を取り出し、その差（+1）がその範囲の中にある平方数の個数と言う作りにした。
ポイントとなった整数のsqrt が秀逸だったのでここに書いておく。 どんなに巨大な数字でも数回のシフト操作だけで終わるから極端にスピードが速い。
ソースは、gist.github.com/bnlucas/5879594
# integer square root
def isqrt_2(n):
if n < 0:
raise ValueError('Square root is not defined for negative numbers.')
x = int(n)
if x == 0:
return 0
a, b = divmod(x.bit_length(), 2)
#divmod(a, b)は(a // b, a % b)のタプルを返す。
#平方数は半分のビット数以下だからそれを最大値で計算開始
n = 2 ** (a + b)
while True:
y = (n + x // n) >> 1 #1bit右にシフト
if y >= n:
return n
n = y
-----------------
#結果 0.0 秒 count= 1000000000
#範囲 999999999000000000000000000000000000 1000000001000000000000000000000000000
#入力bit_length()=120 入力bit_length()=120
平方数範囲 999999999500000000 1000000000499999999
上の二乗 999999999000000000250000000000000000 1000000000999999998249999999000000001