3

b ビット数が整数の 2 乗であるかどうかを判断する公開された O(log b) アルゴリズムはありますか?

（この質問がこのサイトの範囲を超えている場合はお詫び申し上げます。そうであれば、喜んで取得します）

更新: 私の質問が不合理であることは理解しています。ですから、b の部分多項式演算であるアルゴリズムを求めることで修正させてください。定数 k に対して必ずしも O(log^kb) ではなく、「妥当な」空間の複雑さがあります。操作は通常の意味で定義されます。つまり、目の前のタスクに適したもの (たとえば、加算、否定、xor、および、またはなど) です。

追記: 今、私の質問がナンセンスであることに気づきました。n ビット数の平方根を計算するコストは、2 つの n ビット数を乗算するよりも少なくなります。

4

1 に答える 1

0
  1. 十分bに小さい場合、sqrtテーブルを使用すると複雑になりますO(1)
  2. そうでない場合、ビット近似を使用すると複雑になりますO(b/2) = O(log n)

  3. 真四角テーブルの使用も複雑ですO(b/2) = O(log n)

    ただし、はるかに高速な操作 (比較操作とビット操作のみ) ではb、ビット数は最大b/2ビット数の完全な 2 乗になる可能性があるため、テーブルにはビット数2^(b/2)のエントリがbあり、近似インデックス検索 (バイナリ検索と同様) はb/2手順を実行します。

  4. 近似によっていくらかの改善を行うことができます

    近似関数y=approx_sqrt(x);を作成して計算すると、近似精度に依存する定数であるランタイムを持つy値を確認できます。ほとんどの概算はより大きな値でオフになっているため、作成でき、複雑さは突然、あなたが探しているものだと思います。< y-c , y+c > ~T(2c)c(1,2,3,...)c=log(b)O(log b) = O(log log n)

[編集]

  1. 反対票を投じた後、マークダウンするとテキストの一部が非表示になることがわかりました

    フォーマットなどを想定している< interval >ので、非表示を解除するためにスペースをいくつか追加しました。また、箇条書き5が間違っていることがわかったので、削除しました。それがダウン投票の理由だった場合、私はそれを見落としていました...最近素数で何かをしていた...だから、私の脳はそれを徹底的に考えずにそこにコピーします

  2. 通常、コードとWikiページがないと、信じられずに反対票を投じるだけの人がいるので、上記のテスト済みの実装を次に示します。

    //---------------------------------------------------------------------------
int  is_square(int x,int &cnt)      // return sqrt(x) if perfect or 0, cnt = num of cycles ~ runtime
    {
    int y,yy;
    // y=aprox_sqrt(x)
    for (y=x,yy=x;yy;y>>=1,yy>>=2); // halves the bit count
    if (y) y=(y+(x/y))>>1;          // babylonian approximation
    if (y) y=(y+(x/y))>>1;
    if (y) y=(y+(x/y))>>1;
    // check estimated y and near values
    cnt=1;
    yy=y*y; if (yy==x) return y;
    if (yy<x) for (;;)
        {
        cnt++;
        y++;
        yy=y*y;
        if (yy==x) return y;
        if (yy> x) return 0;
        }
    else for (;;)
        {
        cnt++;
        y--;
        yy=y*y;
        if (yy==x) return y;
        if (yy< x) return 0;
        }
    }
//---------------------------------------------------------------------------

    複雑さを自分でテストできるように、cnt を追加しました。私の使用済みの近似には適切な開始値が必要なので、明らかにビット数を半分にしますO(log b)が、bignumsとfloat値の場合、指数/ビット数は既にわかっているため、単一のビット/ワード/ベース/指数シフトに変換されO(1)ます。ところで、これはor関数のほとんどの近似によって行われるIEEE フロート マジックです。sqrtlog

  3. 私の測定値は、最初の見積もりよりも優れています (非正確なバビロニア近似であっても):

    /*----------------
|          N | T |
------------------
| 1000000000 | 6 |
|  100000000 | 4 |
|   10000000 | 2 |
|    1000000 | 2 |
----------------*/

    whereはテストされたNループです。さまざまな近似のテストされた数値の最大値です（ニーズにより適しています）ここで見ることができますNTcnt< 0,N >

したがって、あなたの質問に対する私の答えは「はいO(log n)」です。完全な正方形であるかどうかを判断するよりも高速なアルゴリズムが存在しnます (たとえば、上記の も計算しsqrtます)。いいえ、ビット操作でさえO(log n)bignumで行われるためです!!!

ところで、二分探索sqrtは乗算なしでも実行できます。

それが役に立てば幸い。

于 2013-11-10T09:48:12.560 に答える