Алгоритм быстрого возведения в степень

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

Алгоритм не всегда оптимален: например, быстрое возведение в степень n = 15 потребует 6 умножений, хотя возведение в 15-ю степень можно выполнить и за 5 умножений.

Описание[править | править вики-текст]

Пусть n=(\overline {m_{k}m_{k-1}...m_{1}m_{0}})_2 — двоичное представление степени n, то есть,

n=m_{k} \cdot 2^{k}+m_{k-1} \cdot 2^{k-1}+\dots+m_{1} \cdot 2+m_{0},

где m_{k}=1, m_{i} \in \{ 0,1 \}. Тогда

x^{n}=x^{((\dots((m_{k} \cdot 2+m_{k-1}) \cdot 2+m_{k-2}) \cdot 2+\dots) \cdot 2+m_{1}) \cdot 2 + m_{0}}=((\dots(((x^{m_{k}})^{2} \cdot x^{m_{k-1}})^{2}\dots)^{2} \cdot x^{m_{1}})^2 \cdot x^{m_{0}}.

Таким образом, алгоритм быстрого возведения в степень сводится к мультипликативному аналогу схемы Горнера:

\begin{Bmatrix} s_1=x \\ s_{i+1}=s_i^2 \cdot x^{m_{k-i}} \\ i=1,2,\dots,k \end{Bmatrix}.

Реализация[править | править вики-текст]

Реализация алгоритма на С++:

double power(double x, long n)
{
    double result = 1.0;
    while (n != 0)
    {
        if (n % 2 != 0)
        {
            result *= x;
            n -= 1;
        }
        x *= x;
        n /= 2;
    }
    return result;
}

Вычислительная сложность[править | править вики-текст]

Количество умножений, требуемое для возведения числа x в степень n алгоритмом быстрого возведения в степень, даётся формулой: H+2(E-1), где H — количество нулей, а E — количество единиц в двоичной записи числа n. Таким образом, количество умножений равно  O(\log_2{n}) .

Например, для возведения числа в сотую степень этим алгоритмом потребуется всего лишь 8 умножений.

Обобщения[править | править вики-текст]

Пусть пара (S, *) — полугруппа, то есть S — произвольное множество, на котором задана бинарная операция * такая, что:

  • Для любых элементов a и b из S справедливо: (a * b) так же из S. (замкнутость)
  • Для любых элементов a, b и c из S справедливо: ((a * b) * c) = (a * (b * c)). (ассоциативность)

Мы можем назвать операцию * умножением и определить операцию возведения в натуральную степень:

a^n=\left\{ \begin{array}{ll} a & n = 1 \\ a * \left(a^{n-1}\right) & n > 1 \end{array} \right.

Для вычисления значений an можно использовать алгоритм быстрого возведения в степень.

Примеры решения задач[править | править вики-текст]

Применяя алгоритм, быстро вычислим 595703 (mod 991):

Имеем n = 703 =(1010111111)2 = 20+21+22+23+24+25+ 27+29.

595703 = ((((((((5952)2*595)2)2* 595)2*595)2 * 595)2*595)2*595)2*595

= ((((((( 2382*595)2)2* 595)2*595)2 * 595)2*595)2*595)2*595

= (((((( 2612)2* 595)2*595)2 * 595)2*595)2*595)2*595

= ((((( 7332* 595)2*595)2 * 595)2*595)2*595)2*595

= ((((( 167* 595)2*595)2 * 595)2*595)2*595)2*595

= (((( 2652*595)2 * 595)2*595)2*595)2*595

= ((( 3422 * 595)2*595)2*595)2*595

= (( 6052*595)2*595)2*595

= ( 7332*595)2*595

= ( 167*595)2*595

= 2652*595

= 342.

Схема «справа налево»[править | править вики-текст]

Другим вариантом является схема типа «справа налево». Её можно представить следующей формулой:

d = a^n =

= a^{\sum_{i=0}^k m_i* 2^i} =

= a^{m_0}* a^{2m_1}* a^{2^2*m_2}* ... * a^{2^k*m_k}=

= a^{m_0}* (a^2)^{m_1}* (a^{2^2})^{m_2}* ... * (a^{2^k})^{m_k}=

 = \prod_{i=0}^k {(a^{2^{i}})^{m_i}}

Пример. Посчитаем с помощью простой двоичной схемы возведения в степень типа «справа налево» значение 175235 mod 257.

Представим число 235 в двоичном виде:

23510 = 111010112.

1. d := 1 * 175 mod 257 = 175,

t := 1752 mod 257 = 42;

2. d := 175 * 42 mod 257 = 154,

t := 422 mod 257 = 222;

3. t := 2222 mod 257 = 197;

4. d := 154 * 197 mod 257 = 12,

t := 1972 mod 257 = 2;

5. t := 22 mod 257 = 4;

6. d := 12 * 4 mod 257 = 48,

t := 42 mod 257 = 16;

7. d := 48 * 16 mod 257 = 254,

t := 162 mod 257 = 256;

8. d := 254 * 256 mod 257 = 3,

9. → d = 3. Потребовалось 7 возведений в квадрат и 5 умножений.

См. также[править | править вики-текст]

Ссылки[править | править вики-текст]