二乗によるべき乗。
int ipow(int base, int exp)
{
int result = 1;
for (;;)
{
if (exp & 1)
result *= base;
exp >>= 1;
if (!exp)
break;
base *= base;
}
return result;
}
これは、非対称暗号で膨大な数の剰余累乗を行うための標準的な方法です。
二乗による累乗は最適な方法ではないことに注意してください。これはおそらく、すべての指数値に対して機能する一般的な方法として実行できる最善の方法ですが、特定の指数値に対しては、乗算の回数が少なくて済む、より優れたシーケンスが存在する可能性があります。
たとえば、x^15 を計算したい場合、二乗による累乗の方法は次のようになります:
x^15 = (x^7)*(x^7)*x
x^7 = (x^3)*(x^3)*x
x^3 = x*x*x
これは合計 6 回の乗算です。
これは、加算連鎖累乗による "ちょうど" 5 つの乗算を使用して実行できることがわかりました。
n*n = n^2
n^2*n = n^3
n^3*n^3 = n^6
n^6*n^6 = n^12
n^12*n^3 = n^15
この最適な乗算シーケンスを見つけるための効率的なアルゴリズムはありません。ウィキペディアより:
2 を累乗する必要がある場合。これを行う最も速い方法は、べき乗でビット シフトすることです。
2 ** 3 == 1 << 3 == 8
2 ** 30 == 1 << 30 == 1073741824 (A Gigabyte)