[過去ﾛｸﾞ] プログラミングのお題スレ Part13 (1002ﾚｽ)
上下前次1-新
抽出解除 必死ﾁｪｯｶｰ(本家) (べ) 自ID ﾚｽ栞 あぼーん

---

このｽﾚｯﾄﾞは過去ﾛｸﾞ倉庫に格納されています｡
次ｽﾚ検索 歴削→次ｽﾚ 栞削→次ｽﾚ 過去ﾛｸﾞﾒﾆｭｰ

---

42(2): 2019/02/05(火)12:28 ID:aE6b0ZPr(1)調 AAS
>>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

---

上下前次1-新書関写板覧索設栞歴

---

ｽﾚ情報 赤ﾚｽ抽出 画像ﾚｽ抽出 歴の未読ｽﾚ AAｻﾑﾈｲﾙ

---

ぬこの手 ぬこTOP 0.056s