10010


a を整数、n を自然数とします。  
一般に a^n の計算を高速に行う方法を教えてください。

なお、この質問は  
「特定の n に対して最小の計算回数を求める」  
という趣旨の質問ではありません。

（追記）  
バイナリ法によるコード（Ruby版およびPython版）を  
回答に載せました。


CC BY-SA 3.0
2015-05-10T10:05:08.797
10006
2015-06-19T10:24:20.957
2015-05-17T07:34:51.070
5363
5363
question
ruby python アルゴリズム
冪乗計算を高速に行うには？


(Ruby 2.2)  
以下のような  
①バイナリ法の上位桁から計算する方式+再帰  
②バイナリ法の上位桁から計算する方式  
と  
③その三進法バージョン  
を比較しましたが、①②に比べて③は遅い感じです。

バイナリ法＋再帰

[code]

    a = 5
    n = 10 ** 5
    
    def power2(a, n)
      return 1 if n == 0
      k = power2(a, n >> 1)
      k *= k
      return k if n & 1 == 0
      return k * a
    end
    
    sum = 0
    (0..n).each{|i|
      sum += power2(a, i)
    }
    p sum == a ** (n + 1) / (a - 1)
    
[/code]

バイナリ法

[code]

    a = 5
    n = 10 ** 5
    
    def power2(a, n)
      p = 1
      n.to_s(2).split('').each{|i|
        p *= p
        if i == '1'
          p *= a
        end
      }
      p
    end
    
    sum = 0
    (0..n).each{|i|
      sum += power2(a, i)
    }
    p sum == a ** (n + 1) / (a - 1)
    
[/code]

三進法バージョン

[code]

    a = 5
    n = 10 ** 5
    
    def power3(a, n)
      p = 1
      n.to_s(3).split('').each{|i|
        p *= p * p
        if i == '1'
          p *= a
        elsif i == '2'
          p *= a * a
        end
      }
      p
    end
    
    sum = 0
    (0..n).each{|i|
      sum += power3(a, i)
    }
    p sum == a ** (n + 1) / (a - 1)
    
[/code]

(Python 2.7)  
同じ計算をさせたのですが、Ruby 2.2よりずっと遅い。  
ちなみに、組み込み関数  
pow(<http://docs.python.jp/2/library/functions.html#pow>)  
を使っても同じくらい遅い。

バイナリ法

[code]

    a = 5
    n = 10 ** 5
    
    def power2(a, n):
        p = 1
        for i in list(format (n, 'b')):
            p *= p
            if i == '1':
                p *= a
        return p
    
    sum = sum(power2(a, i) for i in xrange(n + 1))
    print sum == a ** (n + 1) / (a - 1)
    
[/code]

powを用いた計算

[code]

    a = 5
    n = 10 ** 5
    
    sum = sum(pow(a, i) for i in xrange(n + 1))
    print sum == a ** (n + 1) / (a - 1)
    
[/code]


CC BY-SA 3.0
2015-05-10T11:59:15.050
10010
2015-05-14T14:08:17.623
2015-05-14T14:08:17.623
5363
5363
10006
answer


![冪乗](https://i.stack.imgur.com/s060R.jpg)

◆参考コード（C言語）

[code]

    int power(int x, int y, bool *of) {
        long long a = x;
        long long b = y;
    
        *of = true;
        if (b < 0) return 0;
    
        long long int hi = 0x7fffffffULL;
        long long int lo = ~(hi + 1) + 1;
        long long sum = 1;
    
        while (b != 0) {
            sum = ((b & 1) == 0) ? sum : a * sum;
            a = a * a;
            b >>= 1;
        }
    
        // check overflow
        if ((sum > hi) || (sum < lo)) {
            *of = true;
        }
        else {
            *of = false;
        }
    
        return sum;
    }
    
[/code]

以上です。


CC BY-SA 3.0
2015-06-19T10:24:20.957
11520
2015-06-19T10:24:20.957
10216
10006
answer