2026-10-10
is_isqrt.c
#include <stdint.h>
bool is_isqrt(uint32_t n, uint32_t r) {
}
整数平方根を求める関数の事後条件として assert に書く述語 is_isqrt を書いてください。r が n の整数平方根、つまり2乗しても n を超えない最大の整数なら true、そうでなければ false を返します。n と r が uint32_t のどの値でも正しく判定し、n が 0 のときは r が 0 の場合だけ true です。
入力例 1
is_isqrt(10, 3)
出力例 1
true
入力例 2
is_isqrt(4294967295, 65535)
出力例 2
true
入力例 3
is_isqrt(100000, 65536)
出力例 3
false
Reference
#include <stdint.h>
bool is_isqrt(uint32_t n, uint32_t r) {
uint64_t r64 = r;
return r64 * r64 <= n && n < (r64 + 1) * (r64 + 1);
}
整数平方根の定義をそのまま式にすると r * r <= n && n < (r + 1) * (r + 1) ですが、uint32_t のまま掛けると、積が 232 以上になったところで剰余が取られ、小さな値に化けます1。入力例2では (r + 1) * (r + 1) が 4294967296 になるはずが 0 に巻き戻り、正しい組なのに false を返します。入力例3では逆に r * r が 0、(r + 1) * (r + 1) が 131073 に化けて両方の比較が通り、誤った組に true を返します。
参考実装は、掛ける前に r を uint64_t に移します。左の積 r64 * r64 は uint32_t の最大値どうしでも 264 未満に収まります。右の積を計算するのは && の左が真のとき、つまり r が 65535 以下のときだけなので、こちらも 232 以下で済みます。比較の相手の n は、通常の算術変換で uint64_t に揃えられます。
事後条件の述語が誤っていると、正しい実装を assert で止めたり、誤った実装を素通りさせたりします。表明する式も、検査される側のコードと同じようにオーバーフローを考えて書く必要があります。掲載したのは参考実装で、唯一の正解ではありません。r <= n / r のように割り算で比べれば64ビットの型を使わずに書けますが、r が 0 の場合を別に扱うことになります。
uint32_tがunsigned intと同じ幅になる、32ビットのintを持つ一般的な環境での話です。符号なし整数の演算は、結果の型で表せる最大値に1を足した数を法として計算されると規格が定めています。