- •Основы компьютерной арифметики и логики
- •Предисловие
- •Глава 4, подготовленная доцентом о.П. Шафеевой, посвящена вопросам разработки алгоритмических моделей выполнения арифметических операций и моделирования на пэвм спроектированных алгоритмов.
- •Основы двоичной компьютерной арифметики
- •1.1. Позиционные системы счисления
- •Десятичная позиционная система счисления
- •Двоичная позиционная система счисления
- •1.1.3. Восьмеричная позиционная система счисления
- •1.1.4. Шестнадцатеричная позиционная система счисления
- •Сложение Вычитание
- •Перевод чисел из одной позиционной системы счисления в другую
- •1.2.1. Перевод целых чисел
- •1.2.2. Перевод правильных дробей
- •1.2.3. Перевод неправильных дробей из одной системы счисления в другую
- •1.2.4. Частный случай перевода чисел из одной системы счисления в другую
- •1.2.5. Перевод чисел из одной системы счисления в другую с использованием промежуточной двоично-десятичной системы
- •1.3. Представление чисел с фиксированной запятой (точкой)
- •1.4. Представление чисел с плавающей запятой (точкой)
- •1.5. Коды двоичных чисел
- •1.5.1. Прямой код
- •1.5.2. Обратный код
- •1.5.3. Модифицированный обратный код
- •1.5.4. Дополнительный код
- •2.1.1. Алгебраическое сложение чисел в дополнительном коде
- •2.1.2. Алгебраическое сложение чисел в обратном коде
- •2.1.3. Переполнение разрядной сетки при сложении чисел
- •2.2. Сложение (вычитание) двоичных чисел с плавающей запятой
- •2.2.1. Метод ускоренного сложения двоичных чисел с запоминанием переносов
- •2.3. Умножение двоичных чисел с фиксированной запятой
- •2.4. Машинные технологии выполнения операции умножения двоичных чисел с фиксированной запятой
- •2.5. Умножение двоичных чисел с плавающей запятой
- •2.6. Методы ускоренного выполнения операции умножения двоичных чисел
- •2.6.1. Метод пропуска такта суммирования
- •2.6.2. Метод анализа сомножителей
- •2.6.3. Метод расшифровки и одновременного умножения на два разряда множителя
- •2.6.4. Метод ускоренного умножения Мак-Сорли
- •2.6.5. Метод ускоренного умножения Лемана
- •2.6.6. Метод умножения с расшифровкой пар разрядов множителя и запоминанием переносов
- •2.7. Деление двоичных чисел с фиксированной запятой
- •2.8. Деление двоичных чисел с плавающей запятой
- •3. Основы десятичной компьютерной арифметики
- •3.1. Машинное кодирование десятичных чисел
- •3.2. Выполнение арифметических операций с десятичными числами
- •3.2.1. Сложение десятичных чисел в эвм
- •3.2.2. Умножение десятичных чисел в эвм
- •3.2.3. Ускорение умножения в -кодах
- •Деление десятичных чисел в эвм
- •4.2. Моделирование алгоритма сложения двоичных чисел
- •Различные случаи ненормализованных мантисс
- •4.3. Проектирование алгоритма умножения чисел
- •4.5. Проектирование алгоритма деления чисел
- •4.7. Разработка алгоритма вычисления квадратного корня
- •Определение 1. Пусть и произвольные множества. Соответствием называется тройка множеств
- •Свойства отношений
- •Эквивалентность
- •Толерантность
- •Отношения порядка
- •Самодвойственные функции
- •Монотонные функции
- •Линейные функции
- •Функции, сохраняющие константу
- •5.2.7. Минимизация булевых функций
- •Метод Блейка
- •Метод Квайна-Мак-Класки
- •Минимизация с использованием карт Карно
- •Дана функция четырех переменных (рис. 5.13):
- •Минимизация не полностью определенных булевых функций
- •Минимизация систем булевых функций
- •5.3. Методика синтеза комбинационных схем на логических элементах
- •5.3.1. Логические элементы
- •5.3.2. Общий алгоритм построения комбинационных схем
- •5.3.3. Синтез кс в классическом базисе
- •5.3.4. Синтез кс в базисах «и-не», «или-не»
- •5.3.5. Реализация кс в базисе Жегалкина
- •5.3.6. Синтез составных кс
- •Заключение
- •Библиографический список к главам 1, 2, 3, 4
- •Библиографический список к главе 5
-
Деление десятичных чисел в эвм
Деление представляет многошаговый процесс. Для определения цифр частного необходимо произвести последовательное вычитание делителя из делимого, при этом если очередной остаток положительный или равен нулю, то в соответствующий разряд частного добавляется единица. Деление можно производить с восстановлением и без восстановления остатка.
При делении без восстановления остатка в том случае, когда образуется отрицательный остаток, делитель сдвигают на один десятичный разряд вправо по отношению к остатку и продолжают деление, прибавляя делитель к отрицательному остатку с приписанным справа следующим разрядом делимого. После первого такого прибавления в очередном разряде частного устанавливается цифра 9. На каждом очередном этапе сложения содержимое этого разряда частного уменьшается на единицу. При новом появлении положительного остатка в данном разряде зафиксируется искомая цифра разряда частного. Далее осуществляется переход к определению следующей цифры частного.
Если делимое не делится нацело, то для целей округления можно определить дополнительную цифру частного.
Пример.
Вычислить десятичное частное при по методу с восстановлением остатка.
Для простоты и наглядности операции будем производить вначале деление в десятичной системе счисления.
Сумматор Частное
Делимое 0 5 6
доп. = 920 + 9 2 0
Восстановление 9 7 0 0 (остаток меньше 0)
остатка пр. = 080 + 0 8 0
1
Сдвиг делителя 9 9 2
доп. = 992 0 4 8 01 (остаток больше 0)
+ 9 9 2
0 4 0 02 (остаток больше 0)
+ 9 9 2
0 3 2 03 (остаток больше 0)
+ 9 9 2
0 2 4 04 (остаток больше 0)
+ 9 9 2
0 1 6 05 (остаток больше 0)
+ 9 9 2
0 0 8 06 (остаток больше 0)
+ 9 9 2
0 0 0 07 (остаток равен 0)
Таким образом, Z=X : Y= 7.
Пример.
Теперь рассмотренный пример деления с восстановлением остатка представим в -кодах.
Делимое X=65, делитель Y=8, Z = X : Y.
Ниже приводится схема реализации деления в D-кодах.
Сумматор Частное
Делимое [056] 0000 0101 0110
[080] 1111 1000 0000
1111 1101 0110
коррекция 1010 1010 0000
(976) 1001 0111 0110 < 0 0
Восстановление [080] 0110 1110 0110
0000 0101 1100
коррекция 0000 0000 1010
1
[008] 1111 1111 1000
0000 0100 1110
коррекция 0000 0000 1010
(048) 0000 0100 1000 > 0 01
[008] 1111 1111 1000
0000 0100 0000
коррекция 0000 0000 0000
(040) 0000 0100 0000 > 0 02
[008] 1111 1111 1000
0000 0011 1000
коррекция 0000 0000 1010
(032) 0000 0011 0010 > 0 03
[008] 1111 1111 1000
0000 0010 1010
коррекция 0000 0000 1010
(024) 0000 0010 0100 > 0 04
[008] 1111 1111 1000
0000 0001 1100
коррекция 0000 0000 1010
(016) 0000 0001 0110 > 0 05
[008] 1111 1111 1000
0000 0000 1110
коррекция 0000 0000 1010
(008) 0000 0000 1000 > 0 06
[008] 1111 1111 1000
0000 0000 0000 = 0 07
Таким образом, Z = X : Y = 7.
В заключение рассмотрим пример деления десятичных чисел без восстановления остатка.
Пример.
Вычислить десятичное частное Z = X :Y при X=56, Y=8 по методу без восстановления остатка в десятичной системе счисления.
Сумматор Частное
+
доп. = 920 9 2 0
1
+
9 7 6 0 (остаток меньше 0)
Сдвиг делителя 0 0 8
+
0 0 8
+
0 0 8
0 0 0 07 (остаток равен 0)
Таким образом, Z=X : Y= 7.
Вышеприведенный пример деления без восстановления остатка рассмотрим теперь в -кодах. Делимое X=56, делитель Y=8, Z = X : Y.
Сумматор Частное
Делимое [056] 0000 0101 0110
[080] 1111 1000 0000
1111 1101 0110
коррекция 1010 1010 0000
1
[008] 0110 0110 1110
1111 1110 0100
коррекция 1010 0000 1010
(984) 1001 1000 0100 < 0 09
[008] 0110 0110 1110
1111 1111 0010
коррекция 1010 1010 0000
(992) 1001 1001 0010 < 0 08
[008] 0110 0110 1110
0000 0000 0000 = 0 07
Следовательно, Z=X : Y = 7.
4. АЛГОРИТМИЧЕСКИЕ МОДЕЛИ ВЫПОЛНЕНИЯ
АРИФМЕТИЧЕСКИХ ОПЕРАЦИЙ
4.1. Проектирование универсального алгоритма перевода чисел
в разные системы счисления
Перевод чисел из одной позиционной системы счисления в другую выполняется по разным алгоритмам для целых и дробных частей числа [12].
Алгоритм 1. Для перевода целого числа из системы счисления с основанием p в систему счисления с основанием q нужно делить число и его частные на q. Последовательное деление производится до тех пор, пока не получится частное, равное нулю. Деление выполняется в исходной системе счисления. При этом в виде остатков от деления получаются q-ичные цифры (начиная с младшей) числа.
Алгоритм 2. Для перевода правильной дроби (дробной части числа) из p-ичной в q-ичную систему счисления нужно умножать эту дробь и дробные части полученных произведений на q. Целые части этих произведений образуют q-ичные цифры (начиная со старшей) представления правильной дроби в q-ичной системе счисления. Умножение выполняется в исходной системе счисления.
Алгоритм 3. Если результирующей системой счисления (p) - десятичная, то наиболее простой способ перевода - это перевод по весовым коэффициентам:
Xq = xn-1*qn-1 + xn-2*qn-2 + … + x1*q1 + x0*q0 + x-1*q-1 + x-2*qm-2 + … + xk*qk
или при алгоритмической реализации нужно вычислить сумму следующего вида:
n-1
Xq = xi*qi ,
i=-t
где n – количество разрядов в целой части числа, t – количество разрядов в дробной части числа.
Алгоритм 4. Частным случаем перевода чисел из одной системы счисления в другую служит ситуация, когда основание одной системы счисления является целой степенью другой (p=qk). В этом случае для перевода произвольного числа из q-ичной системы счисления в p-ичную нужно цифры числа влево и вправо от запятой разбить на группы по k разрядов в каждой. При этом если необходимо, крайнюю левую и крайнюю правую группы дополняют нулями до k цифр в группе. Затем надо заменить каждую выделенную k-значную группу цифрой в p-ичной системе счисления.
Рис. 4.1. Схема универсального алгоритма перевода чисел
из одной системы счисления в другую
Схема универсального алгоритма перевода чисел из любой системы счисления в любую представлена на рис. 4.1, где частные алгоритмы оформлены подпрограммами. Число X в исходной системе счисления с основанием p в ней переводится в q-ичную систему счисления. Если p=10, то число разделяют на целую и дробную части, для перевода которых применяют алгоритмы 1 и 2 соответственно. Если результирующая система счисления является десятичной, то используют третий алгоритм. Если ни исходная, ни результирующая системы не являются десятичными, но p=qk, то пользуются четвертым алгоритмом. В случае, когда не выполняется ни одно из перечисленных условий, приходится сначала переводить число в десятичную систему счисления, после чего – в искомую. Это обусловлено сложностью выполнения операций в непривычных для человека системах счисления.