4

n^pを見つけるためのアルゴリズムは次のとおりです。

unsigned long long power(unsigned n, unsigned p)
{
    unsigned long long x=1, y=n;
    while(p > 0)
    {
        if(p&1) x *= y;
        y *= y;
        p >>= 1;
    }
    return x;
}

誰かがこのアルゴリズムの背後にある論理/数学を説明できますか? 私はそれが機能することを知っており、いくつかのテストケース（ドライラン）でうまくいきました。それがどのように機能し、一般的な素朴な方法からどのように効率的であるかを意味します。

4

1 に答える 1

6

これは2 乗によるべき乗です。>>= 1/= 2

その背後にある考え方は、pが偶数の場合、n^(p/2)それを 2 乗できるということです。が奇数のときpは偶数でp-1なければならないので、 を取りn^((p-1)/2)、それを 2 乗し、その結果を で乗算して、2 乗する前にから引いnた を補うことができます。1p

于 2012-12-24T14:29:14.387 に答える