c++ - p ^ q（べき乗）を計算する効率的な方法。ここで、qは整数です。

Question

^{p q}を計算する効率的な方法は何ですか？ここで、qは整数です。

Answer 1

Exponentiation by squaring uses only O(lg q) multiplications.

template <typename T>
T expt(T p, unsigned q)
{
    T r(1);

    while (q != 0) {
        if (q % 2 == 1) {    // q is odd
            r *= p;
            q--;
        }
        p *= p;
        q /= 2;
    }

    return r;
}

This should work on any monoid (T, operator*) where a T constructed from 1 is the identity element. That includes all numeric types.

Extending this to signed q is easy: just divide one by the result of the above for the absolute value of q (but as usual, be careful when computing the absolute value).

Answer 2

Assuming that ^ means exponentiation and that q is runtime variable, use std::pow(double, int).

EDIT: For completeness due to the comments on this answer: I asked the question Why was std::pow(double, int) removed from C++11? about the missing function and in fact pow(double, int) wasn't removed in C++0x, just the language was changed. However, it appears that libraries may not actually optimize it due to result accuracy concerns.

Even given that I would still use pow until measurement showed me that it needed to be optimized.

Answer 3

^とは、ビット単位のxorではなく、べき関数を意味すると思います。

任意のタイプのpおよび任意の正の積分qに対する効率的なべき関数の開発は、StepanovおよびMcJonesの著書ElementsofProgrammingのセクション3.2全体の主題です。この本の言語はC++ではありませんが、C++に非常に簡単に翻訳できます。

これは、二乗による指数化、末尾再帰への変換と反復、累積変数の除去など、いくつかの最適化をカバーし、最適化を型の規則性と結合演算の概念に関連付けて、そのようなすべての型で機能することを証明します。