c++ - sqrt関数を使わずに平方根の底を見つける

Question

私が整数を持っていて、その数の二乗が よりも小さいn最大の数を見つけたいとしましょう。mn

この問題の最適な解決策は何ですか?

Answer 1

「最適解」はめったに存在しませんが、かなり高速なアルゴリズムは次のとおりです (名前を知っている人はいますか? )、それはバビロニア法と呼ばれます。

int num = 4567;

int r1 = num / 2;
int r2 = 2;

while (std::abs(r2 - r1) > 1) {
     r2 = (r1 + r2) / 2;
     r1 = num / r2;
}

ここでr1とr2は、平方根の下側近似と上側近似です。あなたの場合、小さい方が必要です。

Answer 2

整数部分を探しているだけなので、次のように行うことができます。

1. 可能な限り低いm、つまりm = 1でループを開始します（n <1を許可している場合を除く）
2. m*mがnより大きいかどうかを確認します
3. そうでない場合は、次のmをチェックする必要があるため、mに1を追加して、ループの次の反復に進みます。
4. 大きい場合は、ループを停止し、mから1を引きます。これは、m-1がnの平方根よりも小さい最終値であるためです。

int n = 123; //or whatever you want
int m = 1;
while (m * m <= n) {
    m = m + 1;
}
return (m - 1);