Возведение в степень по цепочке сложения
В математике и информатике оптимальное возведение в степень с помощью цепочки сложения — это метод возведения в степень по положительной целой степени , требующий минимального количества умножений. Используя форму кратчайшей цепочки сложения с умножением вместо сложения, вычисляет желаемый показатель степени (вместо кратного) основания . (Это соответствует последовательности OEIS A003313 (длина кратчайшей цепочки сложения для n) .) Каждое возведение в степень в цепочке можно оценить путем умножения двух предыдущих результатов возведения в степень. В более общем смысле, возведение в степень цепочки сложения может также относиться к возведению в степень с помощью неминимальных цепочек сложения, построенных с помощью различных алгоритмов (поскольку кратчайшую цепочку сложения очень трудно найти).
кратчайшей цепочки сложения Алгоритм требует не больше умножений, чем возведение в степень двоичного кода , а обычно и меньше. Первый пример того, где это работает лучше, — это 15 , где двоичный метод требует шести умножений, а самая короткая цепочка сложения требует только пяти:
- (двоичный, 6 умножений)
- (кратчайшая цепочка сложения, 5 умножений).
- (также кратчайшая цепочка сложения, 5 умножений).
![{\displaystyle a^{15}=a\times (a\times [a\times a^{2}]^{2})^{2}\!}](https://wikimedia.org/api/rest_v1/media/math/render/svg/df6b0c397c4ac1d81a12becfd276b0ba6382daa3)
![{\displaystyle a^{15}=([a^{2}]^{2}\times a)^{3}\!}](https://wikimedia.org/api/rest_v1/media/math/render/svg/8289fd09aadb110020e879df956790cf70b20c0a)
![{\displaystyle a^{15}=a^{3}\times ([a^{3}]^{2})^{2}\!}](https://wikimedia.org/api/rest_v1/media/math/render/svg/3e5cd212acf5a014ca9f7a8e8e44923b91010b73)
| Количество умножения | Действительный возведение в степень | Конкретная реализация цепочки сложения для возведения в степень |
|---|---|---|
| 0 | а 1 | а |
| 1 | а 2 | а × а |
| 2 | а 3 | а × а × а |
| 2 | а 4 | (а × а → б) × б |
| 3 | а 5 | (а × а→б) × б × а |
| 3 | а 6 | (а × а→б) × б × б |
| 4 | а 7 | (а × а→б) × б × б × а |
| 3 | а 8 | ((a × a→b) × b→d) × d |
| 4 | а 9 | (а × а × а → с) × с × с |
| 4 | а 10 | ((a × a→b) × b→d) × d × b |
| 5 | а 11 | ((a × a→b) × b→d) × d × b × a |
| 4 | а 12 | ((a × a→b) × b→d) × d × d |
| 5 | а 13 | ((a × a→b) × b→d) × d × d × a |
| 5 | а 14 | ((a × a→b) × b→d) × d × d × b |
| 5 | а 15 | ((a × a→b) × b × a→e) × e × e |
| 4 | а 16 | (((a × a→b) × b→d) × d→h) × h |
С другой стороны, определить кратчайшую цепочку сложения сложно: в настоящее время не известны эффективные оптимальные методы для произвольных показателей, а связанная с этим проблема поиска кратчайшей цепочки сложения для заданного набора показателей оказалась NP-полной . [1] Даже при наличии самой короткой цепочки возведение в степень сложения требует больше памяти, чем двоичный метод, поскольку потенциально он должен хранить множество предыдущих показателей из цепочки. Таким образом, на практике возведение в степень кратчайшей цепочки сложения в основном используется для небольших фиксированных показателей, для которых кратчайшая цепочка может быть вычислена заранее и не слишком велика.
Существует также несколько методов аппроксимации кратчайшей цепочки сложения, которые часто требуют меньшего количества умножений, чем возведение в степень двоичного кода; Бинарное возведение в степень само по себе является неоптимальным алгоритмом цепочки сложения. Выбор оптимального алгоритма зависит от контекста (например, относительной стоимости умножения и количества повторных использований данного показателя степени). [2]
Проблема нахождения кратчайшей цепочки сложения не может быть решена с помощью динамического программирования , поскольку оно не удовлетворяет предположению об оптимальной подструктуре . То есть недостаточно разложить степень на меньшие степени, каждая из которых вычисляется минимально, поскольку цепочки сложения для меньших степеней могут быть связаны (для совместного использования вычислений). Например, в кратчайшей цепочке сложения для 15 выше, подзадача для 6 должно быть рассчитано как ( a 3 ) 2 с тех пор как 3 используется повторно (в отличие, скажем, от 6 = а 2 ( а 2 ) 2 , что также требует трёх умножений).
Сложение-вычитание-цепное возведение в степень
[ редактировать ]Если разрешены и умножение, и деление, то можно использовать цепочку сложения-вычитания , чтобы получить еще меньшее общее количество умножений + делений (где вычитание соответствует делению). Однако медлительность деления по сравнению с умножением делает этот метод в целом малопривлекательным. С другой стороны, для возведения в степень до отрицательных целых степеней, поскольку в любом случае требуется одно деление, часто бывает полезна цепочка сложения-вычитания. Одним из таких примеров является −31 , где вычисление 1/ a 31 кратчайшей цепочкой сложения для 31 требуется 7 умножений и одно деление, тогда как самая короткая цепочка сложения-вычитания требует 5 умножений и одного деления:
- (цепочка сложения-вычитания, 5 множений + 1 деление).
Для возведения в степень на эллиптических кривых обратная точка ( x , y ) доступна бесплатно, поскольку это просто ( x , − y ), и поэтому цепочки сложения-вычитания оптимальны в этом контексте даже для положительных целых показателей степени. [3]
Ссылки
[ редактировать ]- ^ Дауни, Питер; Леонг, Бентон; Сетхи, Рави (1981). «Вычисление последовательностей с цепочками сложения». SIAM Journal по вычислительной технике . 10 (3): 638–646. дои : 10.1137/0210047 .
- ^ Гордон, Дэниел М. (1998). «Обзор методов быстрого возведения в степень» (PDF) . Дж. Алгоритмы . 27 : 129–146. CiteSeerX 10.1.1.17.7076 . дои : 10.1006/jagm.1997.0913 .
- ^ Франсуа Морен и Хорхе Оливос, « Ускорение вычислений на эллиптической кривой с использованием цепочек сложения-вычитания », RAIRO Informatique théoretique et application 24 , стр. 531-543 (1990).
- Дональд Э. Кнут , Искусство компьютерного программирования, Том 2: Получисловые алгоритмы , 3-е издание, §4.6.3 (Аддисон-Уэсли: Сан-Франциско, 1998).
- Дэниел Дж. Бернштейн, « Алгоритм Пиппенджера », будет включен в авторскую книгу по высокоскоростной криптографии . (2002)