Методы ускорения умножения

Рассмотренный в предыдущей теме материал показывает, что умножение – это достаточно длинная операция, состоящая из N суммирований и сдвигов, а также выделений очередных цифр множителя.

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

· на аппаратные;

· логические (алгоритмические);

· комбинированные.

 

Аппаратные методы

1. Распараллеливание вычислительных операций. Например, совмещение во времени суммирования и сдвига.

2. Табличное умножение. Это довольно распространенный способ реализации различных функций. Остановимся на нем подробнее.

Пусть X и Y – целые числа длиной в 1 байт. Надо вычислить Z=X*Y. Можно использовать 65 Кбайт памяти и занести в них значения Z для всех возможных комбинаций X и Y, а сомножители X и Y использовать в качестве адреса. Получается своеобразная таблица следующего вида:

 

 

Алгоритмические методы

Эти методы разнообразны. Приведем только один пример: при S=16 можно за один такт обрабатывать несколько разрядов множителя (4 разряда). Сдвиги тоже осуществляются на 4 разряда. Следует отметить, однако, что в большинстве случаев алгоритмические методы требуют определенную аппаратную поддержку.

 

Комбинированные методы

Рассмотрим пример. Пусть X и Y – 16-разрядные числа. Надо вычислить произведение вида Z=X*Y. Использовать непосредственно табличный метод не удастся, поскольку для этих целей потребуется очень большой объем памяти. Однако можно представить каждый сомножитель как сумму двух 16-разрядных слагаемых, каждое из которых представляет группы старших и младших разрядов сомножителей. В этом случае произведение примет вид

 

Z = X*Y = (x₁₅ ... x₀)*(y₁₅ ... y₀) =

= (x₁₅...x₈000...0 + 000...0x₇...x₀)* (y₁₅...y₈000...0 + 000...0y₇...y₀) =

= 2¹⁶(x₁₅...x₈) (y₁₅...y₈) + 2⁸(x₁₅...x₈) (y₇...y₀) + 2⁸(x₇...x₀) (y₁₅...y₈) +

+ (x₇...x₀)*(y₇...y₀) .

 

Таким образом, произведение раскладывается на простые 8-разрядные сомножители. Эти произведения 8-разрядных операндов вычисляются табличным методом, а затем следует сдвиг слагаемых сразу на 16,8,8,0 разрядов и суммирование.