*** ВНИМАНИЕ: Блог переехал на другой адрес - demin.ws ***

среда, 12 мая 2010 г.

Плавающая точка уплыла

Решал одну задачу на UVa Online Judge. Долго не мог найти проблему и проверял алгоритм.

Но все было гораздо проще. Как вы думаете, что должна выводить следующая программа?

#include <iostream>
#include <cmath>
using namespace std;

int main(int argc, char* argv[]) {
  double f = 1.15;
  int a = f * 100.0 + 0.1E-9;
  int b = f * 100.0;
  cout << "a = " << a << endl;
  cout << "b = " << b << endl;
  return 0;
}

Я ожидал два числа 115.

Нет, у меня на VS2008 она печатает:

a = 115
b = 114

Вот такие дела.

Update:
Кстати, если попробовать так:

#include <iostream>
#include <cmath>
using namespace std;

int main(int argc, char* argv[]) {
  double f = 1.15;
  int a = f * 100.0 + 0.1E-9;
  int b = f * 100.0;
  cout << "a = " << a << endl;
  cout << "b = " << b << endl;
  double f1 = 0.15;
  int a1 = f1 * 100.0 + 0.1E-9;
  int b1 = f1 * 100.0;
  cout << "a1 = " << a1 << endl;
  cout << "b1 = " << b1 << endl;
  return 0;
}
то результат будет:
a = 115
b = 114
a1 = 15
b1 = 15
Как я думаю, это из-за того, что числа, у которых целая часть нулевая имеют немного особое внутреннее представление в IEEE.

На ТопКодере есть отличная статья на эту тему (часть 1 и часть 2). Все кратко и по делу.

11 комментариев:

  1. Некоторые компиляторы сжимают числа с плавающей точкой до целого числа с испольльзованием формата Q16.

    ОтветитьУдалить
  2. Проверил в дотнете еще такой вариант:

    float f = 1.15f;
    int a = (int)(f * 100.0f + (float)(0.1E-9));
    int b = (int)(f * 100.0f);

    Вообще травокурность получается :)
    Дебаггер в рантайме показывает значение выражений 115.0, но приведение к инт-у делает из обоих значение 114.

    ОтветитьУдалить
  3. Шаг дисретной сетки? Аналогичный пример на 1й странице Страуструпа с числом 10.0

    ОтветитьУдалить
  4. Ничего удивительного. Числа с плавающей точкой не представимы точно, если только это не суммы степеней двойки. В итоге 1.15 * 100 оказывается на самом деле числом, чуть меньше 115. При приведении чисел с плавающей точкой к целым дробная часть отсекается, не важно что она равна 0.999999999.

    ОтветитьУдалить
  5. я в таких случаях (нужно округлить до целого по привычным школьным правилам) делаю
    double d = 115.0
    std::cout << (int)(d+0.5);

    ОтветитьУдалить
  6. Egor: Пардон, VS2008.

    Vlad: Это все понятно. Просто странно, что технически мантиссы даже во float должно хватить, чтобы точно представить 1.15. К тому же я задаю константу, а не получаю это в результате деления, например.

    ОтветитьУдалить
  7. Немного обновил пример. Получается еще интереснее.

    ОтветитьУдалить
  8. Да плавающей точке вообще особо доверять не стоит. Взять хотя бы классический пример с округлением 0.1 до ближайшего конечного двоичного представления.

    #include
    int main(){
    std::cout << 0.1 + 0.1 + 0.1 + 0.1 + 0.1 + 0.1 + 0.1 + 0.1 + 0.1 + 0.1 + 0.1 + 0.1 + 0.1 + 0.1 + 0.1 + 0.1 + 0.1 + 0.1 + 0.1 + 0.1 - 2 << std::endl;
    return 0;
    }

    Получается 4.44089e-16 (g++ 4.4.4-1, Debian), так как 0.1 — периодическая дробь в двоичной системе и, разумеется, округляется.

    А во втором примере так получилось не из-за разного представления, а совсем наоборот. Представление там как раз очень единообразное.

    Просто 0.15 представляется как 0.0010011001100110011001…, а 1.15 — как 1.0010011001100110011001….

    Получается бесконечная периодическая дробь, так как 15/100=3/20, а 20 не является степенью двойки. То есть округление неизбежно.

    Из-за целой части нормализации для 1.15 и 0.15 будут разные:
    0.15 = 1.0011001100110011001…e-3
    1.15 = 1.0010011001100110011…e+0
    (нужно взять столько знаков, сколько требуется для мантиссы в соответствующем типе).

    Различия начинаются после 3-го знака за десятичной точкой.

    При умножении и сложении с 0.1e-9 числа будут приводиться к общей экспоненте, тогда при округлениях и скажется это всё.

    Если в качестве f брать 1.15 и 1.16, то a и b будут разными, так как они представляются бесконечными дробями и будут округлены при представлении в виде IEEE745, а вот если взять число, лежащее между ними — 1.15625 — и имеющее конечное представление, то они совпадут.

    Вообще различие между числами происходило из-за того, что b чуть-чуть недотягивало до целого, что в a компенсировалось добавлением малого числа.

    ОтветитьУдалить
  9. Реализация, подсмотренная в mscorlib 2.0.0.0 решает проблему :)

    int ToInt32(double value)
    {
    if (value >= 0.0)
    {
    if (value < 2147483647.5)
    {
    int num = (int) value;
    double num2 = value - num;
    if ((num2 > 0.5) || ((num2 == 0.5) && ((num & 1) != 0)))
    {
    num++;
    }
    return num;
    }
    }
    else if (value >= -2147483648.5)
    {
    int num3 = (int) value;
    double num4 = value - num3;
    if ((num4 < -0.5) || ((num4 == -0.5) && ((num3 & 1) != 0)))
    {
    num3--;
    }
    return num3;
    }
    cout << "Overflow_Int32" << endl;
    return 0;
    }

    ОтветитьУдалить
  10. Поэтому к int'у и делают приведение ввиде округления:

    int a = static_cast(floor(f * 100.0 + 0.1E-9 + 0.5));
    int b = static_cast(floor(f * 100.0 + 0.5));

    это работает так, как надо :)

    ОтветитьУдалить