2026-10-29
isqrt.c
uint64_t isqrt(uint64_t n) {
}
2乗して n を超えない最大の整数を返す isqrt を書いてください。値は、正の整数 x を (x + n / x) / 2(uint64_t どうしの割り算)で置き換える操作を繰り返して求め、浮動小数点数は使いません。n は0から UINT64_MAX までのどの値でもよく、n が0のときは0を返します。
入力例 1
isqrt(15)
出力例 1
3
入力例 2
isqrt(0)
出力例 2
0
入力例 3
isqrt(UINT64_MAX)
出力例 3
4294967295
Reference
uint64_t isqrt(uint64_t n) {
if (n < 2) {
return n;
}
uint64_t x = n / 2;
uint64_t y = (x + n / x) / 2;
while (y < x) {
x = y;
y = (x + n / x) / 2;
}
return x;
}
求める値を r とします。この反復は、どこから始めても1回目で r 以上になります。割り算を切り捨てずに考えると、x と n / x の平均は2つの積が n なので √n 以上で、切り捨てても整数の r を下回らないからです。そして x が r より大きい間は x * x > n なので n / x < x となり、次の値は x より小さくなります。x が r に着くと n / x は r 以上になり、次の値はもう減りません。そのため参考実装は、次の値 y が x より小さい間だけ進み、y が x 以上になった時点の x を返します。
初期値は r 以上で、しかも足し算が桁あふれしない値にします。x = n は r 以上ですが、n が UINT64_MAX だと x + n / x が n + 1 になって0に戻り、次の n / x は0での割り算になります。n / 2 なら n が4以上で √n 以上、n が2と3では答えの1そのものです。0と1は n / 2 が0になって割り算に使えないので、先に返します。
止める条件を y != x にすると、n = 15 で値が7、4、3、4、3……と3と4を行き来して止まりません。切り捨てのせいで r から次の値が r + 1 に戻ることがあるからです。逆に初期値を1にすると、1回目で値が増えるので、y < x の条件ではすぐに止まって1を返します。
掲載したのは参考実装で、唯一の正解ではありません。初期値は、n の2進数の桁数の半分から作った2のべき乗のように、r 以上で桁あふれしない値なら何でもかまいません。根に近いほど繰り返しが少なく済みます。