Быстрое возведение в степень

Алгоритм быстрого возведения в степень — алгоритм, предназначенный для возведения числа x в натуральную степень n за меньшее число умножений, чем это требуется в определении.

Пусть [math]m=(m_{k}m_{k-1}...m_{1}m_{0})_2[/math] — двоичное представление степени n. Тогда [math]n=m_{k} \cdot 2^{k}+m_{k-1} \cdot 2^{k-1}+...+m_{1} \cdot 2+m_{0}[/math], где [math]m_{k}=1, m_{i} \in \{ 0,1 \}[/math] и [math]x^{n}=x^{((...((m_{k} \cdot 2+m_{k-1}) \cdot 2+m_{k-2}) \cdot 2+...) \cdot 2+m_{1}) \cdot 2 + m_{0}}[/math].

Функция быстрого возведения в степень

Функция int Power(int value, int pow)

1. int result = 1;
2. while (pow) {
3.     if (pow & 1) result *= value;
4.     value *= value;
5.     pow >>= 1;
6. }
7. return result;

Ссылки

• BinPow and 2^k-ary pow
• Montgomerry Ladder