Компьютерная арифметика Компьютерная арифметика

Спецкурс в 7 семестре
Шауман А.М.


1. Проблемы представления чисел в компьютерах

Основные понятия и определения. Системы счисления. Весомозначные аддитивные системы счисления. Натуральный код. Базовые и полные алфавиты. Понятие машинного числа. Отображение множества вещественных чисел в множество машинных чисел.

Представление чисел разных знаков. Натуральный код с симметричным алфавитом и отрицатльным основанием системы счисленич. Прямой код. Дополнительные коды. Обратные коды. Унифицированный натуральный код.

Диапазон и точность представления машинных чисел. Определение характеристик точности и диапазона представления вещественных чисел. Естественная запятая. Фиксированная запятая. Представление чисел в форме с плавающей запятой. Понятие о переполнении в машинном коде. Выбор оптимального основания системы счисления при постоянной и переменной длине слов. Представление чисел с переменной величиной нолей мантиссы и порядка.

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

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

2. Принципы выполнения основных операций машинной арифметики.

Алгебраическое сложение. Параллельный сумматор. Учет переносов и переполнения. Определение знака результата. Особенности сложения и вычитания для прямых кодов. Двухпроводность операции вычитания прямых кодов. Формирование дополнений при вычитании. Реализация сложения и вычитания для дополнительных и обратных кодов.

Методы умножения. Умножение натуральных кодов. Методы реализации таблиц умножения. Машинная реализация умножения прямых кодов. Реализация методов умножения для дополнительных и обратных кодов. Влияние основания системы счисления на время реализации умножения.

Методы деления. Начальная установка делимого и делителя. Метод пробных вычитаний делителя из остатка. Машинная реализация методов для прямых, дополнительных и обратных кодов. Использование избыточного симметричного алфавита для оптимизации алгоритма деления без восстановления остатка. Особенности деления натуральных кодов с симметричным алфавитом.

Арифметические операции над числами с плавающей запятой. Сложение чисел с плавающей запятой. Выравнивание порядков. Сложение и округление мантисс. Нормализация результата. Правила сложения для очень больших и малых чисел и машинного нуля. Умножение и деление для чисел с плавающей запятой. Арифметические действия с числами при ненормализованной мантиссе.

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

3. Арифметика в нестандартных системах счисления с двоичным алфавитом

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

Композитные системы счисления. Определение весов разрядов в композитной системе счисления. Определение классов композитных систем счисления. Числа Фибоначчи как пример композитной системы счисления. Арифметика в нормальных фибоначчиевых системах счисления с положительными весами. Распространение переносов "вперед" и "назад". Операция "свертки" и "развертки". Арифметика в нормальных фибоначчиевых системах с чередующимися весами. Применение композитных систем счисления для контроля вычислений.

Двоично-r-ичные системы счисления. Избыточность представления как фактор, позволяющий организовать контроль вычислений. Особенности прямого и обратного перевода в двоичную систему счисления. Арифметика в двоично-r-ичных системах счисления. Требования, предъявляемые к сумматорам r-ичной системы счисления. Получение промежуточного результата и перевод его к конечному виду. Коды с естественными двоичными весами. Коды с искусственными двоичными весами. Невесомозначные коды. Коды с весами разных знаков. Экономичное представление и арифметика двоично-r+-ичных чисел. Особенности арифметики в двоично-стоичной системе счисления.

4. Нестандартные системы счисления.

Унифицированная система счисления. Перевод чисел из одной унифицированной системы в другую при одинаковом основании. Алгебраическое сложение. Округление результатов. Умножение и деление.

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

Знако-логарифмическая система счисления. Представление чисел. Использование постоянной памяти для реализации алгабраического сложения. Реализация умножения и деления как однопроходной операции алгебраического сложения. Проблемы перевода из знако-логарифмической системы счисления в десятичную и обратно.

5. Методы ускоренного выполнения операции сложения.

Метод ускоренного сложения для позиционных систем счисления с естественными весами. Асинхронный сумматор. Сумматор со скозным переносом. Сумматоры с обходным распространением переносов. Сумматоры с опережающими переносами. Сумматоры с сокращающимися переносами. Сумматор с избираемыми переносами. Сумматоры с условными переносами.

Методы ускоренного сложения при избыточном кодировании. Знако-разрядные избыточные системы счисления. Знако-разрядная двоичная система счисления. Избыточное колирование при неотрицательном алфавите. Избыточные алфавиты. Сложение с сохранением переносов.

Ускоренное суммирование в двоично-кодированных системах счисления. Модернизация классической схемы двоично-r-ичного сумматора. Использование отрицательных двоичных весов. Определение промежуточного двоичного результата.

Табличные методы суммирования. Многооперационное суммирование. Конвейерные схемы суммирования. Деревья спуска. Ускоренное суммирование чисел с плавающей запятой.

6. Методы ускоренного умножения и деления.

Методы быстрого умножения. Применение знакоразрядных цифр множителя. Ускоренный сдвиг частичных произведений. Использование кратных множимого. Определение кратных, для которых операция умножения реализуется как поразрядная логическая операция. Одновременное суммирование частичных произведений. Матричные умножители. Быстрое умножение чисел большой разрядности с использованием базового умножителя.

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

7. Аппаратная реализация специальных функций.

Возведение в квадрат. Метод последовательного суммирования. Табличный метод. Возведение в квадрат на основе использования переключательных функций алгебры логики. Реализация умножения через сложение и возведение в квадрат.

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

Вычисление логарифма двоичных чисел. Определение погрешности вычисления функции log(1+x). Таблично-арифметическая реализация вычисления функции log(1+x). Выбор оптимальных коэффициентов.

Аппаратурная реализация элементарных функций. Приближение функций полиномами и рациональными выражениями. Табличные методы. Таблично-алгоритмические методы. Итерационные методы. Вычисление элементарных функций по методу “цифра за цифрой”. Обоснование метода. Реализация метода “цифра за цифрой” на базе рекуррентных соотношений, описывающих алгоритмы “псевдоумножения” и “псевдоделения”.

На заглавную страницу Учебного плана специальности 220400

Документ установлен 15 декабря 1999 г.
Б.К.Мартыненко <д