Основы компьютерной арифметики и логики. Компьютерная арифметика Счетная машина Шиккарда

История развития компьютерной арифметики

Целью разработки компьютеров было автоматизировать выполнение расчетов, облегчить процесс вычислений. Первые вычислительные машины, которые выполняли четыре арифметические операции (сложение, вычитание, умножение и деление), были сконструированы в XVII столетии.

Счетная машина Шиккарда

В $1623$ г. Вильгельм Шиккард, немецкий ученый, математик, астроном, сконструировал машину, автоматически выполняющую операции сложения, вычитания, умножения и деления. Счетная машина содержала суммирующее, множительное устройства и механизм для записи промежуточных результатов. Разработка машины Шиккарда не стала достаточно известной, поэтому принципы ее работы не существенно повлияли на дальнейшее развитие вычислительной техники, но признана первооткрывательницей эры механической вычислительной техники.

Рисунок 1. Арифметическая машина Шиккарда

Суммирующая машина Паскаля

Машина Паскаля (названная ) была разработана французским ученым в $1641$ г. ($1643$ г. по другим данным) для выполнения финансовый расчётов, которыми занимался его отец. Принцип действия Паскалины был как у машины Шиккарда с одним отличием – в машине Паскаля был реализован автоматический перенос единицы в следующий разряд при полном обороте колеса предыдущего разряда (так же, как при сложении десятичных чисел в следующий разряд числа переносятся десятки, которые образовались в результате сложения единиц, сотни – в результате сложения десятков). Такое решение давало возможность выполнять сложение многозначных чисел автоматически, без человеческого вмешательства в работу механизма. Этот принцип использовался с середины XVII до XX века при построении механических арифмометров и электрических вычислительных машин.

Рисунок 2. Паскалина

Арифмометр Лейбница

Арифмометр был создан немецким математиком Готфридом В. Лейбницем в $1673$ г. Выполнение операции сложения чисел выполнялось как на Паскалине – при помощи связанных между собой колёс. В конструкцию была добавлена движущаяся часть и специальная рукоятка, которая позволяла крутить ступенчатое колесо (в последующем заменено на цилиндры), что ускоряло повторяющиеся операции сложения, при помощи которых выполнялось умножение и деление чисел. Необходимое количество повторных сложений выполнялось автоматически. Машина Лейбница могла выполнять четыре арифметические операции в десятичной системе счисления.

Рисунок 3. Копия арифмометра Лейбница в Немецком музее

Арифмометр разработан в $1873$ г. русским механиком В.Т. Однером.

Рисунок 4. Арифмометр Однера

Арифмометр являлся успешным образцом, но все же массовое изготовление таких машин всё ещё было невыгодным. Попытки усовершенствовать арифмометр тянулись весь XVIII век и только в XIX веке арифмометры стали широко распространены.

Рисунок 5. Арифмометр 1932 г. выпуска

В XX веке на смену механическим вычислительным машинам пришли электронные, в основе которых лежат алгоритмы, использующие минимальное число элементарных операций для выполнения арифметических операций.

Особенности представления чисел в компьютере

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

• естественная форма (с фиксированной запятой);
• нормальная форма (с плавающей запятой).

Пример 1

Рисунок 6.

Всякое десятичное число, прежде чем оно попадает в память компьютера, преобразуется из десятичной системы счисления в двоичную. Форма с фиксированной запятой применяется к целым числам (как положительным, так и отрицательным), форма с плавающей запятой – к вещественным числам (целым и дробным). Под запятой подразумевается знак-разделитель целой и дробной части числа.

Диапазон чисел, представляемых в компьютере, измеряется значением $2^n$, где $n$ – разрядность двоичного числа.

Определение 1

Если числа только положительные, то они называются беззнаковыми целыми .

Для представления положительных и отрицательных чисел используются такие формы представления, как:

• код со смещением;
• прямой код;
• дополнительный код – наиболее удобная форма для представления отрицательных чисел при выполнении арифметических операций посредством компьютера. Форма дополнительного кода сложна для понимания, но очень хорошо подходит для выполнения арифметических действий.

Формы представления чисел в формате с плавающей запятой сложнее, чем в формате с фиксированной запятой. Основная идея – мантисса умножается на число $10$ в степени, равной экспоненте.

Рисунок 7.

Такая форма записи является удобной для представления очень больших и очень маленьких чисел.

В памяти компьютера форма представления числа с плавающей запятой использует основание, равное $2$, а не $10$:

$1,2345 \cdot 2^{10}$.

Определение 2

Числа с плавающей запятой являются нормализованными, т.е. только одна цифра, не равная нулю, располагается слева от десятичной точки (называется двоичной точкой ). Для числа по основанию $2$ существует только одна цифра, не равная нулю – это $1$. Поэтому для мантиссы эта цифра всегда равна $1$ и ее можно не записывать.

В настоящей книге рассматриваются методы быстрого выполнения различных видов вычислений, рассказывается о реализации быстрых алгоритмов как в виде логических схем - математической модели реальных электронных микросхем, так и в виде компьютерных программ. Исследуются также вопросы о том, как измерить сложность того или иного вычислительного алгоритма и оценить время его работы на компьютере. Большая часть материала книги доступна всем, кто знаком лишь со школьным курсом математики, но и опытный читатель может найти в этой книге кое-что новое для себя.
Книга написана на основе лекций, которые автор в разное время читал учащимся физико-математической Школы им. А. Н. Колмогорова при МГУ, на Малом и Большом мехмате, а также на факультетах информационной безопасности и информатики РГГУ.

Быстрое деление многочленов.
Здесь будет показано, что деление можно выполнять с той же по порядку сложностью, что и умножение. Впервые это было сделано немецким математиком Фолкером Штрассеном в 70-е гг. XX века. Мы приведем другое доказательство, которое далее почти дословно будет перенесено и на случай деления многозначных чисел.

Обозначим D0(m, n) наименьшее количество арифметических операций над числами, требующихся для нахождения неполного частного при делении многочлена степени не выше га на многочлен степени n, а через D(m, n) - сложность деления этих многочленов, в которую включается также сложность нахождения остатка от деления и произведения неполного частного на делитель. Очевидно, что при m < n обе эти величины равны нулю. Далее для удобства изменим определение M(n, m), заменив его на М(n + 1, m + 1), т. е. обозначим М(m, n) сложность умножения двух многочленов степеней m и n соответственно.

Содержание
От автора
Введение
Глава 1. Школьные алгоритмы арифметических операций с многочленами
Глава 2. Школьные алгоритмы сложения и умножения чисел
Глава 3. Умножение столбиком нескольких чисел
Глава 4. Переносы при сложении двоичных чисел и теорема Куммера
Глава 5. Минимальные формы двоичной записи с цифрами 0 и ± 1 и первая попытка уменьшить сложность умножения
Глава 6. Быстрое умножение многочленов
Глава 7. Быстрое умножение чисел
Схемная реализация метода Карацубы для умножения двоичных чисел
Глава 8. Деление многозначных чисел
Глава 9. Как представляются отрицательные числа в компьютере
Глава 10. SRT-деление
Глава 11. Быстрое деление многочленов
Глава 12. Быстрое деление чисел
Глава 13. Сравнение сложности умножения, деления, возведения в квадрат и извлечения квадратного корня
Глава 14. О сложности преобразования чисел из одной системы в другую
Глава 15. Модулярная арифметика и китайская теорема об остатках
Глава 16. Сложность операций модулярной арифметики
Как найти остаток от деления, не вычисляя частное
Глава 17. Умножение и деление на константы
Глава 18. Некоторые быстрые алгоритмы работы с битами
Маленькие хитрости в работе с битами
Глава 19. Вычисление некоторых целочисленных элементарных функций
Целочисленный квадратный корень
Целочисленные логарифмы
Глава 20. Быстрые операции с дробно-рациональными функциями
Быстрое сложение дробно-рациональных функций
Быстрый китайский алгоритм
Быстрая интерполяция
Еще о быстром умножении многочленов
Глава 21. Варианты алгоритма Евклида
Алгоритм Евклида с выбором минимального остатка
Бинарный алгоритм Евклида
Глава 22. Еще о схеме Горнера
Глава 23. Что можно вычислить на счетах
Литература.

Бесплатно скачать электронную книгу в удобном формате, смотреть и читать:
Скачать книгу Занимательная компьютерная арифметика, Быстрые алгоритмы операций с числами и многочленами, Гашков С.Б., 2012 - fileskachat.com, быстрое и бесплатное скачивание.

Скачать pdf
Ниже можно купить эту книгу по лучшей цене со скидкой с доставкой по всей России.

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

Практические работы

Для выполнения этих работ используется учебный компьютер «ЛамПанель», который можно загрузить со страницы http://kpolyakov. spb. ru/prog/lamp. htm.

Программа «ЛамПанель» – это модель процессора, который управляет ламповой панелью, то есть, может с помощью специальных команд зажигать и гасить определенные лампочки.

Процессор обрабатывает данные, используя специальные сверхбыстродействующие ячейки собственной памяти – регистры. В этой работе мы будем использовать только четыре 16-битных регистра общего назначения, которые называются R0, R1, R2 и R3. В области 1 на рисунке вы видите двоичные значения этих регистров (показаны черным цветом), шестнадцатеричные (синий цвет) и десятичные, без учета знака (зеленый цвет) и со знаком (коричневый цвет).

Область 2 – это текстовый редактор, в котором набирается программа для процессора на специальном языке, который называется языком ассемблера. Для того, чтобы программа выполнилась, нужно нажать клавишу F9 (выполнение без остановки) или F8 (выполнение по шагам). Чтобы программа остановилась, процессор должен выполнить команду STOP. Таким образом, простейшая программа состоит из одной команды STOP.

Для того, чтобы записать число в регистр, используют команду MOV (от англ. move – переместить). Числа записываются в шестнадцатеричной системе счисления. Например, команда

запишет число 1216 = 18 в регистр R0. Каждая команда записывается в отдельной строке. Поэтому полная программа будет выглядеть так:

Для того, чтобы добавить число к регистру, применяют команду ADD (от англ. add – сложить). Например, команда

добавляет число 1516 = 23 к регистру R0. Есть и аналогичная команда вычитания – SUB (от англ. subtract – вычесть). Нам будет нужна еще одна команда:

которая выполняет инверсию всех битов регистра, то есть меняет все нули на единицы, а единицы – на нули.

Запустите тренажер «Лампанель». Используя команду MOV, напишите программу, которая заполнит регистры так, как на рисунке:

Не забудьте закончить программу командой STOP. Выполните программу.

Программа:

Какую операцию выполняет этот алгоритм? Найдите описание этого алгоритма в учебнике.

и заполните таблицу:

Подсказка: 65535=FFFF16, 32767=7FFF16

Арифметические операции с целыми числами

Знакомство с программой «ЛамПанель»

Кроме регистров общего назначения, с которыми мы уже работали, в процессоре есть служебные регистры. В этой работе мы будем использовать один из них – регистр состояния PS. Используются только три младших бита этого регистра (см. рисунок), которые показывают, какой результат был получен в результате последней операции:

бит C (от англ. carry – перенос) установлен (равен 1), если произошел перенос; в остальных случаях сброшен (равен 0); бит Z (от англ. zero – ноль) установлен, если результат последней операции – ноль; в остальных случаях сброшен; бит N (от англ. negative – отрицательный) установлен, если результат последней операции отрицательный; в остальных случаях сброшен. бит O (от англ. overflow – переполнение) установлен, если в результате последней операции произошло переполнение и результат неверен; в остальных случаях сброшен.

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

Если результат предыдущей операции НЕ равен нулю, то происходит переход на указанную метку. Вот пример программы, которая вычисляет сумму натуральных чисел от 1 до 5:

MOV 0, R0 ; начальное значение суммы

MOV 5, R1 ; количество шагов цикла

m: ; метка обозначает начало цикла

ADD R1, R0 ; R0:= R0 + R1

SUB 1, R1 ; уменьшить R1 – оставшееся число шагов

JNZ m ; переход, если получился не ноль

Здесь в каждой строчке после точки с запятой записан комментарий, объясняющий ее действие. Давайте проследим, как выполняется эта программа:

Цикл заканчивается, потому что бит Z равен 1 (результат последней операции вычитания – ноль) и перехода по команде JNZ не происходит.

Запустите тренажер «Лампанель». Вычислите приведенные выражения с помощью программы. Запишите в таблицу результаты, значение знакового бита и битов O, C, N и Z.
Замечание: в программу нужно вводить числа в шестнадцатеричной системе счисления!

Объясните полученные результаты:

Программа:

Замечание: в программу нужно вводить числа в шестнадцатеричной системе счисления!

Для выполнения умножения используйте команду MUL (см. справочную систему, клавиша F1).

Программа:

С помощью программы заполните таблицу:

Объясните результаты, полученные в последних двух строчках:

Логические операции и сдвиги

Знакомство с программой «ЛамПанель»

В программе «ЛамПанель» можно использовать логические операции «НЕ» (уже знакомая нам команда NOT), «И» (команда AND), «ИЛИ» (команда OR) и «исключающее ИЛИ» (команда XOR). В последних трех командах после названия команды сначала указывается маска, а затем через запятую – регистр, к которому применяется логическая операция. Например, команда

обнуляет старшие 8 бит (старший байт) регистра R0. Маска может находиться в регистре, например, последовательность команд

устанавливает в единицу 8 младших бит регистра R0, а остальные оставляет без изменений.

Для выполнения сдвигов используются следующие команды

SHL 1,R0 ; логический сдвиг влево на 1 бит

SHR 2,R0 ; логический сдвиг вправо на 2 бита

SAR 1,R0 ; арифметический сдвиг вправо на 1 бит

ROL 2,R0 ; циклический сдвиг влево на 2 бита

ROR 3,R0 ; циклический сдвиг вправо на 3 бита

Конечно, сдвиг может применяться к любому регистру общего назначения, а не только к R0.

Задание на практическую работу

Запустите тренажер «ЛамПанель». Напишите программу, которая решает следующую задачу, используя логические операции:

В регистрах R1, R2 и R3 записаны коды трех десятичных цифр, составляющих трехзначное число (соответственно сотни, десятки и единицы). Построить в регистре R0 это число. Например, если R1=3116, R2=3216 и R3=3316, в регистре R0 должно получиться десятичное число 123.

Программа:

Ответьте на вопросы:

как изменится результат выполнения программы, если в команде 1 записать в R0 другое число?

как изменится результат выполнения программы, если в командах 2 и 3 заменить маску на другую, например, на CB2416?

как изменится результат выполнения программы, если маску в команде 2 изменить, а маску в команде 3 не менять?

Замечание: не забудьте перевести числа в шестнадцатеричную систему!

Когда последовательное выполнение этих двух команд не изменяет данные?

При кодирование цвета используются 4-битные значения составляющих R (красная), G (зеленая) и B (синяя). Коды этих составляющих записаны в регистрах R1, R2 и R3. Построить в регистре R0 полный код цвета. Например, если R1=A16, R2=B16 и R3=C16, в регистре R0 должно получиться число ABC16.

Программа:

Учебное пособие

Омск– 2004

УДК 004.9(075)

ББК 32.973.202+22.12 я 73

Рецензенты:

С.А. Терентьев, канд. физ.-мат. наук, Омский государственный университет;

О.Н. Лучко канд. пед. наук, Омский государственный институт сервиса

Потапов В.И., Шафеева О.П., Червенчук И.В.

П 64 Основы компьютерной арифметики и логики: Учеб.пособие. – Омск: Изд- во

ОмГТУ, 2004. – 172 с.

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

Предназначено для студентов направления «Информатика и вычислительная техника».

Печатается по решению редакционно-издательского совета Омского государственного технического университета.

УДК 004.9(075)

ББК 32.973.202+22.12 я 73

© Омский государственный

технический университет, 2004

ПРЕДИСЛОВИЕ

В учебных планах подготовки дипломированных специалистов по специальности 220100 – «Вычислительные машины, комплексы, системы и сети» и направлению 552800 – «Информатика и вычислительная техника» дисциплины «Дискретная математика», «Введение в информатику и вычислительную технику», «Алгоритмические языки и программирование» входят в состав фундаментального цикла дисциплин, формирующих у студентов представление о базовых понятиях информатики и вычислительной техники как о предмете их дальнейшей профессиональной деятельности. Изучение указанных дисциплин и овладение навыками разработки и моделирования алгоритмов реализации арифметических и логических компьютерных операций, синтеза логических схем создает теоретическую базу для изложения таких дисциплин, как «Теория автоматов», «Организация ЭВМ и систем», «Микропроцессорные системы» и других специальных курсов.

В главах 1, 2, 3, подготовленных профессором В.И. Потаповым, изложены основы двоичной и десятичной компьютерной арифметики, алгоритмы выполнения арифметических операций в ЭВМ для двоичных чисел с фиксированной и плавающей запятой (точкой) и для двоично-десятичных чисел в D-кодах. Рассмотрены многочисленные методы ускоренного выполнения арифметических операций в ЭВМ в двоичной и в двоично-десятичной системе счисления.

Глава 4, подготовленная доцентом О.П. Шафеевой, посвящена вопросам разработки алгоритмических моделей выполнения арифметических операций и моделирования на ПЭВМ спроектированных алгоритмов.

В главе 5, подготовленной доцентом И.В. Червенчуком, рассматриваются фундаментальные вопросы математической логики и задачи синтеза комбинационных схем на логических элементах, а также свойства булевых функций и вопросы их минимизации известными в инженерной практике методами.

Учебное пособие иллюстрировано многочисленными примерами и содержит вопросы для самоконтроля.