Умножение чисел со старших разрядов в прямом коде

Пусть два числа X и Y представлены с фиксированной запятой в виде:

[X]_пк = sign X.x₁x₂...x_n – множимое[Y]_пк = sign Y.y₁y₂...y_n – множитель

Представим множитель в виде:

[Y]_пк = sign Y. (y₁*2^-1 + y²*2^-2 +... + yⁿ*2^-n)

Тогда:

[Z]_пк = [X]_пк*[Y]_пк = sign Z. |X| (y₁*2^-1 + y₂*2^-2 +... + y_n*2^-n) = = sign Z. (|X|*y₁*2^-1 + |X|*y₂*2^-2 +... + |X|*y_n*2^-n) == sign Z. (|X|*2^-1*y₁ + |X|*2^-2*y₂ +... + |X|*2^-n*y_n)

Это есть аналитическая запись алгоритма умножения двух чисел, начиная со старшихразрядов множителя.

Алгоритм:

• Множимое сдвигается вправо на 1 разряд
• Анализируется цифра множителя. Если она – нуль, то частичное произведение не суммируется, а если она – единица, то частичное произведение добавляется к общему результату.
• Последовательность операций по пунктам 1 и 2 продолжается "n" раз.

· Знак произведения находится независимо от получения цифровой части по формуле:

sign Z = sign X sign Y

Пример:

Видно, что в общем случае нужно иметь для точного результата сетку с числом разрядов, равным сумме разрядностей сеток сомножителей.

Если нужно получать произведение с точностью не хуже, чем 2^-n, то достаточно иметь не удвоенную величину разрядной сетки, а лишь увеличенную на

d = log₂n разрядов

Дата добавления: 2014-01-06