Возведение в степень цепочки сложения

В математике и информатике оптимальная цепочка сложения возведение в степень - это метод возведения в степень положительными целыми степенями, который требует минимального количества умножений. Это соответствует последовательности A003313 в Онлайн-энциклопедии целочисленных последовательностей. Он работает путем создания кратчайшей цепочки сложения, которая генерирует желаемый показатель степени. Каждое возведение в степень в цепочке можно оценить, умножив два предыдущих результата возведения в степень. В более общем смысле, возведение в степень цепочки сложения может также относиться к возведению в степень с помощью неминимальных цепочек сложения, построенных с помощью множества алгоритмов (так как самую короткую цепочку сложения очень сложно найти).

Алгоритм кратчайшей цепочки сложения требует не больше умножений, чем двоичное возведение в степень, а обычно меньше. Первый пример того, где это лучше, - это для a, где для двоичного метода требуется шесть умножений, а для самой короткой цепочки сложения требуется только пять:

$a\; 15\; =\; a\; \times \; (a\; \times \; [a\; \times \; a\; 2]\; 2)\; 2\; \{\backslash \; displaystyle\; a\; ^\; \{15\}\; =\; a\; \backslash \; times\; (a\; \backslash \; times\; [a\; \backslash \; times\; a\; ^\; \{2\}]\; ^\; \{2\})\; ^\; \{2\}\; \backslash !\}$(двоичное, 6 умножений)

$a\; 15\; =\; a\; 3\; \times \; ([a\; 3]\; 2)\; 2\; \{\backslash \; displaystyle\; a\; ^\; \{15\}\; =\; a\; ^\; \{3\}\; \backslash \; times\; ([a\; ^\; \{3\}]\; ^\; \{2\})\; ^\; \{2\}\; \backslash !\; \}$(кратчайшая цепочка сложения, 5 умножений).

Таблица, демонстрирующая, как выполнить возведение в степень с использованием цепочек сложения

Количество. умножений	Фактическое. возведение в степень	Конкретная реализация. цепочек сложения для возведения в степень
0	a	a
1	a	a × a
2	a	a × a × a
2	a	(a × a → b) × b
3	a	(a × a → b) × b × a
3	a	(a × a → b) × b × b
4	a	(a × a → b) × b × b × a
3	a	((a × a → b) × b → d) × d
4	a	(a × a × a → c) × c × c
4	a	((a × a → b) × b → d) × d × b
5	a	((a × a → b) × b → d) × d × b × a
4	a	((a × a → b) × b → d) × d × d
5	a	((a × a → b) × b → d) × d × d × a
5	a	((a × a → b) × b → d) × d × d × b
5	a	((a × a → b) × b × a → e) × e × e
4	a	(((a × a → b) × b → d) × d → h) × h

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

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

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

Если разрешены и умножение, и деление, тогда цепочка сложения-вычитания может использоваться для получения еще меньшего общего числа умножений + делений ( где вычитание соответствует делению). Однако медленность деления по сравнению с умножением делает эту технику в целом непривлекательной. С другой стороны, для возведения в степень до отрицательных целых степеней, поскольку в любом случае требуется одно деление, часто бывает полезна цепочка сложения-вычитания. Одним из таких примеров является a, где для вычисления 1 / a с помощью кратчайшей цепочки сложения для a требуется 7 умножений и одно деление, тогда как для самой короткой цепочки сложения-вычитания требуется 5 умножений и одно деление:

$a\; -\; 31\; =\; a\; /\; (((\; ((a\; 2)\; 2)\; 2)\; 2)\; 2\; \{\backslash \; displaystyle\; a\; ^\; \{-\; 31\}\; =\; a\; /\; ((((a\; ^\; \{2\})\; ^\; \{2\})\; ^\; \{2\})\; ^\; \{2\})\; ^\; \{2\}\; \backslash !\}$(цепочка сложения-вычитания, 5 множителей + 1 деление).

Для возведения в степень на эллиптических кривых, обратная точка (x, y) доступен бесплатно, так как это просто (x, −y), и поэтому цепочки сложения-вычитания оптимальны в этом контексте даже для положительных целых показателей.

• Donald E. Knuth, Искусство компьютерного программирования, Том 2: Получисловые алгоритмы, 3-е издание, §4.6.3 (Аддисон-Уэсли: Сан-Франциско, 1998).
• Дэниел Дж. Бернстайн, «Алгоритм Пиппенгера "для включения в книгу автора" Высокоскоростная криптография ". (2002)