Содержание
- 1 Теория
- 2 Содержание
- 3 Описание [ править | править код ]
- 4 Обобщения [ править | править код ]
- 5 Примеры решения задач [ править | править код ]
- 6 Схема «справа налево» [ править | править код ]
- 7 Вычислительная сложность [ править | править код ]
- 8 Оптимизация алгоритма [ править | править код ]
- 9 Применение [ править | править код ]
- 10 1 ответ 1
- 11 Всё ещё ищете ответ? Посмотрите другие вопросы с метками python python-3.x или задайте свой вопрос.
На данной странице калькулятор поможет возвести матрицу в степень онлайн с подробным решением. Для расчета задайте целые или десятичные числа.
Матрицу в степень
Теория
Возвести в степень можно только квадратную матрицу 2×2, 3×3 и т.д.
Чтобы возвести матрицу A в квадрат, нужно это матрицу умножить саму на себя.
Пример
Возвести матрицу А в квадрат.
Умножим матрицу A саму на себя.
Чтобы возвести матрицу A в куб, нужно это матрицу умножить саму на себя три раза.
A 3 = A · A · A = A 2 · A.
Пример
Возвести матрицу А в куб.
Умножим матрицу A саму на себя и найдем матрицу во второй степени.
Полученную матрицу умножим на исходную A.
Алгоритмы быстрого возведения в степень (дихотомический алгоритм возведения в степень, бинарный алгоритм возведения в степень) — алгоритмы, предназначенные для возведения числа 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^
Кроме того, некоторые алгоритмы для дальнейшей оптимизации используют тот факт, что операция возведения в квадрат быстрее операции умножения за счёт того, что при возведении в квадрат цифры в сомножителе повторяются [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 k = 1 , m i ∈ < 0 , 1 ><displaystyle m_
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 в двоичном виде
- Если 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^
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 <egin
Схема «справа налево» [ править | править код ]
В данной схеме, в отличие от схемы «слева направо», биты показателя степени просматриваются от младшего к старшему [5] .
Последовательность действий при реализации данного алгоритма.
- Представить показатель степени n в двоичном виде.
- Положить вспомогательную переменную z равной числу x.
- Если 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^
Пример. Посчитаем с помощью схемы возведения в степень «справа налево» значение 21 13 .
i | 1 | 2 | 3 | |
---|---|---|---|---|
a 2 i <displaystyle a^<2^>> | 21 | 441 | 194 481 | 37 822 859 361 |
m 1 <displaystyle m_<1>> | 1 | 1 | 1 |
- 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
Например, для возведения числа в сотую степень этим алгоритмом потребуется всего лишь 8 операций умножения и возведения в квадрат [5] .
Для сравнения, при стандартном способе возведения в степень требуется n − 1 <displaystyle n-1> операция умножения, то есть количество операций может быть оценено как O ( n ) <displaystyle O(n)> [10] .
Оптимизация алгоритма [ править | править код ]
Как правило, операция возведения в квадрат выполняется быстрее операции умножения. Метод окон позволяет сократить количество операций умножения и, следовательно, сделать алгоритм возведения в степень более оптимальным [8] .
Окно фактически представляет собой основание системы счисления [7] . Пусть w — ширина окна, то есть за один раз учитывается w знаков показателя.
Рассмотрим метод окна.
- Для i = 0 , 2 w − 1 ¯ <displaystyle i=<overline <0,2^
-1>>>заранее вычисляется x i - Показатель степени представляется в следующем виде: 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)>> - Пусть y — переменная, в которой будет вычислен конечный результат. Положим y = x n k / w <displaystyle y=x^>>.
- Для всех i = k/w — 1, k/w — 2, …, 0 выполнить следующие действия:
- y = y 2 w <displaystyle y=y^<2^
>> - y = y ⋅ x n i <displaystyle y=ycdot x^>>[8] .
В данном алгоритме требуется k возведений в квадрат, но число умножений в среднем сокращается до k/w [8] .
Ещё более эффективным является метод скользящего окна. Он заключается в том, что ширина окна во время выполнения процесса может изменяться:
- Показатель степени представляется в виде 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)>>, а ei+1 — ei ≥ w. - Для i = ( 1 , 3 , 5 , . . . , 2 w − 1 ) <displaystyle i=(1,3,5. 2^
-1)>вычисляется x i . Далее будем обозначать x i как xi. - Пусть y — переменная, в которой будет вычислен конечный результат. Положим y = x n l <displaystyle y=x^
>>. - Для всех i = l — 1, l — 2, …, 0 выполнить следующие действия:
- Для всех j от 0 до ei+1 — ei — 1 y возвести в квадрат
- j = m i <displaystyle j=m_>
- y = y ⋅ x j <displaystyle y=ycdot x_
>
Количество операций возведения в степень в данном алгоритме такое же, как и в методе окна, а вот количество операций умножений сократилось до l, то есть до k w + 1 <displaystyle <frac
Для примера возведём методом скользящего окна число x в степень 215. Ширина окна w = 3.
- 215 = 2 7 + 5 · 2 4 + 7
- y = 1
- y = y · x = x
- y 3 раза возводится в квадрат, так как на данном шаге e2 — e1 −1 = 7 — 4 — 1 = 2, а отсчёт ведётся с нуля, то есть y = y 8 = x 8
- y = y · x 5 = x 13
- y 4 раза возводится в квадрат, так как на данном шаге e1 — e −1 = 4 — 0 — 1 = 3, то есть y = y 16 = x 208
- y = y · x 7 = x 215
Применение [ править | править код ]
Алгоритм быстрого возведения в степень получил широкое распространение в криптосистемах с открытым ключом. В частности, алгоритм применяется в протоколе RSA, схеме Эль-Гамаля и других криптографических алгоритмах [11] .
Пытаюсь применить быстрое возведение числа в степень на матрицу, работать работает, но считает не корректно. Код который получился:
Что получилось при выполнении этого:
Результат выполнения кода:
В чем моя ошибка и как это исправить ?
1 ответ 1
При возведении матрицы в нулевую степень нужно возвращать единичную матрицу, а не исходную (которая получается при возведении в 1-ю степень). Из-за этого у вас выходит в результате возведение в четвёртую степень, а не во вторую.
Всё ещё ищете ответ? Посмотрите другие вопросы с метками python python-3.x или задайте свой вопрос.
Похожие
Для подписки на ленту скопируйте и вставьте эту ссылку в вашу программу для чтения RSS.
дизайн сайта / логотип © 2019 Stack Exchange Inc; пользовательское содержимое попадает под действие лицензии cc by-sa 4.0 с указанием ссылки на источник. rev 2019.11.15.35459