Интерпретация положительных и отрицательных чисел

⇐ ПредыдущаяСтр 2 из 6Следующая ⇒

В кольце вычетов невозможно определить порядок, согласованный с операциями (т.е. так, чтобы, к примеру, сумма двух положительных чисел была положительной). Таким образом, в компьютере нет, строго говоря, положительных и отрицательных целых чисел, поскольку компьютерные целые числа - это на самом деле элементы кольца вычетов. Выбирая либо неотрицательную, либо симметричную систему остатков, можно интерпретировать эти числа либо как неотрицательные в диапазоне от нуля до m-1, либо как отрицательные и положительные числа в диапазоне от -k до k, где k - целая часть от деления m на 2.

В программировании симметричная система остатков более популярна, поскольку трудно обойтись без отрицательных чисел. При этом следует понимать, что сумма двух положительных чисел может оказаться отрицательной, или, наоборот, сумма двух отрицательных чисел - положительной. Иногда в программировании такую ситуацию называют переполнением. Привычные свойства целочисленных операций в компьютере выполняются лишь для небольших чисел, когда результат операции не превосходит числа m = 2³². В случае целочисленных переменных переполнение не является экстраординарной ситуацией и не приводит к аппаратным ошибкам или прерываниям. (Это, кстати, отличает компьютерные целые числа от вещественных.) Переполнение - совершенно нормальная ситуация, если вспомнить, что компьютер работает с элементами кольца вычетов по модулю m, а не с настоящими целыми числами.

Следует также отметить, что симметричная система остатков кольца Z_m в случае четного m (а m для компьютера равно 2³², т.е. четно) не вполне симметрична. Поскольку ноль не имеет знака, то число положительных остатков не может равняться числу отрицательных.

Какой остаток выбрать в классе эквивалентности числа k = m/2? Для этого элемента выполняется непривычное с точки зрения школьной математики равенство

k+k

0 (mod m),

т.е.

-k (mod m)

Как отрицательный остаток -k, так и положительный k в равной мере подходят для представления этого класса эквивалентности. По традиции выбирается отрицательный остаток. Таким образом, в компьютере количество отрицательных целых чисел на единицу больше, чем количество положительных. Так как m = 2³² = 4294967296, то k = 2³¹ = 2147483648, и симметричная система остатков состоит из элементов

-2147483648, -2147483647, ..., -2, -1, 0, 1, 2, ..., 2147483647.

В двоичном представлении старший разряд у отрицательных целых чисел равен единице, у положительных - нулю. Двоичные разряды представления целого числа в программировании нумеруют от 0 до 31 справа налево. Старший разряд имеет номер 31 и часто называется знаковым разрядом. Таким образом, знаковый разряд равен единице у всех отрицательных чисел и нулю у неотрицательных. Двоичное представление максимального по абсолютной величине отрицательного числа k состоит из единицы и тридцати одного нуля:

-2147483648₁₀ = 10000000000000000000000000000000₂

Двоичное представление числа -1 состоит из тридцати двух единиц:

-1₁₀ = 11111111111111111111111111111111₂

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

2147483647₁₀ = 01111111111111111111111111111111₂

Следует отметить, что в программировании часто используют также короткие целые числа, двоичная запись которых занимает восемь разрядов, т.е. один байт, или шестнадцать разрядов, т.е. два байта. Работа с такими короткими целыми числами поддерживается на аппаратном уровне. В языке Си однобайтовым целым числам соответствует тип char (тип char в Си - это именно целые числа, символы представляются их целочисленными кодами), двухбайтовым - тип short. Однобайтовые целые числа - это элементы кольца вычетов Z_m, где m = 2⁸ = 256. Симметричная система остатков в этом случае состоит из элементов

-128, -127, ..., -2, -1, 0, 1, 2, ..., 127.

В случае двухбайтовых целых чисел (тип short) m = 2¹⁶ = 65536, а симметричная система остатков состоит из элементов

-32768, -32767, ..., -2, -1, 0, 1, 2, ..., 32767.

Вещественные переменные

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

r = ±2^e* m

Представление числа состоит из трех элементов:

знак числа - плюс или минус. Под знак числа отводится один бит в двоичном представлении, он располагается в старшем, т.е. знаковом разряде. Единица соответствует знаку минус, т.е. отрицательному числу, ноль - знаку плюс. У нуля знаковый разряд также нулевой;
показатель степени e, его называют порядком или экспонентой. Экспонента указывает степень двойки, на которую домножается число. Экспонента может быть как положительной, так и отрицательной (для чисел, меньших единицы). Под экспоненту отводится фиксированное число двоичных разрядов, обычно восемь или одиннадцать, расположенных в старшей части двоичного представления числа, сразу вслед за знаковым разрядом;
мантисса m представляет собой фиксированное количество разрядов двоичной записи вещественного числа в диапазоне от 1 до 2:

4. 1

m<2

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

В языке Си вещественным числам соответствуют типы float и double. Элемент типа float занимает 4 байта, в которых один бит отводится под знак, восемь - под порядок, остальные 23 - под мантиссу (на самом деле, в мантиссе 24 разряда, но старший разряд всегда равен единице, поэтому хранить его не нужно). Тип double занимает 8 байтов, в них один разряд отводится под знак, 11 - под порядок, остальные 52 - под мантиссу. На самом деле в мантиссе 53 разряда, но старший всегда равен единице и поэтому не хранится. Поскольку порядок может быть положительным и отрицательным, в двоичном коде он хранится в смещенном виде: к нему прибавляется константа, равная абсолютной величине максимального по модулю отрицательного порядка. В случае типа float она равна 127, в случае double - 1023. Таким образом, максимальный по модулю отрицательный порядок представляется нулевым кодом.

Основным типом является тип double, именно он наиболее естественен для компьютера. В программировании следует по возможности избегать типа float, так как его точность недостаточна, а процессор все равно при выполнении операций преобразует его в тип double. (Один из немногих случаев, где применение типа float оправдано, - трехмерная компьютерная графика.)

Несколько примеров представления вещественных чисел в плавающей форме:

1.0 = +2⁰*1.0

Здесь порядок равен 0, мантисса - 1. В двоичном коде мантисса состоит из одних нулей, так как старший разряд мантиссы (всегда единичный) в коде отсутствует. Порядок хранится в двоичном коде в смещенном виде, он равен 127 в случае float и 1023 в случае double;

3.5 = +2¹*1.75

Порядок равен единице, мантисса состоит из трех единиц, из которых в двоичном коде хранятся две: 1100...0; смещенный порядок равен 128 для float и 1024 для double;

0.625 = +2^-1*1.25

Порядок отрицательный и равен -1, дробная часть мантиссы равна 0100...0; смещенный порядок равен 126 для float и 1022 для double;

100.0 = +2⁶*1.5625

Порядок равен шести, дробная часть мантиссы равна 100100...0; смещенный порядок равен 133 для float и 1029 для double.

При выполнении сложения двух положительных плавающих чисел происходят следующие действия:

выравнивание порядков. Определяется число с меньшим порядком. Затем последовательно его порядок увеличивается на единицу, а мантисса делится на 2, пока порядки двух чисел не сравняются. Аппаратно деление на 2 соответствует сдвигу двоичного кода мантиссы вправо, так что эта операция выполняется быстро. При сдвигах правые разряды теряются, из-за этого может произойти потеря точности (в случае, когда правые разряды ненулевые);
сложение мантисс;
нормализация: если мантисса результата стала равна или превысила двойку, то порядок увеличивается на единицу, а мантисса делится на 2. В результате этого мантисса попадает в интервал 1 m<2. При этом возможна потеря точности, а также переполнение, когда порядок превышает максимально возможную величину.

Вычитание производится аналогичным образом. При умножении порядки складываются, а мантиссы перемножаются как целые числа, после чего у результата правые разряды отбрасываются.

Машинный эпсилон

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

a+b = a при b

Более того, для сложения не выполняется закон ассоциативности:

a+(b+c)

(a+b)+c

Действительно, пусть ε - максимальное плавающее число среди чисел, удовлетворяющих условию

1.0+ε = 1.0

(приведенные выше рассуждения показывают, что такие числа существуют). Тогда

(1.0+ε)+ε

1.0+(ε+ε)

поскольку левая часть неравенства равна единице, а правая строго больше единицы (это следует из максимальности числа ε).

Число ε часто называют машинным эпсилоном или, чуть менее корректно, машинным нулем, поскольку при прибавлении к единице оно ведет себя как ноль. Величина машинного эпсилона характеризует точность операций компьютера. Она примерно одинакова для всех современных компьютеров: большинство процессоров работают с восьмибайтовыми плавающими числами (тип double в Си), а арифметика плавающих чисел подчиняется строгим международным стандартам.

Оценим величину машинного эпсилона для типа double. Число 1.0 записывается в плавающей форме как

1.0 = +2⁰*1.0.

Порядок плавающего числа 1.0 равен нулю. При сложении 1.0 с числом ε производится выравнивание порядка путем многократного сдвига мантиссы числа ε вправо и увеличения его порядка на 1. Поскольку все разряды числа ε должны в результате выйти за пределы разрядной сетки, должно быть выполнено 53 сдвига. Порядок числа ε после этого должен стать равным порядку числа 1.0, т.е. нулю. Следовательно, изначально порядок числа ε должен быть равным -53:

ε = 2^-53*m

где m - число в диапазоне от единицы до двух. Таким образом, величина машинного эпсилона составляет примерно

2^-53

10^-16

Приблизительно точность вычислений составляет 16 десятичных цифр. (Это также можно оценить следующим образом: 53 двоичных разряда составляют примерно 15.95 десятичных, поскольку 53/log₂10 53/3.321928 15.95.)

В случае четырехбайтовых плавающих чисел (тип float языка Си) точность вычислений составляет примерно 7 десятичных цифр. Это очень мало, поэтому тип float чрезвычайно редко применяется на практике. К тому же процессор сконструирован для работы с восьмибайтовыми вещественными числами, а при работе с четырехбайтовыми он все равно сначала приводит их к восьмибайтовому типу. В программировании следует избегать типа float и всегда пользоваться типом double.

Некоторые процессоры применяют внутреннее представление плавающих чисел с большим количеством разрядов мантиссы. Например, процессор Intel использует 80-битовое (десятибайтовое) представление. Поэтому точность вычислений, которые не записывают промежуточные результаты в память, может быть несколько выше указанных оценок.

Кроме потери точности, при операциях с вещественными числами могут происходить и другие неприятности:

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

Кроме того, некорректной операцией является деление на ноль. В отличие от операций с целыми числами, переполнение и исчезновение порядка считаются ошибочными ситуациями и приводят к аппаратному прерыванию работы процессора. Программист может задать реакцию на прерывание - либо аварийное завершение программы, либо, например, при переполнении присваивать результату специальное значение плюс или минус бесконечность, а при исчезновении порядка - ноль. Заметим, что среди двоичных кодов, представляющих плавающие числа, имеется несколько специальных значений. Перечислим некоторые из них:

бесконечно большое число - это плавающее число с очень большим положительным порядком и, таким образом, очень большое по абсолютной величине. Оно может иметь знак плюс или минус;
бесконечно малое, или денормализованное, число - это ненулевое плавающее число с очень большим отрицательным порядком (т.е. очень маленькое по абсолютной величине);
Not a Number, или NaN - двоичный код, который не является корректным представлением какого-либо вещественного числа.

Любые операции с константой NaN приводят к прерыванию, поэтому она удобна при отладке программы - ею перед началом работы программы инициализируются значения всех вещественных переменных. Если в результате ошибки программиста при вычислении выражения используется переменная, которой не было присвоено никакого значения, то происходит прерывание из-за операции со значением NaN и ошибка быстро отслеживается. К сожалению, в случае целых чисел такой константы нет: любой двоичный код представляет некоторое целое число.

Запись вещественных констант

Вещественные константы записываются в двух формах - с фиксированной десятичной точкой или в экспоненциальном виде. В первом случае точка используется для разделения целой и дробной частей константы. Как целая, так и дробная части могут отсутствовать. Примеры:

1.2, 0.725, 1., .35, 0.

В трех последних случаях отсутствует либо дробная, либо целая часть. Десятичная точка должна обязательно присутствовать, иначе константа считается целой. Отметим, что в программировании именно точка, а не запятая, используется для отделении дробной части; запятая обычно служит для разделения элементов списка.

Экспоненциальная форма записи вещественной константы содержит знак, мантиссу и десятичный порядок (экспоненту). Мантисса - это любая положительная вещественная константа в форме с фиксированной точкой или целая константа. Порядок указывает степень числа 10, на которую домножается мантисса. Порядок отделяется от мантиссы буквой "e" (от слова exponent), она может быть прописной или строчной. Порядок может иметь знак плюс или минус, в случае положительного порядка знак плюс можно опускать. Примеры:

1.5e+6 константа эквивалентна 1500000.01e-4 константа эквивалентна 0.0001-.75E3 константа эквивалентна -750.0

Символьные переменные

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

Конечно, в памяти компьютера никаких символов не содержится. Символы представляются их целочисленными кодами в некоторой фиксированной кодировке. Кодировка определяется тремя параметрами:

диапазоном значений кодов. Например, самая распространенная в мире кодировка ASCII (от слов American Standard Code of Information Interchange - Американский стандартный код обмена информацией) имеет диапазон значений кодов от 0 до 127, т.е. требует семь бит на символ. Большинство современных кодировок имеют диапазон кодов от 0 до 255, т.е. один байт на символ. Наконец, сейчас во всем мире осуществляется переход на кодировку Unicode, которая использует коды в диапазоне от 0 до 65535, т.е. 2 байта на символ;
множеством изображаемых символов. Например, кодировка ASCII содержит буквы латинского алфавита, в западноевропейской кодировке к символам ASCII добавлены буквы с умлаутами и акцентами, дополнительные знаки препинания, в частности, испанские перевернутые вопросительные и восклицательные знаки, и другие символы европейских языков, основанных на латинской графике. Любая из русских кодировок содержит кириллицу;
отображением множества кодов на множество символов. Например, русские кодировки КОИ-8 (Код обмена информацией восьмибитовый) и "Windows CP-1251", традиционно используемые в операционных системах Unix и MS Windows, имеют один и тот же диапазон кодов и один и тот же набор символов, но отображения их различны (одни и те же символы имеют разные коды в кодировках КОИ-8 и Windows).

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

кодировка КОИ-8 (это наиболее старый стандарт, принятый еще в конце 70-х годов XX века). КОИ-8 в основном используется в системе Unix и до недавнего времени была стандартом де-факто для русскоязычной электронной почты. Последнее время, однако, все чаще в электронной почте используют кодировку Windows;
так называемая альтернативная кодировка CP-866, которая используется в системе MS DOS. Она не удовлетворяет некоторым требованиям международных стандартов - например, ряд русских букв совпадает с кодами символов, используемых для управления передачей по линии. Альтернативная кодировка постепенно уходит в прошлое вместе с системой DOS;
кодировка Windows CP-1251, которая появилась значительно позже кодировки КОИ-8, но создатели русской версии Windows не захотели воспользоваться КОИ-8 (по-видимому, из-за того, что коды русских букв в КОИ-8 не упорядочены в соответствии с алфавитом; в CP-1251 коды русских букв упорядочены, за исключением буквы е). В связи с распространением операционной системы Windows, кодировка Windows получает все большее распространение;
кодировка, используемая в компьютерах Apple Macintosh.

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

С повсеместным переходом на кодировку Unicode все проблемы такого рода должны исчезнуть. Кодировка Unicode включает символы алфавитов всех европейских стран и кириллицу. К сожалению, большинство существующих компьютерных программ приспособлено к представлению одного символа в виде одного байта. Поэтому в настоящее время часто используется промежуточное решение: компьютерные программы работают с внутренним представлением символов в кодировке Unicode (такое решение принято в языках Java и C#). При записи в файл символы Unicode приводятся к однобайтовой кодировке в соответствии с текущей языковой установкой. При этом, конечно, часть символов теряется - например, в кодировке Windows невозможно одновременно записать русские буквы и немецкие умлауты, поскольку умлауты в западно-европейской кодировке имеют те же коды, что и русские буквы в русской кодировке.

Дата добавления: 2018-05-30; просмотров: 522; Мы поможем в написании вашей работы!

Поделиться с друзьями:

⇐ Предыдущая 123 4 5 6 Следующая ⇒

Мы поможем в написании ваших работ!