6 февр. 2009 г.

Представление чисел

Данная статья посвящена разным неожиданностям в связи с конечным представлением чисел в ЭВМ.

Представление чисел в языках программирования в целях экономии памяти ограничивают конкретными размерами, так типичными типами данных можно назвать
  • byte - представление целого числа в виде одного байта, беззнаковые 0 .. 255, знаковые -128 .. 127
  • int - представление целого числа в виде 4х байт***, беззнаковые 0 .. 232 - 1, знаковые -231 .. 231 - 1
  • long - представление целого числа в виде 8х байт***, беззнаковые 0 .. 264 - 1, знаковые -263 .. 263 - 1
  • float - представление числа с плавающей точкой в виде 4х байт***
  • double - представление числа с плавающей точкой в виде 8х байт***

*** - кол-во байт в представлении на разных платформах разное, приведены значения для 32х разрядной платформы

Java.
В одном из проектов нам потребовалось ввести константу, которая содержит кол-во миллисекунд в году, казалось бы просто
public static final int MILLIS_IN_YEAR = 365 * 24 * 60 * 60 * 1000;

К коде хотелось написать именно такое выражение, дабы повысить читаемость кода. Однако, как оказалось значение MILLIS_IN_YEAR хранит далеко не то, что нужно. Когда была записана явно константа 31536000000 компилятор выдал ошибку о необходимости привести long к int.
Действительно, если посчитать кол-во бит, которое занимает данное число log2(N):
 $ echo "l(365 * 24 * 60 * 60 * 1000)/l(2)" | bc -l
34.87628063036765986180
что явно больше, чем 32 бита int'а. Код стал выглядеть:
public static final long MILLIS_IN_YEAR = 365 * 24 * 60 * 60 * 1000;
Однако и в этом случае MILLIS_IN_YEAR не есть 31536000000.

Всё это происходит потому, что типы чисел записанные в произведении - есть int. И в данном случае произведение двух int выражений есть int (и только после вычисления произведения полученный ответ приводится к long JLS, 5.1.2 Widening Primitive Conversion) - JLS, 4.2.2 Integer Operations:
If an integer operator other than a shift operator has at least one operand of type long, then the operation is carried out using 64-bit precision, and the result of the numerical operator is of type long. If the other operand is not long, it is first widened (§5.1.5) to type long by numeric promotion (§5.6). Otherwise, the operation is carried out using 32-bit precision, and the result of the numerical operator is of type int.

Во время вычисления произведения на этапе компиляции происходит переполнение int и число хранит значимую часть битового представления (причём, знак может не сохраняться): Java Language Specification, 15.17.1 Multiplication Operator *
If an integer multiplication overflows, then the result is the low-order bits of the mathematical product as represented in some sufficiently large two's-complement format. As a result, if overflow occurs, then the sign of the result may not be the same as the sign of the mathematical product of the two operand values.

Выход из данной ситуации уже подсказан:
If an integer operator other than a shift operator has at least one operand of type long, then the operation is carried out using 64-bit precision
т.е результирующий код должен выглядеть:
public static final long MILLIS_IN_YEAR = 365L * 24L * 60L * 60L * 1000L;
где L есть обозначение, что число есть long (см. JLS, 3.10.1 Integer Literals)

C/C++.
Примерно такая же история происходит и в C/C++ (хотя точнее будет сказать, что это в Java подобно C/C++, т.к корни java всё же уходят к C/C++):
#include <iostream>

int main(int argc, char *argv[]) {
int i = 365 * 24 * 60 * 60 * 1000;
std::cout << "i " << i << std::endl;
return 0;
};
ожидать чуда конечно не стоит, но только gcc предупредит:
$ g++ -Wall -W main.cpp -o main
main.cpp: In function 'int main(int, char**)':
main.cpp:4: warning: integer overflow in expression
main.cpp: At global scope:
main.cpp:3: warning: unused parameter 'argc'
main.cpp:3: warning: unused parameter 'argv'


ECMA-262: JavaScript, Qt Script, ActiveScript и т.п.
Согласно спецификации ECMA-262 тип Number определён как 64х битное представление числа с двойной точностью IEEE 754 (1985)
4.3.20 Number Type
The type Number is a set of values representing numbers. In ECMAScript, the set of values represents the double-precision 64-bit format IEEE 754 values including the special "Not-a-Number" (NaN) values, positive infinity, and negative infinity.

Т.о Number можно законно считать double на 32х битных платформах - т.е Number, как и любое другое число с плавающей точкой представлено в виде
  • знака (sign)
  • показателя (exponent)
  • мантиссы (fraction)

Или другими словами число с плавающей точкой f может быть представлено схожим образом с нормальной формой как
f = (sign ? -1 : 1) * fraction * 10exponent

Причём, спецификация IEEE 754-1985 General_layout описывает строго, что хранит мантиса:
Мантисса определяет наиболее значимую часть

И не стоит удивляться почему же Number(235723572357235723) == 235723572357235700 и даже Number(235723572357235723) == 235723572357235701 (и не только).

ps. Хочется упомянуть об одном парадоксальном на первый взгляд факте:
В математике существует только одно действительное число, такое, что f == - f и это число есть 0.
В C/C++ есть стандартный header file limits.h, который содержит граничные значения разных типов целых чисел. И не удивляйтесь, что INT_MIN == - INT_MIN.

2 комментария:

Andrey комментирует...

Зачем в решении для Java добавление L к каждому числу?

Вполне достаточно:
public static final long MILLIS_IN_YEAR = 365 * 24 * 60 * 60 * 1000L;

или так (более заметно):
public static final long MILLIS_IN_YEAR = (long)365 * 24 * 60 * 60 * 1000;

Владимир Долженко комментирует...

разницы между (long)365 * 24 * 60 * 60 * 1000 и 365L * 24 * 60 * 60 * 1000 - нет.

по мне так красивее выглядит код с L - дело вкуса.

зачем добавление L к каждому числу ? скорее для ясности, что используется арифметика long-чисел, однако, спорить, не буду - такая запись излишне.