Лекции по дисциплине «Теория вычислительных процессов» (стр. 5 )

Если сомножители представлены ДК, можно применить также способ умножения, основанный на сопоставлении двух смежных цифр множителя:

В ДК произведение имеет вид:

[С]д=[А]д[В]д=-[А]дво 2о+[А]дв12-1+...[А]двn2-n=[А]д(в1-во)2о+[А]д(в2-в1)2-1+...+[А]д(вn-1-вn)2-n

При этом вn+1=0. Тогда с учетом того, что перед началом умножения в сумматоре находится код нуля, для четвертой схемы умножение будет иметь: на нулевом шаге

Со=0+(в1-в0)[А]д20

С1=Со+(в2-в1)[А]д2-1

Сi=Ci-1+(вi+1-вi) [A]д2-i

Аналогичные результаты можно получить для остальных схем умножения.

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

1) Если данная цифра множителя равна 1, а цифра соседнего младшего разряда множителя есть 0, то множимое со своим весом следует вычитать.

2) Если данная цифра множителя 0, а цифра соседнего младшего разряда есть 1, то множимое следует прибавлять со своим весом.

3) Если данная цифра множителя такая, как и цифра соседнего младшего разряда, то данное частичное произведение равно.

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

Деление чисел с восстановлением остатков

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

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

Частное определяется путем деления модулей исходных чисел. При этом во избежание переполнения разрядной сетки должно соблюдаться условие|А|<|В|.

Пусть требуется разделить А на В с точностью до i-го разряда.

Тогда:

Yi=A/B=0 y1 y2...yi=y12-1+y22-2+...yi2-i.

При любом значении i должно выполняться неравенство 0£А-ВYi<B2-i, т. е. остаток от деления (А-ВYi) должен быть меньше делителя, умноженного на 2-i.

Преобразуем это выражение к виду:

0£(А-ВYi)2i<B 0£Ri<B

Цифры частного определяются последовательно, начиная со старшего разряда. Допустим, что в результате выполнения i циклов получены старшие i разрядов частного, т. е. приближенное значение частного Yi. В следующем (i+1)-ом цикле будет получено значение (i+1)-го разряда частного. Исходными данными для этого цикла являются Yi и Ri.

Цифра Yi+1 может иметь одно из двух значений: 1 или 0. Если yi+1=0, то

Yi+1=Yi+yi+1 2-(i+1)=Yi

Ri+1=(A-BYi+1)2i+1=2Ri

т. е. в частное записывается 0 при условии 0£Ri+1=2Ri<B

Если yi+1=1, то

Yi+1=Yi+2-(i+1)

Ri+1=(F-BYi+1)2i+1=(A-BYi-D 2-(i+1)) 2i+1=2Ri-B

т. е. цифра частного равна 1, если выполняется условие: 0£Ri+1=2Ri-B<B или B£2Ri£2B.

Так как всегда выполняется одно из приведенных условий, то для определения текущей цифры частного достаточно проверить одно из них. Обычно проверяют первое. Левая часть этого неравенства выполняется заведомо, т. к. очередной остаток перед началом следующего шага всегда является положительным. Для проверки правой части неравенства сравним разность (2Ri-В) с нулем. Если эта разность окажется отрицательной, то в (i+1) разряд частного запишем 0 и для подготовки исходных данных для (i+2) цикла определим Ri+1 следующим образом:

Ri+1=(2Ri-B)+B=2Ri.

Если разность 2Ri-В окажется положительной, то запишем в(i+1) разряд частного 1, а в качестве исходного значения для (v+2)го цикла используем вычисленную разность: Ri+1=2Ri-B.

Исходными данным для первого цикла являются Yo=0 Ro=(A-BYo)2o=A<B.

После завершения n-го цикла мы получим n-значное частное Yn, вычисленное с недостатком Rn=(A-BYn)2n.

Правило деления с восстановлением остатка формулируется следующим образом. Делитель вычитается из делимого и определяется знак нулевого остатка. Если остаток положительный, то в псевдознаковом разряде частного проставляется 1, при появлении которой формируется признак переполнения разрядной сетки и операция прекращается. Если остаток отрицательный, то в псевдознаковом разряде частного записывается 0, а затем производится восстановление делимого путем добавления к остатку делителя. Далее выполняется сдвиг восстановленного делимого на один разряд влево и повторное вычитание делителя. Знак получаемого таким образом остатка определяет первую значащую цифру частного: если остаток положителен, но в первом разряде частного записывается 2, если отрицательный - 0.

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

Цифры частного получаются как инверсное значение знаковых разрядов текущего остатка, которые принимают значение 00V11. Однако при сдвиге остатка влево в знаковых разрядах может возникнуть 01.

Деление без восстановления остатка

Рассмотренный процесс деления с восстановлением остатка является аритмичным процессом с переменным числом шагов.

Операцию можно упростить и получить каждую цифру за 2 шага.

Рассмотрим случай, когда Ri<0. В предыдущем способе в этом случае выполнялись следующие операции:

1) восстановление остатка

R1i=Ri+|В|=2Ri-1-B|+|B|=2Ri-1

2) Cдвиг восстановленного остатка влево:

Ri=2Ri=2Ri-1 2=4Ri-1

3) вычитание модуля делителя из восстановленного и сдвинутого влево остатка для определения следующего остатка

Rvi=4Ri-1-|B|.

Если не восстанавливать остаток, а сразу сдвинуть отрицательный Ri на один разряд влево, то получим

Ri+1=2Ri=22Ri-1-|B|)=4Ri-1-2|B|.

Результат в данном случае отличается от действительного на величину +|В|. Поэтому в качестве второго шага необходимо произвести коррекцию результата на эту величину:

Ri+1=4Ri-1-2|B|+|B|=4Ri-1-|B|.

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

Таким образом, чтобы определить следующую цифру частного, необходимо сдвинуть текущий остаток влево на 1 разряд, а затем алгебраически прибавить к нему модуль делителя, которому приписывается знак, противоположный знаку текущего остатка. Знак полученного таким образом остатка и определяет следующую цифру частного: если он положителен, то в частном записывается 1, если отрицателен - 0.

Операция сдвигов и алгебраических сложений повторяется до тех пор, пока в частном не получится требуемое количество цифр.

ВЫПОЛНЕНИЕ АРИФМЕТИЧЕСКИХ ОПЕРАЦИЙ

В НЕПОЗИЦИОННЫХ СИСТЕМАХ СЧИСЛЕНИЯ

Основные сведения о системе остаточных классов

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

А(р)= a1b1+a2b2+...+akbk,

где А(р) - представление числа А в системе счисления с основаниями рi;

Вi - целые положительные числа;

ai - наименьший положительный остаток от деления числа А на модуль р:

ai=res(A)modp 0£ai£pi-1.

Остаток выбирается таким образом, чтобы

ai=А-Sipi, i=1,2...k,

образование остатков ai производится независимо друг от друга. В теории чисел доказывается, что если модули р1, р2...рk являются взаимно простыми числами, то для каждого целого положительного числа А его изображение в виде остатков ai единственное.

Диапазон представления чисел в системе остаточных классов - произведение всех оснований системы Р=р1 р2...рk=Прi. Следовательно, для того чтобы обеспечить однозначность изображения чисел, необходимо потребовать выполнения условия:

А<Р или О£А£р-1

Система остаточных классов допускает расширение или сокращение набора оснований, не искажая при этом исходное число.

Перевод чисел из позиционной системы в СОК и обратный перевод

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

Для машинного перевода используется следующий метод перевода чисел в СРК. Имеется позиционная запись числа:

Аq=akqk+ak-1qk-1...a1q1+a0q0

Пусть для набора модулей р1, р2...рn любая степень основания представляется в виде остатков:

qi=(b1i, b2i, ... bni)

После подстановки получаем:

А=ak(b1k, b2k... bnk)+ak-1(b1, k-1, b2, k-1 ... bn, k-1)+ ... +a0(b1,0, b2,0 ... bn,0)=(akb1,k+ak-1b1, k-1+...+a0b1,0)+ ... +ak(bnik+ak-1bn, k-1+ .. +a0bn,0)

отсюда:

a1º(akb1,k+ak-1b1, k-1 ... +a0b1,0)modp1

anº(akbn, k+ak-1bn, k-1 ... +a0bn,0)modpn

Пример: Перевести число А=97 в СОК с основаниями р1=3, р2=5, p3=7.

100= (1, 1, 1) 101=(1, 0, 3)

a1º9 1+7 1º16º1(mоd 3)

a2º9 0+7 1º7º2 (mod 5)

a3º 9 3+7 1º34º6(mod 7)

А=(1, 2, 6)

Задача перевода из СОК в позиционную систему формулируются следующим образом: для заданного набора модулей р1, р2, рn перевести изображение А(a1... an) в систему с основанием q так, чтобы

А=М1В1+М2В2+...+МnВn,

где Bi=(B1,i, B2,i... Bn, i) - базисы.

После подстановки имеем:

А=(М1В1,1+М2В1,2+...+МnВi, n)+...+(М1Вn,1+М2Вn,2+...+МnВn, n).

Величины, записанные в скобках, приравниваем цифрам ai изображения числа в СОК:

М1В1,1+М2В1,2+...+МnВi, n=a1

М1Вn,1+М2Вn,2+...+МnВn, n=an.

Cистема уравнений имеет целочисленное решение при условии, что определитель системы равен ±1:

При этом получается большое количество возможных решений. Однозначное решение будет только в случае. Если в определителе все члены равны 0, за исключением диагональных, которые должны быть равны 1. Отсюда следует: