ПОД (пособие) (1184372), страница 55
Текст из файла (страница 55)
Еслидиапазоны чисел, представимых в арифметике с фиксированной запятой и с плавающейзапятой, соизмеримы, то числа с фиксированной запятой могут более точно представлять(кодировать) величины, так как свободны от часто необходимой для чисел с плавающейзапятой операции округления. При машинной реализации такая операция обычновыполняется в устройстве-предшественнике (например, сумматор) с высокой точностью(большой разрядностью), а затем отсылается в устройство-преемник (например, регистр) сучётом заданной (например, декларированной в описаниях типов и структур данных)точности или с сохранением всех значащих разрядов.
Таким образом, копированиенепосредственного результата операции происходит либо с помощью операции округления,либо с помощью операции усечения.Эти две основные операции (кроме арифметических операций) вводятся следующимобразом:усечение, отбрасывание цифр числа до определённого разряда, например, доближайшего, меньшего целого числа и т.п.;184округление, усечение с коррекцией числа по определённым правилам, например, дочисла кратного заданному числу, до ближайшего целого и т.п.Пример.
Операция взятия целой части числа x (функция Антье - [x] или int(x)) операция усечения, [2.65]=2, [—1.999]=—2. Операция взятия целой части числа x+0.5вместо значения числа х есть округление {x} до ближайшего целого, {1.05}={0.91}=1,{2.61}=[2.6+0.5]=3.ДополнениеЦелочисленные переменныеТип целое число является основным для любого алгоритмического языка. Связано это стем, что содержимое ячейки памяти или регистра процессора можно рассматривать какцелое число. Адреса элементов памяти также представляют собой целые числа, с ихпомощью записываются машинные команды и т.д.
Символы представляются в компьютерецелыми числами - их кодами в некоторой кодировке. Изображения также задаютсямассивами целых чисел: для каждой точки цветного изображения хранятся интенсивностиее красной, зеленой и синей составляющей (в большинстве случаев - в диапазоне от 0 до255).
Как говорят математики, целые числа даны свыше, все остальное сконструировал изних человек.Общепринятый в программировании термин целое число или целочисленная переменная,строго говоря, не вполне корректен. Целых чисел бесконечно много, десятичная илидвоичная запись целого числа может быть сколь угодно длинной и не помещаться в областипамяти, отведенной под одну переменную.
Целая переменная в компьютере может хранитьлишь ограниченное множество целых чисел в некотором интервале. В современныхкомпьютерах под целую переменную отводится 4 байта, т.е. 32 двоичных разряда. Онаможет хранить числа от нуля до 2 в 32-й степени минус 1. Таким образом, максимальноецелое число, которое может храниться в целочисленной переменной, равно232 - 1 = 4294967295Сложение и умножение значений целых переменных выполняется следующим образом:сначала производится арифметическая операция, затем старшие разряды результата,вышедшие за границу тридцати двух двоичных разрядов (т.е. четырех байтов),отбрасываются. Определенные таким образом операции удовлетворяют традиционнымзаконам коммутативности, ассоциативности и дистрибутивности:a+b = b+a, ab = ba(a+b) + c = a+(b+c), (ab)c = a(bc)a(b+c) = ab+acКольцо вычетов по модулю mЦелочисленный тип компьютера в точности соответствует важнейшему понятиюматематики - понятию кольца вычетов по модулю m.
В качестве m выступает число 232 =4294967296. В математике кольцо Zm определяется следующим образом. Все множествоцелых чисел Z разбивается на m классов, которые называются классами эквивалентности.Каждый класс содержит числа, попарная разность которых делится на m. Первый класссодержит числа{...,-2m,-m,0,m,2m, ...}второй{..., -2m+1, -m+1, 1, m+1, 2m+1, ...}последний{..., -m-1, -1, m-1, 2m-1, 3m-1, ...}185Элементами кольца Zm являются классы эквивалентности. Их ровно m, так что, в отличиеот множества целых чисел Z, кольцо Zm содержит конечное число элементов.
Операции склассами выполняются следующим образом: надо взять по одному представителю изкаждого класса, произвести операцию и определить, в какой класс попадает результат. Этоткласс и будет результатом операции. Легко показать, что он не зависит от выборапредставителей.Все числа, принадлежащие одному классу эквивалентности, имеют один и тот же остатокпри делении на m. Таким образом, класс эквивалентности однозначно определяетсяостатком от деления на m. Традиционно остаток выбирается неотрицательным, в диапазонеот 0 до m -1. Остатки используют для обозначения классов, при этом используютсяквадратные скобки. Так, выражение [5] обозначает класс эквивалентности, состоящий извсех чисел, остатки которых при делении на m равны пяти.
Все кольцо Zm состоит изэлементов [0],[1],[2], ...,[m-1], например, кольцо Z5 состоит из элементов [0],[1],[2],[3],[4].В элементарной школьной математике результат операции остатка от деления традиционносчитается неотрицательным. Операция нахождения остатка будет обозначаться знакомпроцента %, как в языке Си. Тогда, к примеру,3%5 = 3,17%5 = 2,(-3)%5 = 2,(-17)%5 = 3.Отсюда видно, что в школьной математике не выполняется равенство (-a)%b = -(a%b),т.е. операции изменения знака и нахождения остатка не перестановочны (наматематическом языке, не коммутируют друг с другом). В компьютере операциянахождения остатка от деления для отрицательных чисел определяется иначе, ее результатможет быть отрицательным.
В приведенных примерах результаты будут следующими:3%5 = 3,17%5 = 2,(-3)%5 = -3,(-17)%5 = -2.При делении на положительное число знак остатка совпадает со знаком делимого. Притаком определении тождество (-a)%b = a%(-b) = -(a%b) справедливо. Это позволяет вомногих алгоритмах не следить за знаками (так же, как в тригонометрии формулы,выведенные для углов, меньших 90 градусов, автоматически оказываются справедливымидля любых углов).Вернемся к рассмотрению кольца Zm. Выберем по одному представителю из каждогокласса эквивалентности, которые составляют множество Zm.
Систему таких представителейназывают системой остатков. Традиционно рассматривают две системы остатков:неотрицательную систему и симметричную систему. Неотрицательная система остатковсостоит из элементов0,1,2,3, ...m-1.Очень удобна также симметричная система остатков, состоящая из отрицательных инеотрицательных чисел, не превосходящих m/2 по абсолютной величине. Пустьk = целая часть(m/2)тогда симметричная система остатков при нечетном m состоит из элементов-k, -k+1, ..., -1, 0, 1, ..., k-1, k,186а при четном m - из элементов-k, -k+1, ..., -1, 0, 1, ..., k-1.Например, при m = 5 симметричная система остатков состоит из элементов-2, -1, 0, 1, 2.Кольцо Zm можно представлять состоящим из элементов, принадлежащих выбраннойсистеме остатков.
Арифметические операции определяются следующим образом: надовзять два остатка, произвести над ними операцию как над обычными целыми числами ивыбрать тот остаток, которой лежит в том же классе эквивалентности, что и результатоперации. Например, для симметричной системы остатков множества Z5 имеем:1+1 = 2,1+2 = -2,1+(-2) = -1, 1+(-1) = 0,(-2)+2 = 0, (-2)+(-2) = 1.Интерпретация положительных и отрицательных чиселВ кольце вычетов невозможно определить порядок, согласованный с операциями (т.е. так,чтобы, к примеру, сумма двух положительных чисел была положительной). Таким образом,в компьютере нет, строго говоря, положительных и отрицательных целых чисел, посколькукомпьютерные целые числа - это на самом деле элементы кольца вычетов.
Выбирая либонеотрицательную, либо симметричную систему остатков, можно интерпретировать этичисла либо как неотрицательные в диапазоне от нуля до m-1, либо как отрицательные иположительные числа в диапазоне от -k до k, где k - целая часть от деления m на 2.В программировании симметричная система остатков более популярна, поскольку труднообойтись без отрицательных чисел. При этом следует понимать, что сумма двухположительных чисел может оказаться отрицательной, или, наоборот, сумма двухотрицательных чисел - положительной.
Иногда в программировании такую ситуациюназывают переполнением. Привычные свойства целочисленных операций в компьютеревыполняются лишь для небольших чисел, когда результат операции не превосходит числаm = 232. В случае целочисленных переменных переполнение не является экстраординарнойситуацией и не приводит к аппаратным ошибкам или прерываниям.
(Это, кстати, отличаеткомпьютерные целые числа от вещественных.) Переполнение - совершенно нормальнаяситуация, если вспомнить, что компьютер работает с элементами кольца вычетов помодулю m, а не с настоящими целыми числами.Следует также отметить, что симметричная система остатков кольца Zm в случае четного m(а m для компьютера равно 232, т.е. четно) не вполне симметрична. Поскольку ноль неимеет знака, то число положительных остатков не может равняться числу отрицательных.Какой остаток выбрать в классе эквивалентности числа k = m/2? Для этого элементавыполняется непривычное с точки зрения школьной математики равенствоk+k 0 (mod m), т.е.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
