c++ - C++で整数を正の整数累乗にする正しい方法は何ですか?

Question

さまざまな理由から、C++ には標準の整数累乗関数がないことがわかっています。かなり小さい整数で正確な算術演算を実行しています。べき乗を計算する正しい方法は何ですか?

Answer 1

標準の高速累乗では、2 乗を繰り返します。

uint_t power(uint_t base, uint_t exponent)
{
    uint_t result = 1;

    for (uint_t term = base; exponent != 0; term = term * term)
    {
        if (exponent % 2 != 0) { result *= term; }
        exponent /= 2;
    }

    return result;
}

ステップ数は の値で対数ですexponent。このアルゴリズムはモジュラ累乗に簡単に拡張できます。

---

更新:これは、乗算を 1 つ減らし、いくつかの些細なケースをより効率的に処理するアルゴリズムの修正バージョンです。さらに、指数がゼロではなく、基数がゼロまたは 1 ではないことがわかっている場合は、最初のチェックを削除することもできます。

uint_t power_modified(uint_t base, uint_t exponent)
{
    if (exponent == 0) { return 1;    }
    if (base < 2)      { return base; }

    uint_t result = 1;

    for (uint_t term = base; ; term = term * term)
    { 
        if (exponent % 2 != 0) { result *= term; }
        exponent /= 2;
        if (exponent == 0)     { break; }
    }

    return result;
}

Answer 2

Kerrek の答えは正しいですが、g++ にはこれを効率的に行うための「秘密の」機能もあります。SGI べき乗関数を見ると、必要なことを行うために簡単に適応させることができます。

http://www.sgi.com/tech/stl/power.html

g++ では、これは__gnu_cxx::powerとして実装されます。ただし、これらを本番コードで使用するべきではないでしょう...

Answer 3

ここでの他の回答に加えて、ウィキペディアにはさまざまな実装を説明する素晴らしい記事もあります -> LINK