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

Пусть два числа 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_n*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" раз.
• Знак произведения находится независимо от получения цифровой части по формуле:

Пример:

 

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

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

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

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

Напишем выражение для произведения двух чисел в несколько изменённом виде, а именно:

[Z]_пк = [X]_пк*[Y]_пк =

= sign Z.(|X|*y₁*2^-1 + |X|*y₂*2^-2 +... + |X|*y_n*2^-n) =

= sign Z.( |X|*2^-1*y₁ + 2^-1 (|X|*2^-1*y₂ + 2^-1 (|X|*2^-1*y₃ + (...)))) =

= sign Z. ((...(( |X|*y_n*2^-1 + |X|*y_n-1)2^-1 + |X|*y_n-2)2^-1 +... +

+ |X|*y₂ )2^-1 + |X|*y₁ )*2^-1

Это выражение называется преобразованием по схеме Горнера и задаёт алгоритм умножения с младших разрядов множителя.

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

• Анализируется младшая цифра множителя. Если она равна " 1", то множимое участвует в формировании части произведения. В противном случае – не участвует.
• Полученное частичное произведение сдвигается вправо на 1 разряд.
• Операции по пунктам 1 и 2 выполняются до старшего разряда.

Пример:

 

Замечание.

Для получения произведения с точностью не ниже, чем 2^-n нужно иметь только " n" – разрядную сетку.

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

Однако, известно, что числа могут быть представлены в различных кодах(это, прежде всего, отрицательные числа).

Мы уже знаем, как выполняется операция суммирования чисел (в том числе и с разными знаками).

Однако микрооперация сдвига имеет некоторые особенности:

 

Сдвиг вправо:

 

Сдвиг влево возможен только в случае, если сдвинутое число меньше единицы по модулю:

Исходные числа:

Если чисто формально сделать преобразование выражения некоторого числа, записанного в прямом коде до выполнения сдвига и после выполнения микрооперации сдвига, в обратный модифицированный код, то:

 

То есть при сдвиге вправо отрицательного числа старшие разряды заполняются единицами. При сдвиге влево в старшие и младшие разряды пишутся единицы.

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

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

Алгоритм:

[Z]_дк = (...(0+[X]_дк*[y_n+1 – y_n])*2^-1 + [X]_дк*[y_n – y_n-1])*2^-1 +...

... + [X]_дк*[y₂ – y₁])*2^-1 + [X]_дк*[y₁ – y₀]

Если y_n = y_{n+ 1}, то производится сдвиг частичного произведения.

Если y_n = 0 и y_n+1 = 1, то к частичному произведению прибавляется [X]_дк

Если y_n = 1 и y_n+1 = 0, то из частичного произведения вычитается [X]_дк.

Пример:

 

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

[Z]_дк = [X]_дк*[Y]_дк = [X]_дк*(y₁ – y₀ ) + [X]_дк*(y₂ – y₁ )*2^-1 +... +

+ [X]_дк*(y_n+1 – y_n )*2^-n

 

[-X]_дк = 1.01011

[Z]_дк = [-X]_дк + [X]*2^-1 + [X]_дк*2^-2*0 + [-X]_дк*2^-3 +

+ [X]_дк*2^-4 + [-X]_дк*2^-5

₊1.01011 [-X]_дк

0.010101 [X]_дк*2^-1

________

₊1.101011

1.11101011 [-X]_дк*2^-3

__________

₊1.10010111

0.000010101 [X]_дк*2^-4

___________

₊1.101000011

1.1111101011 [-X]_дк*2^-5

____________

1.1001110001

Ответ: [Z]_дк = 1.1001110001

 

1. Лекция: Деление

Содержание

· Деление в прямом коде со сдвигом и автоматическим восстановлением остатка

· Деление в прямом коде со сдвигом делителя и автоматическим восстановлением остатка

· Деление в дополнительном (обратном) кодах со сдвигом и автоматическим восстановлением остатка

· Арифметические операции над числами, представленными с плавающей запятой

o Умножение:

o Деление

o Сложение и вычитание

· Десятичные двоично-кодированные системы.

Реализация операции деления в ЭВМ в двоичной системе счисления выполняется проще, чем в десятичной. Это объясняется тем, что при определении каждой цифры частного нужно сделать только одну пробу.

Если числа X и Y заданы в прямом коде, и они представлены с фиксированной запятой, то для выполнения деления используются два основных алгоритма:

· со сдвигом и автоматическим восстановлением остатка;

· со сдвигом делителя и автоматическим восстановлением остатка.

Пусть: [X]_пк = sign X. x₁x₂..x_n

[Y]_пк = sign Y. y₁y₂..y_n

[Z]_пк = [X]_пк/[Y]_пк = sign Z. z₁z₂..z_n

X и Y должны быть такими, чтобы:

|Z| < 1 (то есть фиксированная запятая )

⇐ Предыдущая1234Следующая ⇒

Поделиться: