Введение

Метод возведения в степень положительными целыми числами, требующий минимального количества умножений. В математике и информатике оптимальное возведение в степень с использованием цепочки сложений — это метод возведения в степень с положительной целой степенью, требующий минимального количества умножений. Используя форму кратчайшей цепочки сложений, с умножением вместо сложения, вычисляется желаемая степень (вместо произведения) основания. (Это соответствует .) Каждое возведение в степень в цепочке можно вычислить, умножив два предыдущих результата возведения в степень. В более общем смысле, возведение в степень с использованием цепочки сложений может также относиться к возведению в степень с использованием неоптимальных цепочек сложений, построенных различными алгоритмами (поскольку найти кратчайшую цепочку сложений очень сложно). Алгоритм с кратчайшей цепочкой сложений не требует большего количества умножений, чем двоичное возведение в степень, и обычно требует меньше. Первый пример, когда он оказывается лучше, — это для a15, где двоичный метод требует шести умножений, а кратчайшая цепочка сложений — только пяти: (двоичный метод, 6 умножений) (кратчайшая цепочка сложений, 5 умножений). (также кратчайшая цепочка сложений, 5 умножений). Даже при наличии кратчайшей цепочки, возведение в степень с использованием цепочки сложений требует больше памяти, чем двоичный метод, поскольку ему потенциально необходимо хранить многие предыдущие степени из цепочки. Поэтому на практике возведение в степень с использованием кратчайшей цепочки сложений в основном используется для небольших фиксированных степеней, для которых кратчайшая цепочка может быть предварительно вычислена и не слишком велика. Существуют также несколько методов для приближения кратчайшей цепочки сложений, которые часто требуют меньше умножений, чем двоичное возведение в степень; само двоичное возведение в степень является субоптимальным алгоритмом цепочки сложений. Выбор оптимального алгоритма зависит от контекста (например, от относительной стоимости умножения и количества повторных использований заданной степени). Проблему нахождения кратчайшей цепочки сложений нельзя решить с помощью динамического программирования, поскольку она не удовлетворяет предположению об оптимальной подструктуре. То есть, недостаточно разложить степень на меньшие степени, каждая из которых вычисляется минимально, поскольку цепочки сложений для меньших степеней могут быть связаны (для совместного использования вычислений). Например, в кратчайшей цепочке сложений для a15, подзадача для a6 должна быть вычислена как (a3)², поскольку a3 повторно используется (в отличие от, скажем, a6 = a2 * (a2)², что также требует трех умножений).

Добавление-вычитаниепоказатель цепи

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