Алгоритм умножения 2 (оптимизированный по времени)

Разделим задачу на подзадачи, разделив запись каждого из сомножителей на две части: U= U₂U₁, V=V₂V₁. При n-разрядных сомножителях длины U_i, V_i будут равны n/2. Индексу 1 соответствует младшая половина, а индексу 2 - старшая. Иначе можно записать U = U₂00..00 + U₁ = U₂β^n/2 + U₁.

Произведение UV = (U₂β^n/2 + U₁)(V₂β^n/2 + V₁) = UVβⁿ + U₂V₁β^n/2 + U₁V₂β^n/2 + U₁V₁. Вычисление произведения предлагаемым способом требует четырех умножений чисел половинной длины, трех сложений и трех умножений на величину β^q. Умножения на степень β равносильны сдвигу и требуют времени O(n). То же можно сказать о сложности аддитивных операций.

Четырех умножений чисел оказывается слишком много: log₂4 = 2, сложность рекурсивного алгоритма будет равнаO(n²).

Но можно немного преобразовать расчетную формулу:

UV = U₂V₂(βⁿ + β^n/2) + (U₂ - U₁)(V₁-V₂)β^n/2 + U₁V₁(β^n/2+1)

Она содержит только три умножения. Очевидный алгоритм, строящийся по этой формуле, описывается уравнением для функции сложности:

Т(n) = 3Т(n/2) + βⁿ,

его решение Т(n) = O(n^log3) = O(n^1,58), что значительно лучше классического алгоритма.

На следующем шаге мы рассмотрим возведение целого числа без знака в положительную целую степень.

На этом шаге мы рассмотрим возведение целого числа без знака в положительную целую степень.

Вычисление у = хⁿ для вещественных x и n не представляет никакого труда: y = e^n*ln(x). Но для целых чисел этот способ неприменим, поскольку вычисления экспоненты и логарифма на цифровой вычислительной машине принципиально являются приближенными и не будут давать целочисленный результат. Не поможет здесь и округление, так как крайне трудно достоверно вычислить величину ошибки при приближенных расчетах, следовательно, не известно ни в какую сторону округлять, ни является ли истинным результатом ближайшее целое или ошибка составляет несколько единиц.

Особенно важна эта проблема для длинных целых x и больших n, что встречается в некоторых критических приложениях, например, в шифровании информации.

Правильный результат будет получен, если реализуем возведение в степень через целочисленное умножение. Решение "в лоб" - перемножение n экземпляров x, на что требуется (n-1) операция умножения.

Более остроумный метод состоит в том, чтобы на каждом шаге вычислений активно использовать достижения предыдущих шагов. Пусть, например, требуется вычислить x¹⁰²⁴. Вместо 1023 умножений можно построить следующую цепочку: х = х¹, х² = (x¹)², х⁴ = (x²)², x⁸ = (x⁴)², х¹⁶, х³², х⁶⁴, х¹²⁸, х²⁵⁶, х⁵¹², х¹⁰²⁴. На каждом шаге получается очередная степень x, которая на следующем шаге умножается сама на себя, т. е. предыдущее значение возводится в квадрат. Результат, таким образом, достигается за десять шагов.

Этот метод хорош, если n равно степени двойки. Его сложность равна log n умножений. Для других показателей он требует видоизменения.

Пусть, например, требуется вычислить х¹⁰²³. Очевидным подходом является достижение за девять умножений значения х⁵¹² и перемножение еще за девять операций всех ранее найденных степеней: 1023 = 1 + 2 + 4 + 8 + ... + 256 + 512. Интересно, что для меньшей степени (1023 < 1024) требуется на восемь умножений больше!

Для произвольного n можно использовать так называемый бинарный метод. Представим n его двоичной записью. Читая запись слева направо, начиная с первой значащей цифры (единицы), будем производить следующие действия: первую единицу игнорируем; переменной y присваиваем начальное значение, равное x; далее в цикле пока не закончились цифры - умножаем y на себя, а если очередная цифра равна единице, то дополнительно умножаем y наx. По окончании цикла в y находится значение xⁿ.

Эти действия можно описать следующей процедурой.

procedure BinaryMethod (x, n: integer; var у: integer);

Var

В: integer;

Begin

у:= x;

В:= NextBit(n);

while В = 0 do

В:= NextBit(n); {В B - первая единица.}

В:= NextBit(n);

while not Eon(n) do {Пока не закончилась запись числа n.}

Begin

у:= у*у;

if В = 1 then у:= у*х;

end;

end;

Сложность процедуры зависит от количества единиц λ(n) в записи числа n и может быть определена формулой:

Т(n) = log n + λ(n)-1.

Минимальная сложность получается для степеней двойки, n = 2^m-1, λ(n)=1. Максимальная сложность - для чисел n = 2_m-1:

λ(n) = log₂(n+l).

Что общего между рассмотренными методами оптимизации алгоритмов?

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

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

Эти рассуждения не претендуют на точность, но, вероятно, способны указать верный путь при оптимизации алгоритмов для других задач. Ярким примером является алгоритм быстрой сортировки Э.Хоара.