1

q^k を計算したいのですが、st q は n ビット幅で、制限があります。

  1. 最終結果は n*k ビット幅になります。
  2. 計算のすべてのステップで、x,y st x を乗算した結果は |x| です。ビット幅で、y は |y| です。ビット幅は |x|*|y| です。ビット幅。

私はそれをペアでやろうとしました。最初のステップの結果は 2n ビット、2 番目のステップは (2^2)n ビットなど、最後のステップは n*2^(logk) (=kn ) ビット。log(k) ステップがあり、慎重に計算すると、O(log(n)(log(k))^2) になります。上記の制限の中で、それを行うためのより高速な方法 (またはこのアルゴリズムなどのより良い分析) について聞いていただければ幸いです。前もって感謝します。

4

2 に答える 2

0

k のビットを通過するとき、最適な整数 pow はO(2*Log2(K))だと思います。

  • k はバイナリ形式で記述できます k = { kn-1,...k3,k2,k1,k0 }

式は次のようになります。

q^k = q^( 1*k0 +2*k1 +4*k2 +8*k3 ... )
q^k = q^k0 * q^(2*k1) * q^(4*k2) ....
  • したがって、計算するのは n = ceil(log2(k)) ステップだけです
  • ki!=0 の場合、各ステップで q^i を乗算して結果を得る
  • q(i+1)=qi*qi
  • q0 = q

単純化された作業コード (特殊なケース 0^k、k^0、0^0、... を処理しません):

DWORD pow(DWORD q,DWORD k)
    {
    DWORD s;
    for (s=1;k;k>>=1,q*=q)
     if (k&1) s*=q; 
    return s;
    }

もちろん、bigint演算よりも大きなq、kを使用したい場合は、代わりに必要です

  • 低ビット乗算のペアリングがあまり役立つとは思わない
  • 非常に大きな数に使用しない限り
  • 通常、異なるビット数のサブ結果のペアリングとマージは遅くなるためです。
于 2013-09-17T12:57:31.323 に答える