Главная
Статьи





26.05.2022


26.05.2022


26.05.2022


26.05.2022


26.05.2022






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

21.01.2022

Алгоритмы быстрого возведения в степень (дихотомический алгоритм возведения в степень, бинарный алгоритм возведения в степень) — алгоритмы, предназначенные для возведения числа x {displaystyle x} в натуральную степень n {displaystyle n} за меньшее число умножений, чем это требуется в определении степени. Алгоритмы основаны на том, что для возведения числа x {displaystyle x} в степень n {displaystyle n} не обязательно перемножать число x {displaystyle x} на само себя n {displaystyle n} раз, а можно перемножать уже вычисленные степени. В частности, если n = 2 k {displaystyle n=2^{k}} степень двойки, то для возведения в степень n {displaystyle n} достаточно число возвести в квадрат k {displaystyle k} раз, затратив при этом k {displaystyle k} умножений вместо 2 k {displaystyle 2^{k}} . Например, чтобы возвести число x {displaystyle x} в восьмую степень, вместо выполнения семи умножений x ⋅ x ⋅ x ⋅ x ⋅ x ⋅ x ⋅ x ⋅ x {displaystyle xcdot xcdot xcdot xcdot xcdot xcdot xcdot x} можно возвести число в квадрат ( x 2 = x ⋅ x {displaystyle x^{2}=xcdot x} ), потом результат возвести ещё раз в квадрат и получить четвёртую степень ( x 4 = x 2 ⋅ x 2 {displaystyle x^{4}=x^{2}cdot x^{2}} ), и наконец результат ещё раз возвести в квадрат и получить ответ ( x 8 = x 4 ⋅ x 4 {displaystyle x^{8}=x^{4}cdot x^{4}} ).

Кроме того, некоторые алгоритмы для дальнейшей оптимизации используют тот факт, что операция возведения в квадрат быстрее операции умножения за счёт того, что при возведении в квадрат цифры в сомножителе повторяются.

Бинарный алгоритм возведения в степень был впервые предложен в XV веке персидским математиком Аль-Каши.

Данные алгоритмы не всегда оптимальны. Например, при использовании схемы «слева направо» быстрое возведение в степень n = 15 потребует выполнения трёх операций умножения и трёх операций возведения в квадрат, хотя возведение в 15-ю степень можно выполнить и за 3 умножения и 2 возведения в квадрат. Оптимальное возведение в степень соответствует построению кратчайшей аддитивной цепочки.

Описание

Основным алгоритмом быстрого возведения в степень является схема «слева направо». Она получила своё название вследствие того, что биты показателя степени просматриваются слева направо, то есть от старшего к младшему.

Пусть

n = ( m k m k − 1 . . . m 1 m 0 ¯ ) 2 {displaystyle n=({overline {m_{k}m_{k-1}...m_{1}m_{0}}})_{2}} — двоичное представление степени n, то есть, n = m k ⋅ 2 k + m k − 1 ⋅ 2 k − 1 + ⋯ + m 1 ⋅ 2 + m 0 , {displaystyle 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 ∈ { 0 , 1 } {displaystyle m_{k}=1,m_{i}in {0,1}} . Тогда

x n = x ( ( … ( ( m k ⋅ 2 + m k − 1 ) ⋅ 2 + m k − 2 ) ⋅ 2 + … ) ⋅ 2 + m 1 ) ⋅ 2 + m 0 = ( ( … ( ( ( x m k ) 2 ⋅ x m k − 1 ) 2 … ) 2 ⋅ x m 1 ) 2 ⋅ x m 0 {displaystyle 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}}} .

Последовательность действий при использовании данной схемы можно описать так:

  • Представить показатель степени n в двоичном виде
  • Если m i {displaystyle m_{i}} = 1, то текущий результат возводится в квадрат и затем умножается на x. Если m i {displaystyle m_{i}} = 0, то текущий результат просто возводится в квадрат. Индекс i изменяется от k-1 до 0.
  • Таким образом, алгоритм быстрого возведения в степень сводится к мультипликативному аналогу схемы Горнера:

    { s 1 = x s i + 1 = s i 2 ⋅ x m k − i i = 1 , 2 , … , k } . {displaystyle {egin{Bmatrix}s_{1}=xs_{i+1}=s_{i}^{2}cdot x^{m_{k-i}}i=1,2,dots ,kend{Bmatrix}}.}

    Обобщения

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

    a n = { a n = 1 a ∗ ( a n − 1 ) n > 1 {displaystyle a^{n}=left{{egin{array}{ll}a&n=1a*left(a^{n-1} ight)&n>1end{array}} ight.}

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

    Примеры решения задач

    Применяя алгоритм, вычислим 2113:

    13 10 = 1101 2 {displaystyle 13_{10}=1101_{2}} m 3 = 1 , m 2 = 1 , m 1 = 0 , m 0 = 1 {displaystyle m_{3}=1,m_{2}=1,m_{1}=0,m_{0}=1} 21 13 = ( ( ( 1 ⋅ 21 m 3 ) 2 ⋅ 21 m 2 ) 2 ⋅ 21 m 1 ) 2 ⋅ 21 m 0 = ( ( ( 1 ⋅ 21 1 ) 2 ⋅ 21 1 ) 2 ⋅ 21 0 ) 2 ⋅ 21 1 = ( ( ( 1 ⋅ 21 ) 2 ⋅ 21 ) 2 ⋅ 1 ) 2 ⋅ 21 = ( ( 21 2 ⋅ 21 ) 2 ) 2 ⋅ 21 = ( ( 441 ⋅ 21 ) 2 ) 2 ⋅ 21 = 85766121 2 ⋅ 21 = 154472377739119461 {displaystyle {egin{aligned}21^{13}&=(((1cdot 21^{m_{3}})^{2}cdot 21^{m_{2}})^{2}cdot 21^{m_{1}})^{2}cdot 21^{m_{0}}&=(((1cdot 21^{1})^{2}cdot 21^{1})^{2}cdot 21^{0})^{2}cdot 21^{1}&=(((1cdot 21)^{2}cdot 21)^{2}cdot 1)^{2}cdot 21&=((21^{2}cdot 21)^{2})^{2}cdot 21&=((441cdot 21)^{2})^{2}cdot 21&=85766121^{2}cdot 21&=154472377739119461end{aligned}}}

    Схема «справа налево»

    В данной схеме, в отличие от схемы «слева направо», биты показателя степени просматриваются от младшего к старшему.

    Последовательность действий при реализации данного алгоритма.

  • Представить показатель степени n в двоичном виде.
  • Положить вспомогательную переменную z равной числу x.
  • Если m i = 1 {displaystyle m_{i}=1} , то текущий результат умножается на z, а само число z возводится в квадрат. Если m i {displaystyle m_{i}} = 0, то требуется только возвести z в квадрат. При этом индекс i, в отличие от схемы слева направо, изменяется от 0 до k-1 включительно.
  • Данная схема содержит столько же умножений и возведений в квадрат, сколько и схема «слева направо». Однако несмотря на это, схема «слева направо» выгоднее схемы «справа налево», особенно в случае, если показатель степени содержит много единиц. Дело в том, что в схеме слева направо в операции result = result · x содержится постоянный множитель x. А для небольших x (что нередко бывает в тестах простоты) умножение будет быстрым. К примеру, для x = 2 мы можем операцию умножения заменить операцией сложения.

    Математическое обоснование работы данного алгоритма можно представить следующей формулой:

    d = a n = {displaystyle d=a^{n}=} = a ∑ i = 0 k m i ⋅ 2 i = {displaystyle =a^{sum _{i=0}^{k}m_{i}cdot 2^{i}}=} = a m 0 ⋅ a 2 m 1 ⋅ a 2 2 ∗ m 2 ⋅ . . . ⋅ a 2 k ∗ m k = {displaystyle =a^{m_{0}}cdot a^{2m_{1}}cdot a^{2^{2}*m_{2}}cdot ...cdot a^{2^{k}*m_{k}}=} = a m 0 ⋅ ( a 2 ) m 1 ⋅ ( a 2 2 ) m 2 ⋅ . . . ⋅ ( a 2 k ) m k = {displaystyle =a^{m_{0}}cdot (a^{2})^{m_{1}}cdot (a^{2^{2}})^{m_{2}}cdot ...cdot (a^{2^{k}})^{m_{k}}=} = ∏ i = 0 k ( a 2 i ) m i {displaystyle =prod _{i=0}^{k}{(a^{2^{i}})^{m_{i}}}} .

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

  • 21 · 194 481 = 4084 101
  • 4084 101 · 37 822 859 361 = 154 472 377 739 119 461
  • Вычислительная сложность

    И для схемы «слева направо», и для схемы «справа налево» количество операций возведения в квадрат одинаково и равно k, где k — длина показателя степени n в битах, k ∼ ln ⁡ n {displaystyle ksim ln {n}} . Количество же требуемых операций умножения равно весу Хэмминга, то есть количеству ненулевых элементов в двоичной записи числа n. В среднем требуется 1 2 ⋅ ln ⁡ n {displaystyle {frac {1}{2}}cdot ln {n}} операций умножения.

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

    Для сравнения, при стандартном способе возведения в степень требуется n − 1 {displaystyle n-1} операция умножения, то есть количество операций может быть оценено как O ( n ) {displaystyle O(n)} .

    Оптимизация алгоритма

    Как правило, операция возведения в квадрат выполняется быстрее операции умножения. Метод окон позволяет сократить количество операций умножения и, следовательно, сделать алгоритм возведения в степень более оптимальным.

    Окно фактически представляет собой основание системы счисления. Пусть w — ширина окна, то есть за один раз учитывается w знаков показателя.

    Рассмотрим метод окна.

  • Для i = 0 , 2 w − 1 ¯ {displaystyle i={overline {0,2^{w}-1}}} заранее вычисляется xi
  • Показатель степени представляется в следующем виде: n = ∑ i = 0 k / w n i ⋅ 2 i ⋅ w {displaystyle n=sum _{i=0}^{k/w}{n_{i}cdot 2^{icdot w}}} , где n i ∈ ( 0 , 1 , . . . , 2 w − 1 ) {displaystyle n_{i}in {(0,1,...,2^{w}-1)}}
  • Пусть y — переменная, в которой будет вычислен конечный результат. Положим y = x n k / w {displaystyle y=x^{n_{k/w}}} .
  • Для всех i = k/w — 1, k/w — 2, …, 0 выполнить следующие действия:
  • y = y 2 w {displaystyle y=y^{2^{w}}}
  • y = y ⋅ x n i {displaystyle y=ycdot x^{n_{i}}} .
  • В данном алгоритме требуется k возведений в квадрат, но число умножений в среднем сокращается до k/w.

    Ещё более эффективным является метод скользящего окна. Он заключается в том, что ширина окна во время выполнения процесса может изменяться:

  • Показатель степени представляется в виде n = ∑ i = 0 l n i ⋅ 2 e i {displaystyle n=sum _{i=0}^{l}{n_{i}cdot 2^{e_{i}}}} , где n i ∈ ( 1 , 3 , 5 , . . . , 2 w − 1 ) {displaystyle n_{i}in {(1,3,5,...,2^{w}-1)}} , а ei+1eiw.
  • Для i = ( 1 , 3 , 5 , . . . , 2 w − 1 ) {displaystyle i=(1,3,5,...,2^{w}-1)} вычисляется xi. Далее будем обозначать xi как xi.
  • Пусть y — переменная, в которой будет вычислен конечный результат. Положим y = x n l {displaystyle y=x^{n_{l}}} .
  • Для всех i = l — 1, l — 2, …, 0 выполнить следующие действия:
  • Для всех j от 0 до ei+1ei — 1 y возвести в квадрат
  • j = m i {displaystyle j=m_{i}}
  • y = y ⋅ x j {displaystyle y=ycdot x_{j}}
  • Для всех j от 0 до e0 — 1 y возвести в квадрат.
  • Количество операций возведения в степень в данном алгоритме такое же, как и в методе окна, а вот количество операций умножений сократилось до l, то есть до k w + 1 {displaystyle {frac {k}{w+1}}} в среднем.

    Для примера возведём методом скользящего окна число x в степень 215. Ширина окна w = 3.

  • 215 = 27 + 5 · 24 + 7
  • y = 1
  • y = y · x = x
  • y 3 раза возводится в квадрат, так как на данном шаге e2e1 −1 = 7 — 4 — 1 = 2, а отсчёт ведётся с нуля, то есть y = y8 = x8
  • y = y · x5 = x13
  • y 4 раза возводится в квадрат, так как на данном шаге e1e0 −1 = 4 — 0 — 1 = 3, то есть y = y16= x208
  • y = y · x7 = x215
  • Применение

    Алгоритм быстрого возведения в степень получил широкое распространение в криптосистемах с открытым ключом. В частности, алгоритм применяется в протоколе RSA, схеме Эль-Гамаля и других криптографических алгоритмах.