Бинарный алгоритм возведения в степень

Алгоритмы быстрого возведения в степень (дихотомический алгоритм возведения в степень, бинарный алгоритм возведения в степень) — алгоритмы, предназначенные для возведения числа x <displaystyle x> в натуральную степень n <displaystyle n> за меньшее число умножений, чем это требуется в определении степени [1] . Алгоритмы основаны на том, что для возведения числа x <displaystyle x> в степень n <displaystyle n> не обязательно перемножать число x <displaystyle x> на само себя n <displaystyle n> раз, а можно перемножать уже вычисленные степени. В частности, если n = 2 k <displaystyle n=2^> степень двойки, то для возведения в степень n <displaystyle n> достаточно число возвести в квадрат k <displaystyle k> раз, затратив при этом k <displaystyle k> умножений вместо 2 k <displaystyle 2^> . Например, чтобы возвести число 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>> ).

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

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

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

Содержание

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

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

n = ( m k m k − 1 . . . m 1 m 0 ¯ ) 2 <displaystyle n=(<overline m_. 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_cdot 2^+m_cdot 2^+dots +m_<1>cdot 2+m_<0>,>

где m k = 1 , m i ∈ < 0 , 1 ><displaystyle m_=1,m_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^=x^<((dots ((m_cdot 2+m_)cdot 2+m_)cdot 2+dots )cdot 2+m_<1>)cdot 2+m_<0>>=((dots (((x^>)^<2>cdot x^>)^<2>dots )^<2>cdot x^<1>>)^<2>cdot x^<0>>> [5] .

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

1. Представить показатель степени n в двоичном виде
2. Если m i <displaystyle m_>= 1, то текущий результат возводится в квадрат и затем умножается на x. Если m i <displaystyle m_>= 0, то текущий результат просто возводится в квадрат [6] . Индекс i изменяется от k-1 до 0 [7] .

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

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

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

1end>
ight.>"> a n = < a n = 1 a ∗ ( a n − 1 ) n >1 <displaystyle a^=left<<egina&n=1\a*left(a^
ight)&n>1end>
ight.> 1end>
ight."/>

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

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

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

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 <egin21^<13>&=(((1cdot 21^<3>>)^<2>cdot 21^<2>>)^<2>cdot 21^<1>>)^<2>cdot 21^<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>>

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

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

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

1. Представить показатель степени n в двоичном виде.
2. Положить вспомогательную переменную z равной числу x.

1. Если m i = 1 <displaystyle m_=1>, то текущий результат умножается на z, а само число z возводится в квадрат. Если m i <displaystyle m_>= 0, то требуется только возвести z в квадрат [6] . При этом индекс i, в отличие от схемы слева направо, изменяется от 0 до k-1 включительно [7] .

Данная схема содержит столько же умножений и возведений в квадрат, сколько и схема «слева направо». Однако несмотря на это, схема «слева направо» выгоднее схемы «справа налево», особенно в случае, если показатель степени содержит много единиц. Дело в том, что в схеме слева направо в операции result = result · x содержится постоянный множитель x. А для небольших x (что нередко бывает в тестах простоты) умножение будет быстрым. К примеру, для x = 2 мы можем операцию умножения заменить операцией сложения [7] .

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

d = a n = <displaystyle d=a^=> = a ∑ i = 0 k m i ⋅ 2 i = <displaystyle =a^<sum _^m_cdot 2^>=> = a m 0 ⋅ a 2 m 1 ⋅ a 2 2 ∗ m 2 ⋅ . . . ⋅ a 2 k ∗ m k = <displaystyle =a^<0>>cdot a^<2m_<1>>cdot a^<2^<2>*m_<2>>cdot . cdot a^<2^*m_>=> = a m 0 ⋅ ( a 2 ) m 1 ⋅ ( a 2 2 ) m 2 ⋅ . . . ⋅ ( a 2 k ) m k = <displaystyle =a^<0>>cdot (a^<2>)^<1>>cdot (a^<2^<2>>)^<2>>cdot . cdot (a^<2^>)^>=> = ∏ i = 0 k ( a 2 i ) m i <displaystyle =prod _^<(a^<2^>)^>>> [9] .

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

i	0	1	2	3
a 2 i <displaystyle a^<2^>>	21	441	194 481	37 822 859 361
m 1 <displaystyle m_<1>>	1	0	1	1

1. 21 · 194 481 = 4084 101
2. 4084 101 · 37 822 859 361 = 154 472 377 739 119 461

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

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

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

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

Оптимизация алгоритма [ править | править код ]

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

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

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

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

1. y = y 2 w <displaystyle y=y^<2^>>
2. y = y ⋅ x n i <displaystyle y=ycdot x^>>[8] .

В данном алгоритме требуется k возведений в квадрат, но число умножений в среднем сокращается до k/w [8] .

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

1. Показатель степени представляется в виде n = ∑ i = 0 l n i ⋅ 2 e i <displaystyle n=sum _^cdot 2^>>>, где n i ∈ ( 1 , 3 , 5 , . . . , 2 w − 1 ) <displaystyle n_in <(1,3,5. 2^-1)>>, а e_i+1 — e_i ≥ w.
2. Для i = ( 1 , 3 , 5 , . . . , 2 w − 1 ) <displaystyle i=(1,3,5. 2^-1)>вычисляется x i . Далее будем обозначать x i как x_i.
3. Пусть y — переменная, в которой будет вычислен конечный результат. Положим y = x n l <displaystyle y=x^>>.
4. Для всех i = l — 1, l — 2, …, 0 выполнить следующие действия:

1. Для всех j от 0 до e_i+1 — e_i — 1 y возвести в квадрат
2. j = m i <displaystyle j=m_>
3. y = y ⋅ x j <displaystyle y=ycdot x_>

Количество операций возведения в степень в данном алгоритме такое же, как и в методе окна, а вот количество операций умножений сократилось до l, то есть до k w + 1 <displaystyle <frac >> в среднем [8] .

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

1. 215 = 2 7 + 5 · 2 4 + 7
2. y = 1
3. y = y · x = x
4. y 3 раза возводится в квадрат, так как на данном шаге e₂ — e₁ −1 = 7 — 4 — 1 = 2, а отсчёт ведётся с нуля, то есть y = y 8 = x 8
5. y = y · x 5 = x 13
6. y 4 раза возводится в квадрат, так как на данном шаге e₁ — e₀ −1 = 4 — 0 — 1 = 3, то есть y = y 16 = x 208
7. y = y · x 7 = x 215

Применение [ править | править код ]

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

Рассматривается следующая задача: для заданного a (например, aR) и заданного n вычислить степень a n .

Для примера рассмотрим вычисление a 11 . Действуя «в лоб» последовательным умножением aaaaaaaaaaa, затратим 10 умножений. Действуя более изобретательно, можно получить результат всего за 5 умножений, а именно: 1) aa=a 2 ; 2) (a 2 ) (a 2 )=a 4 ; 3) a 4 a=a 5 ; 4) (a 5 ) (a 5 ) = a 10 ; 5) a 10 a = a 11 . Чтобы понять этот способ действий, рассмотрим естественное (рекурсивное) определение

(2.10)

и будем применять его последовательно. Например,

Вычисления следует выполнять в обратном порядке: сначала вычислить a 2 , затем a 5 и, наконец, a 11 .

Такой способ действий давно известен. Он называется «индийским» способом вычисления степени и впервые (около 200 года до н. э.) описан в древнем индийском трактате Чанда-сутра (исторические ссылки смотри у Д. Кнута в [2]).

Оказывается, что можно описать эти вычисления без ссылок на рекурсивное определение (2.10). Основную роль здесь будет играть двоичная система счисления. Рассмотрим двоичную запись показателя степени n, например: 11₁₀ = 1011₂. В этой последовательности нулей и единиц заменим каждый символ «0» на символ «К», а каждый символ «1» на пару символов «КУ». Для n = 1011₂ получим «КУККУКУ». Вычеркнем два первых слева символа «КУ» (они соответствуют первому слева символу «1» в двоичной записи). Для n = 1011₂ получим «ККУКУ». Установим текущий результат равным a. Далее читаем полученную последовательность слева направо и выполняем следующие действия: если встретился символ «У», то умножаем текущее значение на a, если же очередной символ есть «К», то возводим текущее значение в квадрат. Для нашего примера при n = 1011₂ получим:

В общем случае обосновать эти действия можно следующим образом. Пусть вычислено b = a m . Рассмотрим число M = 2m + , где  = 0 или 1. Переход от числа m к числу M соответствует приписыванию справа к двоичной записи числа m одного бита . Тогда имеем a M = a 2 m +  = (a m ) 2 a  . При  = 0 получаем a M = (a m ) 2 , что соответствует операции «К», а при  = 1 получаем a M = (a m ) 2 a, что соответствует операции «КУ». Вся последовательность действий получается в результате чтения двоичной записи показателя степени n слева направо и обработки очередного бита  указанным ранее способом. Подсчитаем общее количество умножений, выполняемых при «индийском» способе. Длина двоичной записи числа n равна log₂ n + 1. Пусть N1(n) есть число единиц в двоичной записи числа n. Тогда общее количество операций умножения и возведения в квадрат (с учётом отбрасывания первых символов «КУ») будет log₂ n + 1 + N1(n)  2 или log₂ n + N1(n)  1.

Рассмотренный алгоритм можно назвать бинарным методом «слева направо». Для компьютерной реализации более эффективным оказывается аналогичный бинарный алгоритм, основанный на анализе двоичной записи показателя степени справа налево. Опишем процесс разработки этого алгоритма, основанный на конструктивном использовании понятия инварианта цикла.

Для начала рассмотрим более простую вспомогательную задачу вычисления по заданному n функции N1(n)  числа единиц в двоичной записи числа n. Приведём примеры: N1(11₁₀) = N1(1011₂) = 3, N1(32₁₀) = N1(100000₂) = 1, N1(31₁₀) = N1(11111₂) = 5.

Анализ двоичной записи числа n справа налево выполним, используя булевскую функцию Odd(n): если справедливо Odd(n), т. е. n нечётно, то последний (крайний справа) бит в двоичной записи n есть 1; если же справедливо not Odd(n), т. е. n чётно, то последний бит в двоичной записи n есть 0. Переход к следующему слева биту осуществляется операцией n div 2. Пусть выполнено i таких шагов (0

Для возведения числа x в степень n, как правило, используют стандартный метод, т. е. число x умножают n раз само на себя. В задачах математического толка, решаемых при помощи бумаги и ручки, такой метод вполне приемлем, ведь степенная функция быстро растет и поэтому сомнительно, что придется производить затруднительные операции вручную.

Другое дело программирование, где важно не только решить поставленную задачу, но и составить оптимальное решение, удовлетворяющее предусмотренному диапазону входных данных. Так, в частности, для операции возведения числа в степень имеется алгоритм, позволяющий значительно сократить число требуемых операций. Он достаточно прост и основывается на математических свойствах степеней.

Пусть имеется некоторая степень x n , где x – действительное число, а n – натуральное. Тогда для x n справедливо равенство:

x n = (x m ) k

При этом m*k=n. Например: 3 6 =(3 3 ) 2 , 5 7 =(5 7 ) 1 . Это свойство является одним из основных степенных свойств, и именно на нем основывается рассматриваемый метод. Далее, заметим, что в случае, если n является четным числом, то верно следующее равенство:

x n = (x n/2 ) 2 = x n/2 * x n/2

Так, если x=3, а n=6, то имеем 3 6 = (3 6/2 ) 2 = 3 6/2 * 3 6/2 . Используя это свойство, удастся существенно уменьшить число операций необходимых для возведения x в степень n. Теперь адаптируем формулу для случая с нечетным n. Для этого понадобиться просто перейти к степени на единицу меньшей. Например: 5 7 = 5 6 *5, 12 5 = 12 4 *12. Общая форма равенства перехода:

x n = x n-1 *x

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