a を整数、n を自然数とします。
一般に a^n の計算を高速に行う方法を教えてください。
なお、この質問は
「特定の n に対して最小の計算回数を求める」
という趣旨の質問ではありません。
(追記)
バイナリ法によるコード(Ruby版およびPython版)を
回答に載せました。
(Ruby 2.2)
以下のような
①バイナリ法の上位桁から計算する方式+再帰
②バイナリ法の上位桁から計算する方式
と
③その三進法バージョン
を比較しましたが、①②に比べて③は遅い感じです。
バイナリ法+再帰
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)
バイナリ法
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)
三進法バージョン
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)
(Python 2.7)
同じ計算をさせたのですが、Ruby 2.2よりずっと遅い。
ちなみに、組み込み関数
pow(http://docs.python.jp/2/library/functions.html#pow)
を使っても同じくらい遅い。
バイナリ法
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)
powを用いた計算
a = 5
n = 10 ** 5
sum = sum(pow(a, i) for i in xrange(n + 1))
print sum == a ** (n + 1) / (a - 1)
◆参考コード(C言語)
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;
}
以上です。