Пользователь
0,0
рейтинг
16 апреля 2014 в 15:11

Разработка → Пара слов о числах с плавающей точкой в Java

JAVA*

Несколько дней назад мне на глаза попался занимательный такой вопрос, касающийся того, каков будет результат выполнения данного кода:
double a = 2.0 - 1.1;

или такого:
double f = 0.0;
for (int i=1; i <= 10; i++) {
	f += 0.1;
}

Вопреки всем моим ожиданиям, ответ: 0.89999999999999991 в первом случае и 0.99999999999999989 во втором.
Для тех, кто хочет узнать почему, а так же еще несколько занимательных фактов про этот тип данных, милости просим.



В общем виде ответ на поставленный выше вопрос будет звучать примерно так: «Подобные ошибки связанны с внутренним двоичным (binary) представлением чисел. Подобно тому, как в десятичной системе нельзя точно представить результат деления 1/3, так и в двоичной системе невозможно точно представить 1/10. Если вам нужно исключить ошибки округления, следует использовать класс BigDecimal».

Существует важное различие между абстрактными вещественными числами, такими как π или 0.2, и типом данных double в Java. Во-первых, платонически-идеальное представление вещественных чисел является бесконечным, в то время как представление в Java ограничено числом бит. Однако точность вычислений является еще более насущной проблемой, чем ограничение на размер чисел. Еще больше «интригует» совершенно оригинальный способ округления чисел, но обо всем по порядку.

Начать, пожалуй, стоит с двоичного представления целых чисел. Этот абзац нам пригодится чуть позже. Итак. Самым простым вариантом представления целых чисел считается так называемый «Прямой код», в котором старший бит используется для записи знака числа (0 — положительное, 1 — отрицательное), а оставшиеся биты используются непосредственно для записи самого значения. Таким образом, число "-9" в восьмиразрядном представлении будет выглядеть как 10001001. Недостатком такого подхода считается наличие двух нулей ("+0" и "-0") и усложнение арифметических операций с отрицательными числами. Другим вариантом, интересующим нас, является «Код со сдвигом», в котором, говоря простым языком, мы прибавляем к нашему числу некое константное для данного типа представления число, равное 2^(n-1), где n — число разрядов (бит). В нашем случае, пример с числом "-9" в восьмиразрядном представлении будет выглядеть так:
-9 + 2^(8-1) = -9 + 128 = 119. В двоичном виде получим 01110111. Этот вариант удобен тем, что ноль у нас всего один, однако при арифметических операциях необходимо будет учитывать смещение.

Здесь стоит упомянуть вот о чем. Одной из заявленных целей языка Java является машинная независимость. Вычисления должны приводить к одинаковому результату, независимо от того, какая виртуальная машина их выполняет. Для арифметических вычислений над числами с плавающей точкой это неожиданно оказалось трудной задачей. Тип double использует для хранения числовых значений 64 бита, однако некоторые процессоры применяют 80-разрядные регистры с плавающей точкой. Эти регистры обеспечивают дополнительную точность на промежуточных этапах вычисления, т.е. промежуточный результат вычислений храниться в 80-разрядном регистре, после чего ответ округляется до 64 бит. Однако этот результат может оказаться иным, если в процессе всех вычислений используется 64-разрядный процессор. По этой причине в первоначальном описании JVM указывалось, что все промежуточные вычисления должны округляться. Это вызвало протест многих специалистов, поскольку подобное округление не только может привести к переполнению, но и сами вычисления происходят медленнее. Это привело к тому, что в JDK 1.2 появилась поддержка ключевого слова strictfp, гарантирующая воспроизводимость результатов всех вычислений, производимых внутри этого метода, класса или интерфейса (вернее его реализации). Иными словами, ключевое слово strictfp гарантирует, что на каждой платформе вычисления с плавающей точкой будут вести себя одинаково и с определенной точностью, даже если некоторые платформы могут производить вычисления с большей точностью. Интересно, что для процессоров семейства x86 модуль операций с плавающей точкой был выделен в отдельную микросхему, называемую математическим сопроцессором (floating point unit (FPU)). Начиная с процессоров Pentium модели MMX модуль операций с плавающей точкой интегрирован в центральный процессор. Подробнее.

Далее. Стандарт IEEE 754 говорит нам, что представление действительных чисел должно записываться в экспоненциальном виде. Это значит, что часть битов кодирует собой так называемую мантиссу числа, другая часть — показатель порядка (степени), и ещё один бит используется для указания знака числа (0 — если число положительное, 1 — если число отрицательное). Математически это записывается так:
(-1)^s × M × 2^E, где s — знак, M — мантисса, а E — экспонента. Экспонента записывается со сдвигом, который можно получить по формуле, приведенной выше.

Что такое мантисса и экспонента? Мантисса – это целое число фиксированной длины, которое представляет старшие разряды действительного числа. Допустим наша мантисса состоит из четырех бит (|M|=4). Возьмем, например, число «9», которое в двоичной системе будет равно 1001.
Экспонента (ее еще называют «порядком» или «показателем степени») – это степень базы (двойки) старшего разряда. Можно рассматривать ее как количество цифр перед точкой, отделяющей дробную часть числа. Если экспонента переменная, записываемая в регистр и неизвестная при компиляции, то число называют «числом с плавающей точкой». Если экспонента известна заранее, то число называют «числом с фиксированной точкой». Числа с фиксированной точкой могут записываться в обыкновенные целочисленные переменные (регистры) путем сохранения только мантиссы. В случае же записи чисел с плавающей точкой, записываются и мантиса и экспонента в так называемом стандартном виде, например «1.001e+3». Сразу видно, что мантисса состоит из четырех знаков, а экспонента равна трем.

Допустим мы хотим получить дробное число, используя те же 3 бита мантиссы. Мы можем это сделать, если возьмем, скажем, E=1. Тогда наше число будет равно

1.001e+1 = 1×2^2 + 0×2^1 + 0×2^0 + 1×2^(-1) = 4 + 0,5 = 4,5



Одной из проблем такого подхода может стать различное представление одного и того же числа в рамках одной длины мантиссы. Нашу «9-ку», при длине мантиссы равной 5, можно представить и как 1.00100e+3 и как 0.10010e+4 и как 0.01001e+5. Это не удобно для оборудования, т.к. нужно учитывать множественность представления при сравнении чисел и при выполнении над ними арифметических операций. Кроме того, это не экономично, поскольку число представлений — конечное, а повторения уменьшают множество чисел, которые вообще могут быть представлены. Однако тут есть маленькая хитрость. Оказывается, что для вычисления значения первого бита можно использовать экспоненту. Если все биты экспоненты равны 0, то первый бит мантиссы также считается равным нулю, в противном случае он равен единице. Числа с плавающей точкой, в которых первый бит мантиссы равен единице, являются нормализованными. Числа с плавающей точкой, первый бит мантиссы в которых равен нулю, называются денормализованными. С их помощью можно представлять значительно меньшие величины. Поскольку первый бит всегда может быть вычислен, нет необходимости хранить его явным образом. Это экономит один бит, так как неявную единицу не нужно хранить в памяти, и обеспечивает уникальность представления числа. В нашем примере с «9» нормализованным представлением будет 1.00100e+3, а мантисса будет храниться в памяти как «00100», т.к. старшая единица подразумевается неявно. Проблемой такого подхода является невозможность представления нуля, о которой я скажу чуть позже. Подробнее об этом и многом другом можно почитать тут и тут.

К слову, в JDK 1.5 допустимо задавать числа с плавающей точкой в шестнадцатеричном формате. Например, 0.125 можно представить как 0x1.0p-3. В шестнадцатеричной записи для указания экспоненты используется знак «p» вместо «е».

Вещи, о которых стоит помнить, работая с Double:

  1. Целочисленное деление на 0 генерирует исключение, в то время как результатом деления на 0 чисел с плавающей точкой является бесконечность (или NaN в случае деления 0.0/0). Кстати мне было интересно узнать, что разработчики JVM, согласно все тому же стандарту IEEE 754 ввели также и значения Double.NEGATIVE_INFINITY и Double.POSITIVE_INFINITY, равные -1.0 / 0.0 и 1.0 / 0.0 соответственно.
  2. Double.MIN_VALUE на самом деле не самое маленькое число, которое можно записать в double. Помните, мы говорили о том, что согласно стандарту IEEE 754, старшая единица мантиссы указывается неявно? Так вот. Как уже было оговорено выше, в нормализованной форме числа с плавающей точкой невозможно представить ноль, поскольку нет такой степени двойки, которая равнялась бы нулю. И разработчики JVM специально для решения этой проблемы ввели переменную Double.MIN_VALUE, которая, по сути, является максимально близким значением к нулю. Самым маленьким значением, которое вы можете сохранить в double является "-Double.MAX_VALUE".
    System.out.println(0.0 > Double.MIN_VALUE); // возвращает false 
  3. Развивая предыдущую тему, можно привести еще один интересный пример, показывающий нам, что не все так очевидно, как может показаться на первый взгляд. Double.MAX_VALUE возвращает нам 1.7976931348623157E308, но что будет если мы преобразуем строку, содержащую число с плавающей запятой в double?

    System.out.println(Double.parseDouble("1.7976931348623157E308")); // (...7E308) = 1.7976931348623157E308 max value 
    System.out.println(Double.parseDouble("1.7976931348623158E308")); // (...8E308) = 1.7976931348623157E308 same???
    System.out.println(Double.parseDouble("1.7976931348623159E308")); // (...9E308) = Infinity
    


    Оказывается, между Double.MAX_VALUE и Double.POSITIVE_INFINITY есть еще некоторые значения, которые при вычислении округляются в одну или другую сторону. Тут стоит остановиться подробнее.

    Множество вещественных чисел является бесконечно плотным (dense). Не существует такого понятия, как следующее вещественное число. Для любых двух вещественных чисел существует вещественное число в промежутке между ними. Это свойство не выполняется для чисел с плавающей точкой. Для каждого числа типа float или double существует следующее число. Кроме того, существует минимальное конечное расстояние между двумя последовательными числами типа float или double. Метод Math.nextUp() возвращает следующее число с плавающей точкой, превышающее заданный параметр. Например, данный код печатает все числа типа float между 1.0 и 2.0 включительно.

    float x = 1.0F;
    int numFloats = 0;
    while (x <= 2.0) {
        numFloats++;
        System.out.println(x);
        x = Math.nextUp(x);
    }
    System.out.println(numFloats);
    


    Оказывается, что в промежутке от 1.0 до 2.0 включительно лежит ровно 8,388,609 чисел типа float. Это немало, но намного меньше, чем бесконечное множество вещественных чисел, которые находятся в том же диапазоне. Каждая пара последовательных чисел типа float находится на расстоянии примерно 0.0000001 друг от друга. Это расстояние называется единицей наименьшей точности (unit of least precision – ULP). Для типа double ситуация совершенно идентичная, за исключением того факта, что кол-во чисел после запятой значительно выше.


Пожалуй, на этом все. Желающим «копнуть поглубже» может пригодится следующий код:

// Возвращает представление заданного значения с плавающей точкой в соответствии с IEEE 754
long lbits = Double.doubleToLongBits(-0.06);
long lsign = lbits >>> 63; // знак
long lexp = (lbits >>> 52 & ((1 << 11) - 1)) - ((1 << 10) - 1); // порядок
long lmantissa = lbits & ((1L << 52) - 1); // мантисса
System.out.println(lsign + " " + lexp + " " + lmantissa);
System.out.println(Double.longBitsToDouble((lsign << 63) | (lexp + ((1 << 10) - 1)) << 52 | lmantissa));


Спасибо всем осилившим. Буду рад конструктивной критике и дополнениям.

Материалы по теме:
Новые математические возможности Java: Часть 2. Числа с плавающей точкой
IEEE Standard 754 Floating Point Numbers
Java Language and Virtual Machine Specifications
Представление вещественных чисел
Что нужно знать про арифметику с плавающей запятой
Арифметические операции над числами с плавающей точкой
Сорокин Андрей @asdForever
карма
3,0
рейтинг 0,0
Реклама помогает поддерживать и развивать наши сервисы

Подробнее
Реклама

Самое читаемое Разработка

Комментарии (32)

  • +30
    Ну очень старая тема. Перетертая очень много раз и не только на хабре…
  • +19
    > Вопреки всем моим ожиданиям

    А каковы были ваши ожидания от арифметики с плавающей точкой? 1.0? :)

    Может быть тайну открою, но это не только в Java справедливо.
    • +3
      +1
      Читал статью и недоумевал — а Джава то причем?

      Кстати, по теме есть хороший текст на английском «What Every Computer Scientist Should Know About Floating-Point Arithmetic», David Goldberg, March, 1991

      Доступен в т.ч. на сайте Оракл: docs.oracle.com/cd/E19957-01/806-3568/ncg_goldberg.html
  • +12
    По-моему, это уже в школе преподают, не говоря уже о университете.
    • +4
      В какой школе, вы о чём? В школах либо учат алгоритмы чистки картошки, либо играют в Prehistoric/CS/Worms и т.д.
      Ах да, ещё изучают стили Word и анимации PowerPoint.
      • +1
        Как минимум в школе, где информатику ведёт моя мама. А ещё у нас (электронщиков) в первом семестре информатики в университете было.
        • +3
          Увы, я боюсь, что таких школ как ваша — подавляющее меньшинство.
      • +16
        > алгоритмы чистки картошки
        • +2
          Любимая книга детства
  • +16
    Очередное поколение узнаёт про существование сопроцессора.

    (шёпотом) А ещё Деда Мороза не существует.
  • +4
    Конечно не ново, но мне кажется надо каждые лет пять-семь постить такой текст. Чтобы очередное поколение «хакеров» выучило. А то будут снова деньги через double считать…
    • 0
      Вы, конечно, будете очень смеяться, но биткойн-клиент считает именно с плавающей точкой.
      (поищите «double» например в bitcoinrpc.cpp — я уж не буду копипастить код сюда).
      Почему это было сделано так — мне лично не понятно.
      В принципе деньги можно считать с плавающей точкой, если их количество не превышает определенного максимума и знаков после запятой тоже немного. Но зачем из буханки делать троллейбус?
      • 0
        Заинтересовался и посмотрел. Действительно на уровне API принимает double и конвертирует в int64_t. Странное решение, но на уровне протокола всё нормально. Только пользователям будем неудобно, нельзя посылать количество денег, которое бы и можно бы выразить на уровне протокола, да точности параметров API не хватает.

        Ещё забавная проверка на «dAmount > 21000000.0». API не даст даже попытаться послать все деньги в мире сразу :)

        Но, по крайней мере, на уровне bitcoin протокола всё в порядке.
      • 0
        >>поищите «double» например в bitcoinrpc.cpp
        Спасибо большое! Весьма поучительно ;)
      • 0
        Деньги можно считать через double. При этом никаких проблем с накоплением ошибки не будет, если округлять только на последнем шаге и не использовать округлённое значение в последующих расчетах.

        Насколько я понимаю, главное правило при работе с валютой — никогда не использовать деление. То есть вместо деления пополам мы берем 50% (умножаем на 0.5). Таким образом мы, например, признваем, что невозможно разделить сумму на три. Можно это сделать только с заданной точностью. И это будет управляемо. B = A * 0.333

        А все остальные операции — и сложение, и вычитание, и умножение не дают накопления ошибки. И разницы между использованием десятичной и двоичой системы счисления никакой.
        • 0
          При этом никаких проблем с накоплением ошибки не будет, если округлять только на последнем шаге
          Проблемы могут быть, так как конечное представление чисел в любом случае требует промежуточных округлений. Если длина мантиссы 23 бита, то при перемножении двух чисел имеющих 20-битную мантису ошибки будут появляться.
  • +1
    >Начиная с процессоров Pentium модели MMX модуль операций с плавающей точкой интегрирован в центральный процессор.
    Это немного пораньше произошло, последний сопроцессор вроде на 386-м был.
    • +3
      А что тогда это?
      image
      А это...
      полноценный процессор, который не работал без i486SX, и ставился в слот для сопроцессора, и продавался как сопроцессор.
  • +7
    i.imgur.com/4GU7kg7.png

    p.s. картинка почему-то не отображается, пришлось ссылкой
    • 0
    • 0
      Иногда мне кажется, что это такой очень тонкий намёк. «Странно, почему-то не работают теги...»
      Впрочем, имею право ошибиться ;)
      upd: Упс, товарищ WarAngel_alk, это ответ вам.
  • 0
    Не хватает статьи как правильно складывать суммы с плавающей точкой, чтобы результат получался более точным.
    • –3
      Более точным в общем случае не получится, если не увеличивать разрядность мантиссы.
      Да, можно порассуждать, что десять раз по 0.1 должен получиться литр… тьфу! килограмм… да нет же! единица ровно должна получиться.
      А сколько должно получиться, если десять раз по 0.100000000001? А Пи-в-степени-E?
      В общем, в стандартах явно указано с какой точностью считаются числа с плавающей точкой.
      Для 99% вычислений — этого достаточно (но конечно нужно помнить, что вычисления не абсолютно точные)
      Если вас стандартная точность не устраивает — можно исхитряться разными способами, но за счет уменьшения производительности
  • 0
    Есть кстати весьма полезных алгоритм суммирования Кохэна (вики), который сильно уменьшает погрешность суммирования.

    В некоторых случаях он позволяет получить результат с использованием float-а более точный, без этого алгоритма с использованием double. Хотя это конечно не повод повсеместно переходить с double на float, или использовать числа с плавающей точкой для денег :-) Не стоит к тому же пихать такое суммирование всюду, достаточно только в тех местах, где действительно повышенные требования к точности.

    Пример:

    float[] floats = new float[100];
    Arrays.fill(floats, 0.01f);
    
    double[] doubles = new double[100];
    Arrays.fill(doubles, 0.01);
    
    float fsum = 0;
    for (float x: floats) {
      fsum += x;
    }
    System.out.println(fsum);
    // -> выведет 0.99999934, позорная ошибка округления
    
    double dsum = 0;
    for (double x: doubles) {
      dsum += x;
    }
    System.out.println(dsum);
    // -> выведет 1.0000000000000007 - уже неплохо
    
    System.out.println(kahanSum(floats));
    // -> выведет ровно 1.0 - ура!
    


    Само суммирование (из вики):
    static float kahanSum(float... input) {
      float sum = 0;
      float c = 0;          
      for (float v : input) {
        float y = v - c; 
        float t = sum + y;
        c = (t - sum) - y;
        sum = t;
      }
      return sum;
    }
    
  • 0
    Просто оставлю это здесь, для будущих поколений переводчиков. Товарищ кстати из Valve. ИМХО очень компетентен.
  • 0
    Did you know?


  • –2
    Через 50 лет на Хабре будет очень трудно написать статью, чтобы она не была заминусована ворчливыми стариками… Помнится года 4 назад точно такая же статья стала хитом.
    • 0
      Судя по всему, имеется в виду эта статья («Что нужно знать про арифметику с плавающей запятой»). Так а вы сравните:
      1) Здесь читается тезис: «А я вот узнал, что в Java...». В статье по ссылке — полномасшабный, основательный разбор стандарта IEEE754.
      2) Статья по ссылке оформлена приятнее (ну, на мой личный взгляд).
      3) Тема начинает быть избитой (см. тезис и рейтинг первого комментария).
  • +8
    image
  • 0
    Я тоже не пойму причем тут Java.
    Насколько помню, округлять FP числа при выводе учат еще в школе, ну или институте курсе так на первом.
    Инфа хранится в двоичной форме, выводится в десятичной, отсюда все проблемы.
    А ну если хотите точных вычислений с точкой для денег или еще чего, используйте BigDecimal, если на то пошло.
    • 0
      > Инфа хранится в двоичной форме, выводится в десятичной, отсюда все проблемы.

      Побуду Капитаном Очевидностью, но скажу, что проблемы не только в этом.
      Ни при каком способе хранения, ни при каком выводе ни в какой системе счисления вы не сможете точно представить любое вещественное число, просто потому что мощность множества вещественных чисел равна континууму, а количество разрядов в компьютере (и даже атомов в Солнечной системе, и даже фотонов в Галактике) конечно. Следовательно, для любого представления чисел в компьютере существуют числа которые не могут быть представлены (и обработаны) точно.
      • –1
        вы не сможете точно представить любое вещественное число

        Да это нахрен не надо никому :-)
        Стандартный 80 битный формат покрывает 99% вычислений — 19,20 знаков.
        Для всего остального можно реализовать ручками, если припрет.

Только зарегистрированные пользователи могут оставлять комментарии. Войдите, пожалуйста.