Компьютерная арифметика. Особенности представления чисел в компьютере
К. Поляков, Компьютерная арифметика 1.Особенности представления чисел в компьютереОсобенности представления чисел в компьютере 2.Хранение в памяти целых чиселХранение в памяти целых чисел 3.Операции с целыми числамиОперации с целыми числами 4.Хранение в памяти вещественных чиселХранение в памяти вещественных чисел 5.Операции с вещественными числамиОперации с вещественными числами
К. Поляков, Компьютерная арифметика Тема 1. Особенности представления чисел в компьютере
Компьютерная арифметика К. Поляков, Предельные значения чисел В математике нет предельных значений! В компьютере – конечное число деталей, ограниченное количество разрядов. Какой диапазон? ? 10000?
Компьютерная арифметика К. Поляков, Предельные значения чисел 4 система счисления с основанием B K разрядов Переполнение разрядной сетки это ситуация, когда число, которое требуется сохранить, не умещается в имеющемся количестве разрядов вычислительного устройства.
Компьютерная арифметика К. Поляков, Вещественные числа 5 система счисления с основанием B F разрядов в дробной части Какой диапазон? ?
Компьютерная арифметика К. Поляков, Неточность представления 6 Не все вещественные числа могут быть представлены в компьютере точно! ! 0,3211 0,3212 0,3214
Компьютерная арифметика К. Поляков, Дискретность 7 1.Целые числа дискретны. 2.Вещественные числа непрерывны. 3.Компьютер работает только с дискретными данными. 4.При дискретизации может происходить потеря информации (искажение данных). 5.Большинство трудностей связано с кодированием вещественных чисел. Для хранения вещественных чисел нужна дискретизация! !
К. Поляков, Компьютерная арифметика Тема 2. Хранение в памяти целых чисел
Компьютерная арифметика К. Поляков, Целые числа без знака (unsigned) 9 78 = Беззнаковые данные – не могут быть отрицательными биты младший старший старший полубайт старшая цифра младший полубайт младшая цифра 4 16 E = 4E 16 = N
Компьютерная арифметика К. Поляков, Целые числа без знака 10 01…127128… …7F …FF … … C0 16 FF FF 16 C В газете «Информатика» (1/2011) есть опечатки на этой схеме: вместо «64» набрано «-64»!
Компьютерная арифметика К. Поляков, Целые числа без знака: диапазон 11 KX min X max типы данных byte (Паскаль) unsigned char (Си) word (Паскаль) unsigned short (Си) cardinal (Delphi) unsigned int (Си) ?
Компьютерная арифметика К. Поляков, Целые числа со знаком 12 Сколько места требуется для хранения знака? ? Старший (знаковый) бит числа определяет его знак. Если он равен 0, число положительное, если 1, то отрицательное. Прямой код: 78 = – 78 = –
Компьютерная арифметика К. Поляков, Целые числа со знаком 13 Идея: «– 1» должно быть представлено так, чтобы при сложении с числом «1» получить 0. Как кодируется «-1»? ? Для 8-битных чисел: код числа «–X» равен двоичному коду числа 256 – X (дополнение до 256). При K-битном кодировании дополнительный код числа «–X» равен двоичному коду числа 2 K – X (дополнение до 2 K). !
Компьютерная арифметика К. Поляков, Как построить дополнительный код? 14 Алгоритм А0: перевести число 2 K – X в двоичную систему счисления. для вычислений требуется K+1 разряд Алгоритм А1: 1)перевести число X в двоичную систему счисления; 2)построить обратный код, выполнив инверсию всех битов (заменить 0 на 1 и наоборот); 3)к результату добавить 1. Алгоритм А1: 1)перевести число X в двоичную систему счисления; 2)построить обратный код, выполнив инверсию всех битов (заменить 0 на 1 и наоборот); 3)к результату добавить = инверсия +1+1
Компьютерная арифметика К. Поляков, Как построить дополнительный код? 15 Алгоритм А2: 1)перевести число X-1 в двоичную систему счисления; 2)выполнить инверсию всех битов. Алгоритм А2: 1)перевести число X-1 в двоичную систему счисления; 2)выполнить инверсию всех битов = 77 = инверсия Алгоритм А3: 1)перевести число X в двоичную систему счисления; 2)выполнить инверсию всех старших битов числа, кроме младшей единицы и нулей после нее. Алгоритм А3: 1)перевести число X в двоичную систему счисления; 2)выполнить инверсию всех старших битов числа, кроме младшей единицы и нулей после нее. 78 = инверсия
Компьютерная арифметика К. Поляков, Целые числа со знаком 16 –128–127…–1 0… …FF …7F … … F С FF – 128 – 1– – – – 128 – F 16 С FF
Компьютерная арифметика К. Поляков, Целые числа co знаком: диапазон 17 KX min X max типы данных 8– shortInt (Delphi) char (Си) 16– smallInt (Delphi) short (Си) 32 – integer (Delphi) int (Си) 64 – – 1 int64 (Delphi) long long (Си)
К. Поляков, Компьютерная арифметика Тема 3. Операции с целыми числами
Компьютерная арифметика К. Поляков, Сложение и вычитание 19 Операции с положительными и отрицательными числами выполняются по одинаковым алгоритмам! ! Вычитание = сложение с дополнительным кодом вычитаемого! !
Компьютерная арифметика К. Поляков, Переполнение 20 знаковый бит бит переноса Если бит переноса не совпадает со знаковым битом результата, произошло переполнение и результат неверный. ! СS СS
Компьютерная арифметика К. Поляков, Умножение Умножение выполняется в помощью сложения и сдвига. ! × ×
Компьютерная арифметика К. Поляков, Поразрядные логические операции 22 Поразрядные операции выполняются с отдельными битами числа и не влияют на остальные. Сложение – это поразрядная операция? ? регистр Операция «НЕ» (инверсия, not): R not R
Компьютерная арифметика К. Поляков, Логическая операция «И» (and, &) 23 DMD and M данные маска Маска – константа, которая определяет область применения логической операции к битам многоразрядного числа. С помощью операции «И» можно сбросить (установить в ноль) биты, для которых маска равна 0! ! D D and M M AA 16 6С AA 16 and 6C 16 = ?
Компьютерная арифметика К. Поляков, Логическая операция «ИЛИ» (or, |) 24 DMD or M С помощью операции «ИЛИ» можно записать единицу в биты, для которых маска равна 1! ! D D or M M AA 16 6С 16 EE AA 16 or 6C 16 = ?
Компьютерная арифметика К. Поляков, Операция «исключающее ИЛИ» (xor, ^) 25 DMD xor M С помощью операции «исключающее ИЛИ» можно инвертировать биты, для которых маска равна 1! ! D D xor M M AA 16 6С 16 C AA 16 xor 6C 16 = ?
Компьютерная арифметика К. Поляков, Шифрование с помощью xor 26 Идея: (A xor B) xor B = Операция «исключающее ИЛИ» обратима, то есть ее повторное применение восстанавливает исходное значение! ! A Текст: 2*2=4 Коды символов: "2" = = "*" = 2A 16 = "=" = 3D 16 = "4" = =
Компьютерная арифметика К. Поляков, Шифрование с помощью xor 27 Исходный текст: 2*2=4 "2" xor = "*" 2A 16 xor = "=" 3D 16 xor = "4" xor = "%" 3D 16 "=" 2A 16 "*" "#" Маска: 23 = = Зашифрованный текст: %=%*# Расшифровка: "%" xor = "=" 3D 16 xor = "*" 2A 16 xor = "#" xor = "2" 2A 16 "*" 3D 16 "=" "4" В газете «Информатика» (1/2011) есть опечатка: вместо «%=%*#» набрано «%=%7*7#»!
1; N = N > 1; N:= N shl 1; N:= N shr 1; N:= N shl 1; N:= N shr 1" title="Компьютерная арифметика К. Поляков, 2010 http://kpolyakov.narod.ru Логический сдвиг 28 10011011 Влево: 0011011010 бит переноса С Вправо: 10011011 01001101 1 С 0 Си: Паскаль: N = N > 1; N = N > 1; N:= N shl 1; N:= N shr 1; N:= N shl 1; N:= N shr 1" class="link_thumb"> 28 Компьютерная арифметика К. Поляков, Логический сдвиг Влево: бит переноса С Вправо: С 0 Си: Паскаль: N = N > 1; N = N > 1; N:= N shl 1; N:= N shr 1; N:= N shl 1; N:= N shr 1; shift left shift right 1; N = N > 1; N:= N shl 1; N:= N shr 1; N:= N shl 1; N:= N shr 1"> 1; N = N > 1; N:= N shl 1; N:= N shr 1; N:= N shl 1; N:= N shr 1; shift left shift right"> 1; N = N > 1; N:= N shl 1; N:= N shr 1; N:= N shl 1; N:= N shr 1" title="Компьютерная арифметика К. Поляков, 2010 http://kpolyakov.narod.ru Логический сдвиг 28 10011011 Влево: 0011011010 бит переноса С Вправо: 10011011 01001101 1 С 0 Си: Паскаль: N = N > 1; N = N > 1; N:= N shl 1; N:= N shr 1; N:= N shl 1; N:= N shr 1"> title="Компьютерная арифметика К. Поляков, 2010 http://kpolyakov.narod.ru Логический сдвиг 28 10011011 Влево: 0011011010 бит переноса С Вправо: 10011011 01001101 1 С 0 Си: Паскаль: N = N > 1; N = N > 1; N:= N shl 1; N:= N shr 1; N:= N shl 1; N:= N shr 1">
Компьютерная арифметика К. Поляков, Логический сдвиг Влево: Вправо: Если число нечётное? ? Логический сдвиг влево (вправо) – это быстрый способ умножения (деления без остатка) положительного числа на 2. Если число отрицательное? ?
Компьютерная арифметика К. Поляков, Арифметический сдвиг (вправо) 30 –12 Если число нечётное? ? С – 6 Примеры: –20 –15 –11 –3–3 –1 –10 –8 –6 –2 –1 Арифметический сдвиг вправо – деление на 2 нацело с округлением «вниз» (к ближайшему меньшему целому).
Компьютерная арифметика К. Поляков, Циклический сдвиг Влево: Вправо: Циклический сдвиг предназначен для последовательного просмотра битов без потери данных. !
Компьютерная арифметика К. Поляков, Пример 32 Задача: в целой переменной N (32 бита) закодирована информация о цвете пикселя в RGB: Записать в переменные R, G, B составляющие цвета. Вариант 1: 1.Обнулить все биты, кроме G. Маска для выделения G: 0000FF Сдвинуть вправо так, чтобы число G передвинулось в младший байт. 0RGB Си: G =(N & 0xFF00) >> 8; Паскаль: G:=(N and $FF00) shr 8;
> 8; Паскаль: G:=(N and $FF00) shr 8;">
Компьютерная арифметика К. Поляков, Пример 33 Вариант 2: 1.Сдвинуть вправо так, чтобы число G передвинулось в младший байт. 2.Обнулить все биты, кроме G. Маска для выделения G: FF 16 0RGB Си: G =(N >> 8) & 0xFF; Паскаль: G:=(N shr 8) and $FF; Как решить, используя только сдвиги? ?
> 8) & 0xFF; Паскаль: G:=(N shr 8) and $FF; Как решить, используя только сдвиги? ?">
Компьютерная арифметика К. Поляков, Пример 34 0RGB Си: R =B =R =B = R =B =R =B = Паскаль: R:= B:= R:= B:=
Компьютерная арифметика К. Поляков, Хранение вещественных чисел 36 С фиксированной запятой (в первых ЭВМ): целая частьдробная часть для больших и маленьких чисел нужно масштабирование 0,0 С плавающей запятой (автоматическое масштабирование): знакпорядок P значащая часть Z положение запятой цифры числа 1,2345· ,2345·10 17
Компьютерная арифметика К. Поляков, Хранение вещественных чисел 37 Теоретически оптимальный вариант (целая часть = 0): 0, = 0,12345· ,345 = 0,12345·10 2 X 10 всегда 0 один разряд расходуется впустую! Экономный вариант (целая часть от 1 до B): основание системы счисления X 10 0, = 1,2345· ,345 = 1,2345·10 1 повышение точности при конечном числе разрядов
Компьютерная арифметика К. Поляков, Число обычной точности (single) ,25 = ,01 2 = -1, ·2 4 знакпорядокзначащая часть single: 4 байта = 32 бита мантисса = дробная часть Z порядок со смещением знак p = = 131 = С18A000 0 для single
Компьютерная арифметика К. Поляков, Диапазон вещественных чисел 40 типдиапазон число десятичных значащих цифр размер (байт) single1,4· – 3,4· double4,9· – 1,8· extended3,6· – 1,2· Extended – тип для вычислений в сопроцессоре, единица в значащей части не скрывается. Single, double – только для хранения.
Компьютерная арифметика К. Поляков, Сложение и вычитание 42 1)порядки выравниваются до большего 2)значащие части складываются (или вычитаются) 3)результат нормализуется Как сложить два числа с плавающей запятой? ! 1,2345·10 – 5 + 1,2345·10 5 = ? Пример: 7,25 = 111,01 2 = 1, ·2 2 1,75 = 1,11 2 = 1,11 2 ·2 0 1,75 = 0, ·2 2 1,011120,01 2 ·2 2 = 1,001 2 ·2 3 Почему порядки выравнивают до большего? ?
Компьютерная арифметика К. Поляков, Умножение и деление 43 Как умножить два числа с плавающей запятой? ! 1,2345·10 – 5 · 1,2345·10 5 = ? 1)значащие части умножаются (или делятся) 2)порядки складываются (или вычитаются) 3)результат нормализуется Пример: 1,75 = 1,11 2 = 1,11 2 ·2 0 6 = = 1,1 2 ·2 2 1,11 2 ·1,1 2 = 10,101 2 ·2 2 = 1, ·2 3 Надо ли выравнивать порядки? ? = = 2
Компьютерная арифметика К. Поляков, Конец фильма ПОЛЯКОВ Константин Юрьевич д.т.н., учитель информатики высшей категории, ГОУ СОШ 163, г. Санкт-Петербург
История развития компьютерной арифметики
Целью разработки компьютеров было автоматизировать выполнение расчетов, облегчить процесс вычислений. Первые вычислительные машины, которые выполняли четыре арифметические операции (сложение, вычитание, умножение и деление), были сконструированы в 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$ и ее можно не записывать.
КОМПЬЮТЕРНАЯ АРИФМЕТИКА, техническая дисциплина, предметом исследования которой является представление чисел в ЭВМ, алгоритмы вычисления элементарных функций, арифметических операций и др., а также реализующая их аппаратура.
Компьютерная арифметика активно развивается, что обусловлено совершенствованием микроэлектроники (например, значительно уменьшилось время переключения транзистора). Одно из основных направлений компьютерной арифметики - аппаратная реализация алгоритмов, которые прежде осуществлялись программным способом. Например, раньше во многих ЭВМ операция деления выполнялась специальной подпрограммой, теперь почти во всех ЭВМ есть устройство деления и извлечения квадратного корня; вычисление элементарных функций также всё чаще реализуется аппаратными средствами. Это позволяет значительно ускорить (иногда в тысячи раз) вычисления.
В современных ЭВМ применяется двоичная система счисления (смотри Информации представление в ЭВМ). Для представления чисел в ЭВМ обычно используют прямой, обратный и дополнительный коды. Во всех кодах значение знакового разряда положительного числа равно 0, а отрицательного 1. Прямой код числа представляет собой знак числа (знаковый разряд) и модуль (абсолютную величину) числа. Представление положительных чисел во всех кодах совпадает. Обратный код отрицательного числа имеет 1 в качестве знака и поразрядную инверсию (замену всех нулей единицами и всех единиц нулями) модуля в остальных разрядах. Дополнительный код отрицательного числа равен обратному коду этого числа, к младшему разряду которого прибавлена 1. В компьютерной арифметике, как правило, используются два способа представления чисел: с фиксированной и плавающей запятой. Числа с фиксированной запятой - это числа, у которых запятая, отделяющая целую часть от дробной, стоит на постоянном, т. е. фиксированном, месте (обычно справа от младшего разряда числа). В научных и технических вычислениях используются как очень большие, так и очень маленькие числа, то есть требуется большой диапазон представления чисел, который не могут обеспечить числа с фиксированной запятой. В этом случае применяют числа с плавающей запятой. Число с плавающей запятой представляется в виде:
N= (-1) S ·М·2 Е,
где N - величина числа, S - знак числа, М - мантисса, Е - порядок. Если S = 0, то число положительное, если S=1, то число отрицательное. Обычно на мантиссу накладывается ограничение 1≤ М < 2; мантисса, удовлетворяющая этому условию, называется нормализованной. Порядок числа представляется со смещением на половину диапазона (например, у чисел с плавающей запятой формата 64 разряда порядок занимает 11 двоичных разрядов, к порядку всегда прибавляется смещение 1023 = 2 10 -1) ; смещённый порядок Е - всегда положительное число.
Вычисления с плавающей запятой приблизительны, поскольку младшие разряды результата, которым не хватает места в разрядной сетке ЭВМ, отбрасываются и производится округление. При вычислениях ошибка округления накапливается и может стать достаточно большой. Интервальная арифметика (разрабатывающая методы интервальных вычислений) в качестве результата операции даёт не число, а интервал между двумя числами, содержащий точный результат, который можно было бы получить, если бы младшие разряды результата не терялись. Если интервал, в котором заключён результат, очень большой, то выбранный алгоритм имеет недостаточную точность.
Раньше результаты одной и той же программы, производящей вычисления с плавающей запятой, на ЭВМ разных семейств различались, поскольку семантика операций с плавающей запятой не была строго описана в системе команд ЭВМ (ЭВМ отличались по числу разрядов порядка и мантиссы, способу их кодировки, основанию системы счисления, способу округления и др.). В связи с этим в 1985 году в США был принят стандарт на двоичную арифметику с плавающей запятой ANSI/IEEE Standard No. 754. Его принятие значительно улучшило переносимость программ (например, с ЭВМ одной платформы на ЭВМ другой платформы), повысило точность вычислений. С конца 20 века большинство выпускаемых ЭВМ соответствует этому стандарту.
При хранении, передаче и обработке информации в ЭВМ возможно появление ошибки. Разработаны коды, обнаруживающие ошибки, и коды, которые исправляют ошибки (например, так называемые коды Хэмминга). На основе элементарной теории чисел в компьютерной арифметике разрабатываются алгоритмы и аппаратура шифровки и дешифровки информации для криптографии.
Лит.: Карцев М. А. Арифметика цифровых машин. М., 1969; Koren I. Computer arithmetic algorithms. 2nd ed. Natick, 2002.
Омск– 2004
УДК 004.9(075)
ББК 32.973.202+22.12 я 73
Рецензенты:
С.А. Терентьев, канд. физ.-мат. наук, Омский государственный университет;
О.Н. Лучко канд. пед. наук, Омский государственный институт сервиса
Потапов В.И., Шафеева О.П., Червенчук И.В.
П 64 Основы компьютерной арифметики и логики: Учеб.пособие. – Омск: Изд- во
ОмГТУ, 2004. – 172 с.
Изложены основы двоичной и десятичной компьютерной арифметики, алгоритмы выполнения арифметических операций в ЭВМ для двоичных чисел с фиксированной и плавающей запятой и для двоично-десятичных чисел в D-кодах. Рассмотрены методы ускорения выполнения основных арифметических операций в ЭВМ в двоичной и в двоично-десятичной системе счисления. Описаны алгоритмические модели выполнения арифметических операций и изложены методы их проектирования. Даются основные понятия математической логики и методы синтеза комбинационных схем.
Предназначено для студентов направления «Информатика и вычислительная техника».
Печатается по решению редакционно-издательского совета Омского государственного технического университета.
УДК 004.9(075)
ББК 32.973.202+22.12 я 73
© Омский государственный
технический университет, 2004
| |
|||
| ОГЛАВЛЕНИЕ | ||
| Предисловие………………………………………………………………… | ||
| 1. | Основы двоичной компьютерной арифметики ……………………….. | |
| 1.1. | Позиционные системы счисления …………………………………………. | |
| 1.1.1. | Десятичная позиционная система счисления …………………….………. | |
| 1.1.2. | Двоичная позиционная система счисления ……………………..………… | |
| 1.1.3. | Восьмеричная позиционная система счисления ………………………….. | |
| 1.1.4. | Шестнадцатеричная позиционная система счисления …………………… | |
| 1.2. | Перевод чисел из одной позиционной системы счисления в другую…… | |
| 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. | Ускорение умножения в D-кодах ………………………………………….. | |
| 3.2.4. | Деление десятичных чисел в ЭВМ ………………………………………... | |
| 4. | Алгоритмические модели выполнения арифметических операций... | |
| 4.1. | Проектирование универсального алгоритма перевода чисел в разные системы счисления ………………………………………………. | |
| 4.2. | Моделирование алгоритма сложения двоичных чисел ………………….. | |
| 4.3. | Проектирование алгоритма умножения чисел ……………………………. | |
| 4.4. | Разработка алгоритма ускоренного умножения с обработкой за один такт трех разрядов множителя ……………………………………. | |
| 4.5. | Проектирование алгоритма деления чисел ……………………………….. | |
| 4.6. | Разработка алгоритма ускоренного выполнения операции деления с анализом за один такт двух разрядов делителя ………………………… | |
| 4.7. | Разработка алгоритма вычисления квадратного корня …………………... | |
| 5. | Математическая логика и синтез комбинационных схем …………… | |
| 5.1. | Соответствия и предикаты …………………………………………………. | |
| 5.1.1. | Соответствия ………………………………………………………………... | |
| 5.1.2. | Логические функции ……………………………………………………….. | |
| 5.1.3. | Признаки …………………………………………………………………….. | |
| 5.1.4. | Бинарные отношения………………………………………………………... | |
| 5.2. | Булевы функции …………………………………………………………….. | |
| 5.2.1. | Логические операции соединения………………………………………….. | |
| 5.2.2. | Булевы формулы…………………………………………………………….. | |
| 5.2.3. | Совершенные дизъюнктивные нормальные формы ……………………… | |
| 5.2.4. | Булева алгебра ………………………………………………………………. | |
| 5.2.5. | Конъюнктивные нормальные формы …………………………………… | |
| 5.2.6. | Классы булевых функций. Понятие базиса………………………………... | |
| 5.2.7. | Минимизация булевых функций…………………………………………… | |
| 5.3. | Методика синтеза комбинационных схем на логических элементах…..... | |
| 5.3.1. | Логические элементы……………………………………………………….. | |
| 5.3.2. | Общий алгоритм построения комбинационных схем…………………….. | |
| 5.3.3. | Синтез КС в классическом базисе………………………………………….. | |
| 5.3.4. | Синтез КС в базисах «И-НЕ», «ИЛИ-НЕ»………………………………… | |
| 5.3.5. | Реализация КС в базисе Жегалкина………………………………………... | |
| 5.3.6. | Синтез составных КС……………………………………………………….. | |
| Заключение…………………………………………………………………. | ||
| Библиографический список……………………………………………… |
ПРЕДИСЛОВИЕ
В учебных планах подготовки дипломированных специалистов по специальности 220100 – «Вычислительные машины, комплексы, системы и сети» и направлению 552800 – «Информатика и вычислительная техника» дисциплины «Дискретная математика», «Введение в информатику и вычислительную технику», «Алгоритмические языки и программирование» входят в состав фундаментального цикла дисциплин, формирующих у студентов представление о базовых понятиях информатики и вычислительной техники как о предмете их дальнейшей профессиональной деятельности. Изучение указанных дисциплин и овладение навыками разработки и моделирования алгоритмов реализации арифметических и логических компьютерных операций, синтеза логических схем создает теоретическую базу для изложения таких дисциплин, как «Теория автоматов», «Организация ЭВМ и систем», «Микропроцессорные системы» и других специальных курсов.
В главах 1, 2, 3, подготовленных профессором В.И. Потаповым, изложены основы двоичной и десятичной компьютерной арифметики, алгоритмы выполнения арифметических операций в ЭВМ для двоичных чисел с фиксированной и плавающей запятой (точкой) и для двоично-десятичных чисел в D-кодах. Рассмотрены многочисленные методы ускоренного выполнения арифметических операций в ЭВМ в двоичной и в двоично-десятичной системе счисления.
Глава 4, подготовленная доцентом О.П. Шафеевой, посвящена вопросам разработки алгоритмических моделей выполнения арифметических операций и моделирования на ПЭВМ спроектированных алгоритмов.
В главе 5, подготовленной доцентом И.В. Червенчуком, рассматриваются фундаментальные вопросы математической логики и задачи синтеза комбинационных схем на логических элементах, а также свойства булевых функций и вопросы их минимизации известными в инженерной практике методами.
Учебное пособие иллюстрировано многочисленными примерами и содержит вопросы для самоконтроля.
В настоящей книге рассматриваются методы быстрого выполнения различных видов вычислений, рассказывается о реализации быстрых алгоритмов как в виде логических схем - математической модели реальных электронных микросхем, так и в виде компьютерных программ. Исследуются также вопросы о том, как измерить сложность того или иного вычислительного алгоритма и оценить время его работы на компьютере. Большая часть материала книги доступна всем, кто знаком лишь со школьным курсом математики, но и опытный читатель может найти в этой книге кое-что новое для себя.
Книга написана на основе лекций, которые автор в разное время читал учащимся физико-математической Школы им. А. Н. Колмогорова при МГУ, на Малом и Большом мехмате, а также на факультетах информационной безопасности и информатики РГГУ.
Быстрое деление многочленов.
Здесь будет показано, что деление можно выполнять с той же по порядку сложностью, что и умножение. Впервые это было сделано немецким математиком Фолкером Штрассеном в 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
Ниже можно купить эту книгу по лучшей цене со скидкой с доставкой по всей России.
