Методические указания по организации самостоятельной работы студентов

Такой прием не является эффективным. Поэтому на практике чаще всего используют специальные алгоритмы умножения чисел в дополнительных кодах. Алгоритмы корректного умножения операндов в ( Методические указания по организации самостоятельной работы студентов - student2.ru ) можно разделить на две группы:

- алгоритмы первой группы это алгоритмы с обработкой знаковых разрядов отдельно от числовых;

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

Теорема: произведение дополнительных кодов сомножителей равно дополнительному коду результата только в случае положительных сомножителей.

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

Рассмотрим арифметическое обоснование алгоритмов первой группы при различных вариантах комбинаций знаков операндов. С этой целью у операндов отбрасывается знаковая цифра и выполняется умножение полученных псевдомодулей по одному из известных алгоритмов. Результат такого умножения назовем псевдопроизведением ( Методические указания по организации самостоятельной работы студентов - student2.ru ).

Обозначим вес знакового разряда сомножителей ( Методические указания по организации самостоятельной работы студентов - student2.ru ).

Тогда, в соответствии с рассмотренным ранее правилом формирования дополнительного кода, отрицательные сомножители будут представлены в ( Методические указания по организации самостоятельной работы студентов - student2.ru ) следующим образом:

Методические указания по организации самостоятельной работы студентов - student2.ru .

Методические указания по организации самостоятельной работы студентов - student2.ru .

При удалении знакового разряда получаем псевдомодули:

Методические указания по организации самостоятельной работы студентов - student2.ru .

Методические указания по организации самостоятельной работы студентов - student2.ru .

Всего возможны четыре варианта сочетания знаков сомножителей:

Случай №1. Методические указания по организации самостоятельной работы студентов - student2.ru

Методические указания по организации самостоятельной работы студентов - student2.ru

В этом случае сразу получено истинное значение положительного произведения в ( Методические указания по организации самостоятельной работы студентов - student2.ru ), которое не требует корректирования.

Случай №2. Методические указания по организации самостоятельной работы студентов - student2.ru

Методические указания по организации самостоятельной работы студентов - student2.ru .

Результат значительно отличается от модуля кода истинного произведения:

Методические указания по организации самостоятельной работы студентов - student2.ru .

Методические указания по организации самостоятельной работы студентов - student2.ru .

Сомножитель Методические указания по организации самостоятельной работы студентов - student2.ru представляет собой ( Методические указания по организации самостоятельной работы студентов - student2.ru ) - разрядный псевдомодуль числа ( Методические указания по организации самостоятельной работы студентов - student2.ru ), представленного в ( Методические указания по организации самостоятельной работы студентов - student2.ru ).

Сомножитель Методические указания по организации самостоятельной работы студентов - student2.ru эквивалентен сдвигу Методические указания по организации самостоятельной работы студентов - student2.ru на ( Методические указания по организации самостоятельной работы студентов - student2.ru ) разряд влево.

Сравнение ( Методические указания по организации самостоятельной работы студентов - student2.ru ) и ( Методические указания по организации самостоятельной работы студентов - student2.ru ) показывает, что результат умножения должен быть скорректирован посредством сложения ( Методические указания по организации самостоятельной работы студентов - student2.ru ) с поправкой ( Методические указания по организации самостоятельной работы студентов - student2.ru ).

Случай №3. Методические указания по организации самостоятельной работы студентов - student2.ru

Методические указания по организации самостоятельной работы студентов - student2.ru

Методические указания по организации самостоятельной работы студентов - student2.ru .

Случай №4. Методические указания по организации самостоятельной работы студентов - student2.ru

Методические указания по организации самостоятельной работы студентов - student2.ru

Тогда истинное произведение ( Методические указания по организации самостоятельной работы студентов - student2.ru ) равно:

Методические указания по организации самостоятельной работы студентов - student2.ru .

На практике используют упрощенную поправку Методические указания по организации самостоятельной работы студентов - student2.ru , поскольку нескорректированный операнд ( Методические указания по организации самостоятельной работы студентов - student2.ru ) проявит себя в виде ( Методические указания по организации самостоятельной работы студентов - student2.ru ) в знаковом разряде. Это не имеет значения, поскольку знак ( Методические указания по организации самостоятельной работы студентов - student2.ru ) был сформирован отдельно на начальном этапе. Подход к формированию алгоритма умножения состоит в следующем:

1. Получим псевдомодули операндов, отбросив старшие (знаковые) цифры: ( Методические указания по организации самостоятельной работы студентов - student2.ru ) - в положительном числе, ( Методические указания по организации самостоятельной работы студентов - student2.ru ) - в отрицательном.

2. Считая разрядную сетку наращиваемой, видим, что операнд в старших разрядах содержит незначащие цифры, тождественно равные знаковой.

3. В таком случае истинные операнды можем считать «удлиненными псевдомодулями», у которых самые левые цифры играют роль знаковых разрядов.

4. Выполняя их умножение по правилам, рассмотренным выше, получаем уже не модуль ( Методические указания по организации самостоятельной работы студентов - student2.ru ), а само псевдопроизведение с некоторыми псевдознаковыми цифрами в двух самых старших разрядах. Указанные цифры относятся к знаковым по расположению, но не имеют смысла таковых.

5. Возникает задача найти истинное значение знаковой цифры числа ( Методические указания по организации самостоятельной работы студентов - student2.ru ).

Рассмотрим арифметическое обоснование алгоритмов второй группы при различных вариантах комбинаций знаков операндов, т.е. умножение чисел в ( Методические указания по организации самостоятельной работы студентов - student2.ru ) с обработкой знаковых разрядов вместе с числовыми в зависимости от сочетания знаков сомножителей. При этом используем предпосылки, приведенные в предыдущем доказательстве. Считаем, что вес знакового разряда равен ( Методические указания по организации самостоятельной работы студентов - student2.ru ). Тогда вес разряда, следующего за знаковым: Методические указания по организации самостоятельной работы студентов - student2.ru .

Случай №1. Методические указания по организации самостоятельной работы студентов - student2.ru

Перемножая машинные представления сомножителей в ( Методические указания по организации самостоятельной работы студентов - student2.ru ), получим:

Методические указания по организации самостоятельной работы студентов - student2.ru

Случай №2. Методические указания по организации самостоятельной работы студентов - student2.ru

Учитывая, что разрядность произведения (и псевдопроизведения) составит ( Методические указания по организации самостоятельной работы студентов - student2.ru ) - бит, вес разряда, следующего за знаковым разрядом произведения:

Методические указания по организации самостоятельной работы студентов - student2.ru .

Тогда:

Методические указания по организации самостоятельной работы студентов - student2.ru

Перемножая Методические указания по организации самостоятельной работы студентов - student2.ru сомножителей, получим:

Методические указания по организации самостоятельной работы студентов - student2.ru .

Истинное значение произведения получается:

Методические указания по организации самостоятельной работы студентов - student2.ru .

Методические указания по организации самостоятельной работы студентов - student2.ru .

Случай №3. Методические указания по организации самостоятельной работы студентов - student2.ru

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

Методические указания по организации самостоятельной работы студентов - student2.ru

Случай №4. Методические указания по организации самостоятельной работы студентов - student2.ru

Методические указания по организации самостоятельной работы студентов - student2.ru

Методические указания по организации самостоятельной работы студентов - student2.ru .

На практике используют упрощенную поправку:

Методические указания по организации самостоятельной работы студентов - student2.ru

При умножении в ( Методические указания по организации самостоятельной работы студентов - student2.ru ) по любому из вариантов данной группы в процессе прибавления ( Методические указания по организации самостоятельной работы студентов - student2.ru ) к ( Методические указания по организации самостоятельной работы студентов - student2.ru ) важно соблюдать соответствие весов разрядов псевдопроизведения и корректирующей поправки (с учетом наличия псевдознака). Старший разряд корректирующей поправки сформирует знаковую цифру. Из рассмотренных ранее вариантов умножения в соответствии с алгоритмами обеих групп, следует, что для коррекции результата умножения ( Методические указания по организации самостоятельной работы студентов - student2.ru ) операндов необходимо в каждом случае по комбинации знаков определять величину коррекции, а затем выполнять 1-2 шага суммирования.

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

Случай №1. Методические указания по организации самостоятельной работы студентов - student2.ru

По примеру первой и второй групп результат является истинным произведением и корректировка не требуется. Т.е. сформированы истинные модуль и знак.

Случай №2. Методические указания по организации самостоятельной работы студентов - student2.ru

При умножении младшими разрядами вперед получится известный для этого случая модуль псевдопроизведения. Если при умножении на знаковую цифру множителя не прибавлять последнее ( Методические указания по организации самостоятельной работы студентов - student2.ru ) к их сумме, а вычесть его, тем самым, ( Методические указания по организации самостоятельной работы студентов - student2.ru ) будет уменьшено на ( Методические указания по организации самостоятельной работы студентов - student2.ru ).

Кроме того, если для представления последнего ( Методические указания по организации самостоятельной работы студентов - student2.ru ) воспользоваться ( Методические указания по организации самостоятельной работы студентов - student2.ru ), то при его прибавлении не только будет откорректирована числовая часть произведения, но и сформируется правильный его знак.

При этом, последний сдвиг ( Методические указания по организации самостоятельной работы студентов - student2.ru ) должен быть арифметическим с учетом отрицательного знака ЧП.

Случай №3 Методические указания по организации самостоятельной работы студентов - student2.ru

Если сдвиг суммы ( Методические указания по организации самостоятельной работы студентов - student2.ru ) вправо на ( Методические указания по организации самостоятельной работы студентов - student2.ru ) разрядов выполнять по правилам сдвига модифицированного ( Методические указания по организации самостоятельной работы студентов - student2.ru ), а затем выполнять суммирование ( Методические указания по организации самостоятельной работы студентов - student2.ru ) по правилам суммирования модифицированных ( Методические указания по организации самостоятельной работы студентов - student2.ru ) (с потерей переноса из знакового разряда), то будет получено правильное произведение исходных чисел в ( Методические указания по организации самостоятельной работы студентов - student2.ru ), т.е. ( Методические указания по организации самостоятельной работы студентов - student2.ru ).

Т.о., коррекция не требуется.

Случай №4 Методические указания по организации самостоятельной работы студентов - student2.ru

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

Таким образом при положительном множителе умножение в ( Методические указания по организации самостоятельной работы студентов - student2.ru ) можно выполнять по алгоритмам умножения в ( Методические указания по организации самостоятельной работы студентов - student2.ru ), если только суммировать ( Методические указания по организации самостоятельной работы студентов - student2.ru ) и сдвиг выполнять по правилам сложения и сдвига модифицированного ( Методические указания по организации самостоятельной работы студентов - student2.ru ) (перенос из ( Методические указания по организации самостоятельной работы студентов - student2.ru ) будет игнорироваться).

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

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

Это выполняется умножением на ( Методические указания по организации самостоятельной работы студентов - student2.ru ) множимого и множителя.

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

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

1. Исходное значение суммы ( Методические указания по организации самостоятельной работы студентов - student2.ru ) принимается равным ( Методические указания по организации самостоятельной работы студентов - student2.ru ), ( Методические указания по организации самостоятельной работы студентов - student2.ru ) присваивается значение равное числу разрядов множителя.

2. Анализируется младшая разрядная цифра множителя. Если она равна ( Методические указания по организации самостоятельной работы студентов - student2.ru ), то к сумме ( Методические указания по организации самостоятельной работы студентов - student2.ru ) прибавляется множимое; если ( Методические указания по организации самостоятельной работы студентов - student2.ru ) - прибавление не производится. Множимое при этом совмещается с суммой ( Методические указания по организации самостоятельной работы студентов - student2.ru ) по старшим разрядам и представлено в исходном коде.

3. Производится арифметический сдвиг суммы ( Методические указания по организации самостоятельной работы студентов - student2.ru ) вправо на ( Методические указания по организации самостоятельной работы студентов - student2.ru ) разряд с учетом флагов переноса ( Методические указания по организации самостоятельной работы студентов - student2.ru ) и переполнения ( Методические указания по организации самостоятельной работы студентов - student2.ru ). Содержимое ( Методические указания по организации самостоятельной работы студентов - student2.ru ) уменьшается на ( Методические указания по организации самостоятельной работы студентов - student2.ru ).

4. пп.2-3 последовательно выполняются для всех цифровых разрядов множителя.

5. Если множитель - положительное число, то полученный результат является истинным произведением ( Методические указания по организации самостоятельной работы студентов - student2.ru ). Если множитель - отрицательное число, то к полученному результату ( Методические указания по организации самостоятельной работы студентов - student2.ru ) прибавляется множимое с обратным знаком (дополнение), совмещенное по старшим разрядам. Полученная сумма представляет собой истинное произведение ( Методические указания по организации самостоятельной работы студентов - student2.ru ). Методические указания по организации самостоятельной работы студентов - student2.ru . где ( Методические указания по организации самостоятельной работы студентов - student2.ru ) - время, затрачиваемое на выполнение операции сдвига на один разряд; ( Методические указания по организации самостоятельной работы студентов - student2.ru ) - время, затрачиваемое на выполнение операции сложения.

Так как данные в памяти компьютера хранятся в ( Методические указания по организации самостоятельной работы студентов - student2.ru ), операцию деления целесообразно выполнять в ( Методические указания по организации самостоятельной работы студентов - student2.ru ). За основу можно принять базовый алгоритм деления ( без восстановления остатка), т.к. он предполагает использование отрицательного делителя, дополнительного кода для вычитания и учет знаков остатка и делителя на каждом шаге деления. Делимое участвует в операции только на первом шаге, а далее используются остатки, которые могут быть как положительными, так и отрицательными. Поэтому не имеет смысла рассматривать алгоритмы деления в ( Методические указания по организации самостоятельной работы студентов - student2.ru ), где знаки операндов обрабатываются отдельно от их числовых частей. Таким образом, при делении чисел в ( Методические указания по организации самостоятельной работы студентов - student2.ru ) трудности, связанные с коррекцией результата (как при умножении в дополнительном коде), практически отсутствуют.

Пусть:

Методические указания по организации самостоятельной работы студентов - student2.ru .

Методические указания по организации самостоятельной работы студентов - student2.ru .

Методические указания по организации самостоятельной работы студентов - student2.ru .

Методические указания по организации самостоятельной работы студентов - student2.ru .

Для проверки на корректность операции деления используется условие:

Методические указания по организации самостоятельной работы студентов - student2.ru . Таким образом, при пробном вычитании делитель должен быть сдвинут на ( Методические указания по организации самостоятельной работы студентов - student2.ru ) разряд влево.

Однако чтобы обеспечить регулярность процесса деления, делитель сдвигается влево на ( Методические указания по организации самостоятельной работы студентов - student2.ru ) разрядов, а перед пробным вычитанием делимое сдвигается на один разряд влево.

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

Алгоритм деления знаковых чисел отличается от алгоритма деления беззнаковых чисел способом формирования разрядных цифр частного.

Очередная цифра определяется на основе анализа знаков частичного остатка и делителя. Если знак полученного остатка совпадает со знаком делителя, то цифра частного равна ( Методические указания по организации самостоятельной работы студентов - student2.ru ), если нет - ( Методические указания по организации самостоятельной работы студентов - student2.ru ).

При этом частное формируется в прямом или обратном коде (в зависимости от соотношения знаков делимого и делителя).

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

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

Алгоритм деления целых двоичных знаковых чисел заключается в следующем:

1. Частному присваивается значение ( Методические указания по организации самостоятельной работы студентов - student2.ru ), ( Методические указания по организации самостоятельной работы студентов - student2.ru ) - ( Методические указания по организации самостоятельной работы студентов - student2.ru ). Исходное значение частичного остатка равно ( Методические указания по организации самостоятельной работы студентов - student2.ru ) старшим разрядам делимого.

2. Частичный остаток удваивается сдвигом влево на ( Методические указания по организации самостоятельной работы студентов - student2.ru ) разряд, с занесением в младший разряд очередной цифры делимого.

3. Если частичный остаток и делитель разного знака, то они складываются, если же одного знака, то из частичного остатка вычитается делитель.

4. Частное сдвигается влево на ( Методические указания по организации самостоятельной работы студентов - student2.ru ) разряд. В освобождающийся младший разряд заносится очередная цифра частного: ( Методические указания по организации самостоятельной работы студентов - student2.ru ) - если знак делителя и остатка совпадают, ( Методические указания по организации самостоятельной работы студентов - student2.ru ) - в противном случае ( Методические указания по организации самостоятельной работы студентов - student2.ru ) уменьшается на ( Методические указания по организации самостоятельной работы студентов - student2.ru ).

5. Пункты 2-4 повторяются до тех пор, пока ( Методические указания по организации самостоятельной работы студентов - student2.ru ) не станет равным ( Методические указания по организации самостоятельной работы студентов - student2.ru ).

6. Частное и остаток сформированы в обратном коде. Если знак окончательного остатка не совпадает со знаком делимого, то выполняется его восстановление. Для получения ( Методические указания по организации самостоятельной работы студентов - student2.ru ) результата выполняется его коррекция в зависимости от соотношения знаков делимого и делителя.

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

Случай №1. Методические указания по организации самостоятельной работы студентов - student2.ru Деление в этом случае ничем не отличается от деления положительных операндов в прямом коде. Коррекция не требуется.

Случай №2. Методические указания по организации самостоятельной работы студентов - student2.ru Этот случай легко сводится к обычному делению в прямом коде, если считать, что в наличии имеется Методические указания по организации самостоятельной работы студентов - student2.ru .

Однако для формирования правильного знака частного и обратного кода отрицательного результата необходимо псевдознаковую цифру и цифры частного получать равными цифрам знаковых разрядов соответствующих остатков.

Переполнение разрядной сетки здесь фиксируется по ( Методические указания по организации самостоятельной работы студентов - student2.ru ). В конце деления для образования дополнительного кода и округления частного следует прибавить единицу к младшему разряду: ( Методические указания по организации самостоятельной работы студентов - student2.ru ).

Случай №3. Методические указания по организации самостоятельной работы студентов - student2.ru Из отрицательного делимого должен вычитаться положительный делитель, в отличие от деления без восстановления остатка в прямом коде, когда на первом шаге ( Методические указания по организации самостоятельной работы студентов - student2.ru ). Поэтому псевдознаковая цифра частного ( Методические указания по организации самостоятельной работы студентов - student2.ru ), полученная по знаку нулевого остатка в соответствии с алгоритмом деления без восстановления остатка, здесь указывает на переполнение разрядной сетки. Если же переполнения разрядной сетки нет, эта цифра является правильной знаковой цифрой частного (то есть, Методические указания по организации самостоятельной работы студентов - student2.ru ). Знаки всех других остатков в этом случае определяют инверсные значения цифр частного. В результате будет записан обратный код отрицательного частного. Для округления и получения дополнительного кода результата необходимо добавить единицу в младший разряд, если полученный остаток не равен нулю: ( Методические указания по организации самостоятельной работы студентов - student2.ru ).

Случай №4. Методические указания по организации самостоятельной работы студентов - student2.ru На первом шаге алгоритма для формирования правильного знака частного ( Методические указания по организации самостоятельной работы студентов - student2.ru ), необходимо из отрицательного делимого вычитать отрицательный делитель ( Методические указания по организации самостоятельной работы студентов - student2.ru соответствует переполнению разрядной сетки).

Далее же этот случай сводится к третьему. Здесь все цифры частного, включая псевдознаковую, равны знакам остатков. В случае, когда полученный остаток равен нулю, к частному следует прибавить единицу ( Методические указания по организации самостоятельной работы студентов - student2.ru ). При использовании методов с восстановлением остатка и без восстановления остатка сдвиг влево может вызвать передачу значащей цифры из старшего разряда остатка в знаковый, и остаток будет искажен.

Поэтому надо оперировать двумя знаковыми разрядами.

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

Контрольные вопросы

1. Объясните прицип работы логического сдвига.

2. Объясните принцип работы арифметического сдвига.

3. Объясните принцип работы модифицированного сдвига.

4. Объясните принцип работы циклического сдвига.

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

6. Сформулируйте алгоритм деления целых двоичных знаковых чисел методом без восстановлением остатка

Наши рекомендации