Особенности представления чисел в ЭВМ

Как уже отмечалось ранее, множествам целых $$\mathbb{Z}$$ и действительных $$\mathbb{R}$$ чисел в большинстве языков программирования соответствуют их машинные аналоги. В случае языка Java используемые в программах переменные величины и константы типов int и double принимают значения из множеств $$\mathbb{Z}_M$$ и $$\mathbb{R}_M$$ соответственно. В этом параграфе мы разберемся с тем, как именно устроены эти множества, и каковы последствия того, что программы оперируют не с настоящими числами, а с элементами указанных множеств. Однако сначала — некоторые напоминания об информации вообще и ее представлении в ЭВМ.

Представление информации в компьютере

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

Единицей измерения информации является бит (BInary digiT) — именно такое количество информации содержится в ответе на вопрос: нуль или один? Более крупными единицами измерения информации являются байт, килобайт (Kbyte), мегабайт (Mbyte), гигабайт (Gbyte) и терабайт (Tbyte). Один байт (byte) состоит из восьми бит, а каждая последующая величина больше предыдущей в 1024 раза.

Байта достаточно для хранения 256 различных значений, что позволяет размещать в нем любой из алфавитно-цифровых символов, если только мы можем ограничиться языками с небольшими алфавитами типа русского или английского. Первые 128 символов (занимающие семь младших бит) стандартизированы с помощью кодировки ASCII (American Standart Code for Information Interchange). Хуже обстоит дело с кодировками русского текста (символы русского алфавита расположены во второй половине таблицы из 256 символов) — их несколько, а наиболее распространенные из них сейчас две — Windows-1251 и KOI8-R.

Для кодирования всех возможных символов, используемых народами мира, одного байта мало — необходимо использовать два последовательных (стандарт Unicode). Именно так и поступают при хранении символьных ( char ) значений в языке Java.

Полезно знать, что $$2^{10} = 1024 \approx 1000 = 10^3$$. Учитывая, что в книге среднего размера около 300000 букв, легко подсчитать, что, даже не используя никаких средств сжатия информации, на жестком диске современного персонального компьютера емкостью в 20 гигабайт можно разместить большую библиотеку из почти 70000 книг.

Целые числа

К целочисленным типам в языке Java относятся byte, short, int и long. Для хранения значений этих типов на любом компьютере отводится один, два, четыре и восемь байт соответственно. При этом применяется представление чисел в так называемом двоичном дополнительном коде.

Напомним, что используемая нами обычная система счисления является позиционной с основанием 10. Это значит, что в ней все натуральные числа представляются с помощью десяти цифр (от нуля до девяти включительно), а значение каждой из цифр числа зависит от позиции: самая правая цифра означает число единиц ( $$10^0$$ ), вторая — десятков ( $$10^1$$ ), третья — сотен ( $$10^2$$ ) и так далее.

В $$p$$ -ичной системе счисления все точно также, только число 10 в предыдущем абзаце нужно всюду заменить на $$p$$. Наряду с двоичной системой, в которой только две цифры (0 и 1), в информатике часто применяются восьмеричная с цифрами от нуля до 7 и шестнадцатеричная. В последнем случае в качестве цифр от десяти до пятнадцати используются буквы от $$A$$ до $$F$$ соответственно.

При записи положительных целых чисел в системе счисления с основанием $$p$$ (на компьютере $$p=2$$ ) все их множество оказывается состоящим из элементов вида$$d = \alpha_{n-1} p^{n-1} + \alpha_{n-2} p^{n-2} + \ldots + \alpha_0,$$ где величины $$\alpha_i$$ для всех $$i$$ из диапазона от $$n-1$$ до нуля — это цифры $$n$$ -значного числа $$d$$ в $$p$$ -ичной системе счисления.

Перейдем теперь к вопросу представления отрицательных чисел. Для определенности рассмотрим тип byte, в котором любое число занимает ровно восемь бит. Из записи в двоичной системе счисления равенства $$(-1)+1=0$$ легко найти, какой вид должно иметь неизвестное нам пока двоичное представление xxxxxxxx числа $$-1$$:

xxxxxxxx + 00000001 = 00000000

Ясно, что на месте символов xxxxxxxx должно быть расположено число 11111111. Правильным результатом при этом, конечно, следовало бы считать 100000000, а не 00000000, но ведь мы имеем дело с типом byte и, так как результат обязан разместиться в байте, единица "исчезает".

Итак, число $$-1$$ должно кодироваться как 11111111. Дальнейшее уже совсем просто: для получения $$-2$$ нужно $$-1$$ уменьшить на единицу, что даст 11111110 ; число $$-3$$ представляется как 11111101 и т.д.

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

Легко видеть, что при этом самым маленьким отрицательным числом, которое принадлежит типу byte, является число $$-128$$ (двоичное представление 10000000 ), а самым большим — число 127 (представление 01111111 ). Все представимые числа (а их 256) в данном случае могут быть получены как пересечение двух множеств: множества $$\mathbb{Z}$$ всех целых чисел и отрезка $$[-128, 127]$$. Интересным является следующее наблюдение: если число 01111111 увеличить на единицу, то получится 10000000, что означает следующее: $$127 + 1 = -128\;$$!

Итак, множество элементов типа byte можно представлять себе в виде свернутого в кольцо отрезка $$[-128, 127]$$. Принципиально ничего не меняется и для типов short, int и long — увеличивается только длина отрезка, который вырезается из действительной прямой перед сворачиванием его в кольцо. Минимальные и максимальные представимые значения для каждого из этих типов в языке Java определены, как значения констант MIN_VALUE и MAX_VALUE в классах java.lang.Short, java.lang.Integer и java.lang.Long соответственно.

То, что для элементов множества $$\mathbb{Z}_M$$, являющегося машинным аналогом $$\mathbb{Z}$$, нарушено фундаментальное свойство целых чисел $$x + 1 > x$$, способно привести к различным невероятным на первый взгляд результатам, однако гораздо более странные вещи происходят при работе с вещественными числами.

Вещественные числа

Обсуждаемые в данной секции вопросы значительно более полно рассмотрены в четвертой главе классической книги Кнута [7].

Для представления вещественных чисел в языке Java используют переменные и константы типов float и double. Величины первого из них занимают четыре байта, а второго — восемь.

В отличие от множества целых чисел $$\mathbb{Z}$$ вещественные числа $$\mathbb{R}$$ обладают свойством полноты: между любыми двумя различными числами всегда найдется отличное от них третье. Понятно, что любой из способов представления бесконечного множества вещественных чисел с помощью некоторого конечного множества $$\mathbb{R}_M$$ не даст возможности сохранить свойство полноты. Наиболее распространенным способом реализации вещественных чисел на ЭВМ является использование чисел с плавающей точкой. При этом множество $$\mathbb{R}_M$$ оказывается состоящим из элементов вида

где целые числа $$\alpha_i$$ для всех $$i$$ из диапазона от 1 до $$n$$ удовлетворяют соотношению $$0 \leqslant \alpha_i \leqslant p - 1$$, а величина $$e$$ лежит в диапазоне от $$L$$ до $$U$$ ( $$L \leqslant e \leqslant U$$ ). Число $$p$$ является при этом основанием системы счисления (чаще всего это 2), константа $$n$$ задает точность представления чисел (для типа double она больше, чем для float ), а диапазон $$[L,U]$$ определяет область значений экспоненты (для типа double он также больше, чем для float ).

Число $$\pm (\frac{\alpha_1}{p}+\frac{\alpha_2}{p^2}+\ldots+ \frac{\alpha_n}{p^n})$$ принято называть мантиссой числа $$f$$ с плавающей точкой. Часто требуют, чтобы для всех чисел $$f \ne 0$$ величина $$\alpha_1$$ была ненулевой. Такие числа с плавающей точкой называют нормализованными.

В языке Java для кодирования величин типов float и double также используют числа с плавающей точкой. При этом часть из имеющегося множества бит используют для размещения экспоненты $$e$$, а остальные биты — для размещения мантиссы.

Для того чтобы хорошо понять, что же представляет из себя множество $$\mathbb{R}_M$$ нормализованных чисел с плавающей точкой, полезно изобразить его на числовой прямой для случая небольших $$n$$, $$L$$ и $$U$$. Подобная задача приведена в конце параграфа. Сейчас же нам будет достаточно весьма качественного описания этого множества.

Так как $$\mathbb{R}_M$$ симметрично относительно начала координат, то можно разобраться только с неотрицательными числами. Нуль, конечно же, принадлежит искомому множеству. Ближайшая к нулю следующая точка получается при $$\alpha_1 = 1$$, $$\alpha_2 = \alpha_3 = \ldots = \alpha_n = 0$$ и $$e=L$$. Это число для чисел типов float и double определено, как MIN_VALUE в классах java.lang.Float и java.lang.Double соответственно.

Правее располагается множество точек, следующих друг за другом с шагом $$2^{L-n}$$. Затем шаг увеличивается. Потом еще. И еще. При $$e=U$$ расстояние между двумя соседними точками множества $$\mathbb{R}_M$$ достигает $$2^{U-n}$$. Самая правая точка множества получается при $$\alpha_1 = \alpha_2 = \ldots = \alpha_n = 1$$ и $$e=U$$. Для типов float и double это число определено, как MAX_VALUE в классах java.lang.Float и java.lang.Double.

Кроме перечисленных (и симметричных им отрицательных) значений в результате выполнения некоторых операций могут получиться также следующие особые значения: плюс бесконечность ( POSITIVE\_INFINITY ), минус бесконечность ( NEGATIVE\_INFINITY ), минус ноль и не число ( NaN ). Например, при делении единицы на минус ноль получается минус бесконечность.

Описанные особенности множества машинных вещественных чисел $$\mathbb{R}_M$$ приводят к тому, что не для всех его элементов верны следующие соотношения, всегда справедливые для множества настоящих вещественных чисел $$\mathbb{R}$$:

Приведем несколько примеров, иллюстрирующих эти особенности множества $$\mathbb{R}_M$$.

Задача 4.1. Предъявите действительное (типа double ) число $$x$$ такое, что $$x + 1 = x$$, а $$(x\cdot 2) / 2 \ne x$$. Воспользуйтесь тем, что класс java.lang.Double определяет константу MAX_VALUE.

Текст программы

public class DblMaxVal {
    public static void main(String[] args) {    
        double x = Double.MAX_VALUE;
        double y = x + 1.0;

        if (x == y) {
            Xterm.print("Для числа ");
            Xterm.print("x = " + x, Xterm.Blue);
            Xterm.print(" величины x и (x+1) ");
            Xterm.print("равны!\n", Xterm.Red);
        }
	
        y = 2.0 * x;
        double z = y / 2.0;

        if (x != z) {
            Xterm.print("Для числа ");
            Xterm.print("x = " + x, Xterm.Blue);
            Xterm.print(" величины x и (2.0*x)/2.0 ");
            Xterm.print("различны\n", Xterm.Red);
            Xterm.print("и равны соответственно");
            Xterm.print(" " + x, Xterm.Red);
            Xterm.print(" и");
            Xterm.print(" " + z + "\n", Xterm.Red);
        }
    }
}

Задача 4.2.Предъявите такие действительные (типа double ) числа $$a$$, $$b$$ и $$c$$ такие, что $$a+(b+c) \ne (a+b)+c$$.

Достаточно вспомнить, что точки множества $$\mathbb{R}_M$$ расположены на числовой прямой неравномерно.

Текст программы

public class DblNoAssociative {
    public static void main(String[] args) {    
        double x = 1.0e-16;
	
        double y =  1.  + (x  +  x);
        double z = (1.  +  x) +  x ;

        if (y != z) {
            Xterm.print("Для числа ");
            Xterm.print("x = " + x, Xterm.Blue);
            Xterm.print(" величины 1.+(x+x) и (1.+x)+x ");
            Xterm.print("различны\n", Xterm.Red);
            Xterm.print("и равны соответственно");
            Xterm.print(" " + y, Xterm.Red);
            Xterm.print(" и");
            Xterm.print(" " + z + "\n", Xterm.Red);
        }
    }
}

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

Задача Напишите программу, вводящую действительные коэффициенты $$a$$, $$b$$ и $$c$$ квадратного уравнения $$a x^2 + b x + c = 0$$ с положительным дискриминантом, находящую оба корня этого уравнения.

Вот вполне естественное решение этой задачи, которое может быть написано любым человеком, обладающим минимальными знаниями языка Java.

Текст программы

public class SquareEquation {
    public static void main(String[] args) throws Exception {    
        double a = Xterm.inputDouble("Введите число a -> ");
        double b = Xterm.inputDouble("Введите число b -> ");
        double c = Xterm.inputDouble("Введите число c -> ");

        if (a == 0.) {
            Xterm.println("Уравнение не квадратное", Xterm.Red);
            System.exit(0);
        }

        if (b*b - 4.*a*c <= 0.) {
            Xterm.println("Дискриминант неположителен", Xterm.Red);
            return;
        }

        double x1 = ( -b - Math.sqrt(b*b - 4.*a*c) ) / (2.*a);
        double x2 = ( -b + Math.sqrt(b*b - 4.*a*c) ) / (2.*a);

        Xterm.println("Корни уравнения:");
        Xterm.println("x1 = " + x1, Xterm.Blue);
        Xterm.println("x2 = " + x2, Xterm.Blue);
    }
}

Для извлечения квадратного корня здесь используется метод sqrt класса Math. Вызов метода System.exit и применение оператора return, которые в теле метода main почти эквивалентны и приводят к немедленному завершению выполнения программы, позволяет обойтись без ветви else оператора if-else. Остальная часть программы комментариев не требует.

Попробуйте, однако, выполнить эту программу при a=0.2E-16 и b=c=1.0 — первый корень уравнения x1 окажется равным -5.0E16, а второй x2 — нулю.

Если подставить эти значения в выражение $$a x^2 + b x + c$$, то и для x1 и для x2 его значение окажется равным единице, а не нулю. Подобная ошибка для первого, весьма большого по величине корня, представляется вполне естественной, но вот соглашаться с тем, что нуль является корнем данного уравнения, совсем не хочется. Этой проблеме посвящена одна из приведенных ниже задач.

Арифметические и побитовые операторы языка Java

К арифметическим операторам языка Java, которые определены для всех числовых типов, относятся: + (сложение и унарный плюс), += (сложение с присваиванием), - (вычитание и унарный минус), -= (вычитание с присваиванием), * (умножение), *= (умножение с присваиванием), / (деление), /= (деление с присваиванием), % (остаток от деления или деление по модулю), %= (остаток от деления с присваиванием), ++ (инкремент) и -- (декремент).

Любой оператор с присваиванием с точки зрения получаемого результата эквивалентен выполнению соответствующей операции с последующим присваиванием, но работает обычно быстрее: a @= b эквивалентно а = a @ b (здесь символ @ означает любую из бинарных арифметических операций).

Результат выполнения операций деления и деления по модулю (нахождения остатка) для целочисленных операндов является целым числом. Так, например, 5/3 равняется 1.

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

int i = 2, j = 3;   // i = 2, j = 3
    int k = i + j++;    // k = 5, j = 4
    int m = --i;        // i = 1, m = 1

С величинами целых типов можно выполнять дополнительные действия. К побитовым (или поразрядным) операторам языка Java относятся следующие: ~ (дополнение), (побитовое И ), = (побитовое И с присваиванием), | (побитовое Или ), |= (побитовое Или с присваиванием), ^ (исключающее Или ), ^= (исключающее Или с присваиванием), << (сдвиг влево), <<= (сдвиг влево с присваиванием), >> (сдвиг вправо), >>= (сдвиг вправо с присваиванием), >>> (сдвиг вправо с размножением нуля) и >>>= (сдвиг вправо с присваиванием с размножением нуля).

Результаты операций побитового дополнения, Или, исключающего Или и И получаются путем выполнения над каждым из битов операнда (операндов) действий в соответствии с таблицей 4.1.

Например, 4^5 равняется 1 (ибо двоичные представления этих чисел есть соответственно 100 и 101 ).

У операторов сдвига второй аргумент показывает количество разрядов, на которое надо осуществить сдвиг в двоичном представлении первого операнда влево (для << ) или вправо (для >> и >>> ).

int i = 3, j = 100;	// i = 3, j = 100
    int k = i << 4;     // k = 48
    int m = j >> 2;     // m = 25

Легко понять, что сдвиг влево на $$n$$ разрядов эквивалентен умножению на $$2^n$$, а сдвиг вправо — делению на то же число.

Задачи для самостоятельного решения

Задача 4.3.Предъявите целое число $$x$$ такое, что $$x + 1 < x$$.

Задача 4.4.Явно перечислите и изобразите на числовой прямой все точки множества $$\mathbb{R}_M$$, сделав следующие допущения: числа хранятся в нормализованной форме с плавающей точкой; для хранения как мантиссы, так и порядка числа отводится по три бита (из которых в обоих случаях один является знаковым); никаких особых значений нет.

Задача 4.5.Предъявите действительное (типа double ) число $$x$$ такое, что $$(x /2) \cdot 2 \ne x$$. Воспользуйтесь тем, что класс java.lang.Double определяет константу MIN_VALUE.

Задача 4.6.Определите (приближенно) $$MACHEPS$$ (машинное эпсилон) для типов double и float. Машинным эпсилоном называется наибольшее число $$x$$ данного типа, удовлетворяющее соотношению $$1+x=1$$.

Задача 4.7.Предъявите последовательность чисел (типа float ), при суммировании которой в прямом и обратном порядке результаты будут отличаться не менее, чем вдвое.

Задача 4.8.Напишите программу, вводящую действительные коэффициенты $$a$$, $$b$$ и $$c$$ квадратного уравнения $$a x^2 + b x + c = 0$$ с положительным дискриминантом, находящую оба корня этого уравнения достаточно точно во всех случаях.

Числа произвольной длины и точности

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

В случае языка Java пакет java.math дает возможность программисту работать с целыми и вещественными числами произвольной длины и точности, не требуя при этом никакого дополнительного кодирования, однако обсуждение данного пакета в нашем курсе не предполагается.

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