- •Основы компьютерной арифметики и логики
- •Предисловие
- •Глава 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
4.7. Разработка алгоритма вычисления квадратного корня
Вычисление квадратного корня производится путем деления исходного числа на переменный делитель [14]. Первое значение переменного делителя равно 0,01, следующие значения формируются путем приписывания пары цифр 01 к уже найденному числу.
Для нахождения результата нужно выполнить (n-2) цикла, каждый из которых может содержать три такта:
1) из значения на сумматоре вычитается содержимое переменного делителя (РгД) и определяется очередная цифра результата, которая равна инверсии знака сумматора;
2) если после выполнения вычитания сумматор меньше нуля, то нужно выполнить восстановление сумматора путем сложения его с содержимым переменного делителя;
3) производится сдвиг содержимого сумматора на один разряд влево и формируется новый переменный делитель.
Нужно помнить, что из отрицательных чисел корень не вычисляется.
Схема алгоритма извлечения квадратного корня в соответствии с описанным алгоритмом изображена на рис. 4.7.
Р ис. 4.6. Схема алгоритма ускоренного деления
с анализом двух разрядов делителя
Рис. 4.6. Схема алгоритма ускоренного деления с анализом двух разрядов делителя (окончание)
Рис. 4.7. Схема алгоритма вычисления квадратного корня
Буквами yi обозначены разряды регистра результата (РгР). Начальное значение счетчика во всех алгоритмах принимается равным (n-2), где n – число разрядов исходных чисел, так как используются модифицированные коды.
Рассмотрим пример для операции вычисления квадратного корня для числа с фиксированной запятой. Извлечем квадратный корень из числа А = 0,101111 по разработанному алгоритму.
См = 0,101111 РгР = 0 (регистр результата)
+ 1,110000 РгД = 0,01 (переменный делитель)
I 1) См= См-РгД = 0,011111 РгР = 0,1 (так как См>0)
3) См = См← = 0,111110 РгД = 0,101
+ 1,011000
II 1) См= См-РгД = 0,010110 РгР = 0,11 (См>0)
3) См = См← = 0,101100 РгД = 0,1101
+ 1,001100
III 1) См= См-РгД = 1,111000 РгР = 0,110 (так как См<0)
+ 0,110100
2) См=См+РгД = 0,101100
3) См = См← = 1,011000 РгД = 0,11001
+ 1,001110
IV 1) См= См-РгД = 0,100110 РгР = 0,1101 (так как См>0)
3) См = См← = 1,001100 РгД = 0,110101
+ 1,001011
V 1) См= См-РгД = 0,010111 РгР = 0,11011 (так как См>0)
3) См = См← = 0,101110 РгД = 0,1101101
+ 1,0010011
VI 1) См= См-РгД = 0,010111 РгР = 0,110110 (так как См<0)
В циклах I, II, IV и V пропущен второй такт, потому что сумматор положителен и восстановление остатка не требуется.
Ответ: В = = 0,110110, что соответствует результату, полученному при извлечении корня из числа А программой «Операции».
В настоящей главе проанализирована часть алгоритмов реализации программных моделей операций, изучаемых в курсе «Дискретная математика». Приведены схемы алгоритмов перевода чисел из одной позиционной системы счисления в другую, а также для выполнения арифметических операций сложения (вычитания), умножения, деления и вычисления квадратного корня для двоичных чисел, в том числе и ускоренные методы умножения и деления. Таким же образом можно проектировать любые алгоритмы выполнения операций, описанных в теоретических главах 2 и 3.
5. МАТЕМАТИЧЕСКАЯ ЛОГИКА
И СИНТЕЗ КОМБИНАЦИОННЫХ СХЕМ
5. 1. Соответствия и предикаты
5.1.1. Соответствия
Одним из фундаментальных понятий математики является понятие соответствия. Соответствие является абстракцией более высокого порядка, чем функции и отношения.