В математике и информатике оптимальное возведение в степень сложения - это метод возведения в степень положительными целыми степенями, который требует минимального числа умножений. Это соответствует последовательности A003313 в Интернет-энциклопедии целочисленных последовательностей . Он работает, создавая кратчайшую цепочку сложения, которая генерирует желаемый показатель степени. Каждое возведение в степень в цепочке можно оценить, умножив два предыдущих результата возведения в степень. В более общем смысле, возведение в степень аддитивной цепи может также относиться к возведению в степень с помощью неминимальных цепочек сложения, построенных с помощью различных алгоритмов (так как самую короткую цепочку сложения очень трудно найти).
Алгоритм кратчайшей цепочки сложения требует не больше умножений, чем двоичное возведение в степень, а обычно меньше. Первый пример того, где это лучше, - это 15 , где двоичный метод требует шести умножений, а для самой короткой цепочки сложения требуется только пять:
- (двоичный, 6 умножений)
- (кратчайшая цепочка сложения, 5 умножений).
Количество умножений | Фактическое возведение в степень | Конкретная реализация дополнительных цепочек для возведения в степень |
---|---|---|
0 | а 1 | а |
1 | а 2 | а × а |
2 | а 3 | а × а × а |
2 | а 4 | (а × а → б) × б |
3 | а 5 | (a × a → b) × b × a |
3 | а 6 | (a × a → b) × b × b |
4 | а 7 | (a × a → b) × b × b × a |
3 | а 8 | ((a × a → b) × b → d) × d |
4 | а 9 | (a × a × a → c) × c × c |
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 должна быть вычислена как ( 3 ) 2 , так как в 3 повторно используются (в отличие от, скажем, 6 = 2 ( 2 ) 2 , что также требует трех умножений).
Сложение-вычитание-цепное возведение в степень
Если разрешены как умножение, так и деление, то можно использовать цепочку сложения-вычитания для получения еще меньшего общего числа умножений + делений (где вычитание соответствует делению). Однако медленность деления по сравнению с умножением делает этот метод в целом непривлекательным. С другой стороны, для возведения в степень до отрицательных целых степеней, поскольку в любом случае требуется одно деление, часто бывает полезна цепочка сложения-вычитания. Одним из таких примеров являются -31 , где вычисление 1/ 31 кратчайшей аддитивной цепочкой для 31 требует 7 умножений и одно деления, а самая короткая аддитивного вычитание цепь требует 5 умножений и одно деления:
- (цепочка сложение-вычитание, 5 умножений + 1 деление).
Для возведения в степень на эллиптических кривых обратная точка ( x , y ) доступна бесплатно, так как это просто ( x , - y ), и поэтому цепочки сложения-вычитания оптимальны в этом контексте даже для положительных целых показателей. [3]
Рекомендации
- ^ Дауни, Питер; Леонг, Бентон; Сетхи, Рави (1981). «Вычислительные последовательности с добавлением цепочек». SIAM Journal on Computing . 10 (3): 638–646. DOI : 10.1137 / 0210047 .
- ^ Гордон, Д.М. (1998). «Обзор методов быстрого возведения в степень» (PDF) . J. Алгоритмы . 27 : 129–146. CiteSeerX 10.1.1.17.7076 . DOI : 10.1006 / jagm.1997.0913 . Архивировано из оригинального (PDF) 11 ноября 2013 года . Проверено 11 ноября 2013 .
- ^ Франсуа Морен и Хорхе Оливос, « Ускорение вычислений на эллиптической кривой с использованием цепочек сложения-вычитания », RAIRO Informatique théoretique et application 24 , pp. 531-543 (1990).
- Дональд Э. Кнут , Искусство компьютерного программирования, Том 2: получисловые алгоритмы , 3-е издание, §4.6.3 (Аддисон-Уэсли: Сан-Франциско, 1998).
- Дэниел Дж. Бернштейн, « Алгоритм Пиппенгера» , будет включен в книгу автора по высокоскоростной криптографии . (2002)