累乗

累乗（るいじょう、英語：repeated multiplication）とは、冪乗（べきじょう）の指数部が「1以上の自然数（整数）」なものをいう。

ほとんどのプログラミング言語には冪乗を計算する関数は標準搭載されているが、累乗を計算する関数はないことが多く、累乗の計算は冪乗の結果を整数にキャストすることで得るようになっていることが多い。

 // 冪乗関数はこんな感じ
 double Math.Pow(double x, double y);

 // 累乗は結果をキャストすることで得るようになっていることが多い。
 int r = (int)Math.Pow(3,11);

ただし冪乗の計算は自然数以外（浮動小数点）も扱える汎用性の高さの代償として非常に計算量が多いため、累乗（指数部に整数）しか使わないのであれば自前で簡単な関数を実装した方が高速な場合が多い。

    using System;
    using BenchmarkDotNet.Attributes;
    using BenchmarkDotNet.Running;

    public class Program
    {
        public static void Main(string[] args)
        {
            var switcher = BenchmarkRunner.Run<Program>();
        }

        // 冪乗の結果をキャストする
        [Benchmark]
        [Arguments(3, 11)]
        public int PowA(int x, uint exponent)
        {
            return (int)Math.Pow(x, exponent);
        }

        // 累乗：教科書どおりの力技
        [Benchmark]
        [Arguments(3,11)]
        public int PowB(int x, uint exponent)
        {
            int r = 1;
            for (int n = 0; n < exponent; n++)
            {
                r = r * x;
            }
            return r;
        }

        // 累乗：アルゴリズム最適化
        [Benchmark]
        [Arguments(3, 11)]
        public int PowC(int x, uint exponent)
        {
            int ret = 1;
            while (exponent != 0)
            {
                if ((exponent & 1) == 1)
                {// 奇数
                    ret *= x;
                }
                x *= x;
                exponent >>= 1;
            }
            return ret;
        }
    }