- •Компьютерная арифметика и алгоритмическое моделирование арифметических операций
- •Введение
- •Глава 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. Дополнительный код
- •1.5.5. Модифицированный дополнительный код
- •2. Выполнение арифметических операций с двоичными числами
- •2.1. Сложение (вычитание) двоичных чисел с фиксированной запятой
- •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. Алгоритмические модели выполнения арифметических операций
- •4.1. Проектирование универсального алгоритма перевода чисел в разные системы счисления
- •4.2. Моделирование алгоритма сложения двоичных чисел
- •Различные случаи ненормализованных мантисс
- •4.3. Проектирование алгоритма умножения чисел
- •4.5. Проектирование алгоритма деления чисел
- •4.7. Разработка алгоритма вычисления квадратного корня
- •Компьютерная арифметика и алгоритмическое моделирование арифметических операций
Основы двоичной компьютерной арифметики
1.1. Позиционные системы счисления
В современных ЭВМ общего назначения для представления обрабатываемой числовой информации, как правило, используются позиционные системы счисления.
Системой счисления называется совокупность приемов наименования и записи чисел.
Позиционной системой счисления называют такую систему, в которой значение (вес) каждой цифры, образующей число, зависит от ее позиции (местоположения) в числе. То есть одна и та же цифра в зависимости от ее местоположения в числе умножается на различный весовой коэффициент для определения ее истинного значения.
Основанием системы счисления называется количество различных цифр, применяемых в соответствующей позиционной системе счисления, необходимых для изображения любого числа в этой системе.
Так, например, основанием двоичной позиционной системы является число 2, восьмеричной – число 8, десятичной – 10, шестнадцатеричной – 16 и т.д.
Пусть является основанием -ичной позиционной системы счисления. В такой системе используется различных цифр, представляющих последовательные целые числа, начиная с нуля и кончая числом, равным . Любые числа записываются в виде последовательности цифр, в которых целая часть отделена от дробной части запятой (точкой) и каждая последующая (справа налево) цифра имеет весовой коэффициент в раз больше, чем предыдущая.
Если буквами обозначить цифры -ичной позиционной системы счисления, то последовательность цифр
обозначает число
.
Обычно во всех позиционных системах счисления в качестве двух младших цифр используют знаки 0 и 1. При этом основание системы счисления записывается в виде последовательности цифр 10.
Для того, чтобы выполнять произвольные вычислительные операции в любой позиционной системе счисления, необходимо кроме введенных выше понятий уметь пользоваться элементарными арифметическими операциями (сложение, вычитание, умножение и деление) в данной системе счисления.
Основываясь на приведенных определениях, рассмотрим наиболее часто используемые в компьютерной технике и в вычислительной практике позиционные системы счисления: двоичную, восьмеричную, десятичную и шестнадцатеричную. При этом начнем рассмотрение с хорошо всем известной десятичной системы счисления.
Десятичная позиционная система счисления
Основание системы счисления (число десять). Для изображения десяти различных цифр используются знаки (арабские цифры) 0, 1, 2, 3, 4, 5, 6, 7, 8, 9. Последовательность десятичных цифр, например 257 75, представляет собой число
.
Сложение, вычитание, умножение и деление в десятичной системе счисления выполняются в соответствии с хорошо всем известными правилами, которые представляются в виде таблиц.
Двоичная позиционная система счисления
В двоичной системе счисления для записи произвольных чисел используются всего две цифры: 0,1. Основание этой системы счисления (число два) записывается двумя цифрами в виде . Остальные любые двоичные числа представляются в виде последовательности нулей и единиц.
Например, десятичное число 237,75 в двоичной системе счисления будет выглядеть так:
(здесь 10 означает число два).
Показатели степени у основания системы счисления также записаны в двоичной системе счисления.
Для удобства чтения записи представим изображения десятичных чисел от нуля до девяти в двоичной системе:
0; |
1; |
2; |
3; |
4; |
5; |
6; |
7; |
8; |
9. |
0; |
1; |
10; |
11; |
100; |
101; |
110; |
111; |
1000; |
1001. |
Легко проверить теперь правильность двоичной записи числа двести тридцать семь целых семьдесят пять сотых в двоичной системе, переписав правую часть последнего равенства в десятичной системе счисления:
Из приведенных примеров следует, что весовые коэффициенты цифр двоичного числа являются числами, кратными целой степени (положительной или отрицательной) цифры два. При этом для целой части двоичного числа, начиная от младшего разряда к старшему, они равны 1, 2, 4, 8, 16, 32, 64, 128 и т.д., а для дробной части двоичного числа от старшего разряда к младшему весовые коэффициенты цифр имеют значения и т.д.
Таблицы сложения, вычитания и умножения двоичных цифр, лежащие в основе двоичной арифметики, содержат всего четыре строки (табл. 1.1; 1.2; 1.3).
Таблица 1.1 |
|
Таблица 1.2 |
|
Таблица 1.3 |
0 + 0 = 0 |
|
0 - 0 = 0 |
|
0 ∙ 0 = 0 |
0 + 1 = 1 |
|
1 - 0 = 1 |
|
0 ∙ 1 = 0 |
1 + 0 = 1 |
|
1 - 1 = 0 |
|
1 ∙ 0 = 0 |
1 + 1 = 10 |
|
10 - 1 = 1 |
|
1 ∙ 1 = 1 |
Двоичная таблица сложения |
|
Двоичная таблица вычитания |
|
Двоичная таблица умножения |
С помощью приведенных таблиц арифметические операции сложение, вычитание, умножение и деление двоичных чисел выполняются по тем же правилам, что и в десятичной системе счисления.
Пример:
Сложение Вычитание
+
1110101,111 10001110,1111
101000001,100 1000110,1110
Умножение Деление
1001
х
–
11,101 1001 11000101
+
–
10110111011 1001
–
10110111011 1001
–
1001
0000
Используя приведенные выше определения и приемы записи, легко построить позиционную систему счисления с любым основанием .