Skip to main content
ルートが抜けていた
ソース リンク
actorbug
  • 917
  • 1
  • 4
  • 9

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
}

参考サイトのtyに、sy_oldに対応します。参考サイトの戻り値はtではなくsとなっています。

参考サイトの説明に、「(2) s_n ​= ⌊a⌊√a​⌋ のとき、 ⌊a⌊√a⌋ ≤ s_(n+1) ≤ ⌊a⌊√a⌋+1 である。」とある通り、s_(n+1) は ⌊a⌊√a⌋+1 に等しくなる(=正しい値より1だけ大きい値となる)可能性があります。

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
}

参考サイトのtyに、sy_oldに対応します。参考サイトの戻り値はtではなくsとなっています。

参考サイトの説明に、「(2) s_n ​= ⌊a​⌋ のとき、 ⌊a⌋ ≤ s_(n+1) ≤ ⌊a⌋+1 である。」とある通り、s_(n+1) は ⌊a⌋+1 に等しくなる(=正しい値より1だけ大きい値となる)可能性があります。

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
}

参考サイトのtyに、sy_oldに対応します。参考サイトの戻り値はtではなくsとなっています。

参考サイトの説明に(2) s_n ​= ⌊√a​⌋ のとき、 ⌊√a⌋ ≤ s_(n+1) ≤ ⌊√a⌋+1 である。」とある通り、s_(n+1) は ⌊√a⌋+1 に等しくなる(=正しい値より1だけ大きい値となる)可能性があります。

補足説明追加
ソース リンク
actorbug
  • 917
  • 1
  • 4
  • 9

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
}

参考サイトのtyに、sy_oldに対応します。参考サイトの戻り値はtではなくsとなっています。

参考サイトの説明に、「(2) s_n ​= ⌊a​⌋ のとき、 ⌊a⌋ ≤ s_(n+1) ≤ ⌊a⌋+1 である。」とある通り、s_(n+1) は ⌊a⌋+1 に等しくなる(=正しい値より1だけ大きい値となる)可能性があります。

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
}

参考サイトのtyに、sy_oldに対応します。参考サイトの戻り値はtではなくsとなっています。

参考サイトの説明に、「(2) s_n ​= ⌊a​⌋ のとき、 ⌊a⌋ ≤ s_(n+1) ≤ ⌊a⌋+1 である。」とある通り、s_(n+1) は ⌊a⌋+1 に等しくなる可能性があります。

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
}

参考サイトのtyに、sy_oldに対応します。参考サイトの戻り値はtではなくsとなっています。

参考サイトの説明に、「(2) s_n ​= ⌊a​⌋ のとき、 ⌊a⌋ ≤ s_(n+1) ≤ ⌊a⌋+1 である。」とある通り、s_(n+1) は ⌊a⌋+1 に等しくなる(=正しい値より1だけ大きい値となる)可能性があります。

ソース リンク
actorbug
  • 917
  • 1
  • 4
  • 9

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
}

参考サイトのtyに、sy_oldに対応します。参考サイトの戻り値はtではなくsとなっています。

参考サイトの説明に、「(2) s_n ​= ⌊a​⌋ のとき、 ⌊a⌋ ≤ s_(n+1) ≤ ⌊a⌋+1 である。」とある通り、s_(n+1) は ⌊a⌋+1 に等しくなる可能性があります。