整数平方根 isqrt

整数 n に対して a^2 <= n を満たす最大の整数 a を求めるときは，
int(sqrt(n)) ではなくisqrt を使う

ということであるが，math に isqrt があるのは知らなくて，自分で関数を書いたりした。ニュートン法なのでそこそこの速度はあったのだけど。

from math import isqrt
from time import time

def f(n):
    a = isqrt(n)
    return a**2 <= n < (a+1)**2

start = time(); print(f(2**12345678), time()-start)
# True 37.5530788898468

Julia にも isqrt はあるが，実引数 n の指定には BigInt が使われるように定義すること。まあ，それだけだから，簡単といえば簡単だ。

function f(n)
    a = isqrt(n)
    a^2 <= n < (a+1)^2
end

@time f(BigInt(2)^12345678)
# 0.178914 seconds (1.44 k allocations: 51.893 MiB, 0.52% gc time)
# true

Python より 200 倍速い。