流れる空の中で数学を。

とある数学好きの「手作りすうがく」と「気ままな雑記」。

【Python】巨大な数の整数平方根

プログラミング数学

Amazon.co.jp: Yoshiki Ueoka:作品一覧、著者略歴

数学関連の絶版本・品切れ本をコチラから購入できます！

探しても見つからなかったので、巨大な(大きな)自然数nに対して、高速に整数平方根を計算するプログラムを書きました。整数平方根とはnに対して、

$m\lt \sqrt{n}$

となる最大の整数のことです。math.sqrt等のライブラリ関数を使うと、誤差が出てしまいますが、以下の関数Intsqrtはnの桁数の計算量で整数平方根を厳密に計算してくれます。