c - X <= n*n の場合に最小の n を見つける高速な方法

Question

タイトルが悪くてすみません。これ以上のタイトルが見つかりませんでした。(編集は大歓迎です:p)

X=8という数があるとしましょう。私は 2*2=4 を知っているので、数字の 8 は含まれていません。

編集: 2x2 グリッドを想像してください ... 1,2,3,4 ... 8 が含まれていません

これで、3*3 = 9 となり、勝者 (n=3) が見つかりました!

この目的のための私の（貧弱な）コード

 long long int i=0; N = 8;
 while (i*i <N)
    {
        i++;
    }
    l = i; // l is to store he number "3"; say 8 is in a 3x3 grid

N = 100000000 の場合、これは効率的な計算方法ではありません。

X を含む i*i を取得するより効率的な方法は何ですか?

Answer 1

sqrtの関数を使用します<math.h>。これは (かなり) 効率的なアルゴリズムになり、ループよりもはるかに高速に実行されるはずです。それから切り上げれば、あなたはあなたの答えを持っています。

int find_containing_int(double x)
{
  const double sqr = sqrt(x);

  return ceil(sqr);
}