sqrt_i
から返すべき値は、y
ではなくy_old
です。
参考サイトのソースは、以下のようになっています。
// ニュートン法による整数平方根
fn sqrt_newton(x: u64) -> u64 {
if x <= 1 { return x; }
let k = 32 - ((x - 1).leading_zeros() >> 1);
let mut s = (1 as u64) << k; // s = 2**k
let mut t = (s + (x >> k)) >> 1; // t = (s + x/s)/2
// whileループ回数=除算回数は u64:最大6回 u32:最大5回 を想定
// s > floor(sqrt(x)) -> floor(sqrt(x)) <= t < s
// s == floor(sqrt(x)) -> s == floor(sqrt(x)) <= t <= floor(sqrt(x)) + 1
while t < s { s = t; t = (s + (x / s)) >> 1; }
s
}
参考サイトのt
がy
に、s
がy_old
に対応します。参考サイトの戻り値はt
ではなくs
となっています。
参考サイトの説明に、「「(2) s_n = ⌊a⌊√a⌋ のとき、 ⌊a⌊√a⌋ ≤ s_(n+1) ≤ ⌊a⌊√a⌋+1 である。」とある通り、s_(n+1) は ⌊a⌊√a⌋+1 に等しくなる(=正しい値より1だけ大きい値となる)可能性があります。