Разложение деления с плавающей точкой на целую и дробную части - PullRequest
4 голосов
/ 13 июня 2019

Я пытаюсь сделать целочисленное деление + по модулю, используя удвоения (для сплайн-интерполяции), но я столкнулся с некоторыми проблемами, касающимися точности с плавающей точкой при использовании std::floor и std::fmod.

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

#include <iostream>
#include <cmath>

std::pair<double, double> div1(int num, double denom){
    double whole = std::floor(num / denom);
    double remain = std::fmod(num, denom);
    return {whole, remain};
}
std::pair<double, double> div2(int num, double denom){
    double floatdiv = num / denom;
    double whole;
    double remain = std::modf(floatdiv, &whole);
    return {whole, remain * denom};
}
std::pair<double, double> div3(int num, double denom){
    double whole = std::round(num / denom);
    double remain = std::remainder(num, denom);
    return {whole, remain};
}
int main() {
    double denom = 100.0 / 6;
    int divtype = 0;
    for(auto div: {div1, div2, div3}){
        std::cerr << "== Using div" << ++divtype << " for this run ==\n";
        for(int i = 40; i <= 60; ++i){
            auto res = div(i, denom);
            std::cerr << i << ": " << res.first << ", " << res.second << " = " << res.first * denom + res.second << "\n";
        }
        auto oldprec = std::cerr.precision(64);
        auto res = div(50, denom);
        std::cerr << 50 << ": " << res.first << ", " << res.second << " = " << res.first << " * " << denom << " + " << res.second << " = " << std::floor(res.first) * denom + res.second << "\n";
        std::cerr.precision(oldprec);
        std::cerr << "\n";
    }
    return 0;
}

https://ideone.com/9UbHcE

Для случая 50 получаются следующие результаты:

 - div1: 3, 16.6666... 
 - div2: 3, 0
 - div3: 3, -3e-15

Я что-то не так делаю или std::floor(num / denom) + std::fmod(num, denom) ненадежно?Если это так, что является хорошей заменой?div2 лучший вариант?

Версия примера кода с большинством включенных ответов: https://ideone.com/l2wGRj

Ответы [ 4 ]

2 голосов
/ 13 июня 2019

Ваша основная проблема в том, что denom = 100.0/6 не совпадает с математически точным значением denomMath = 100/6 = 50/3, потому что оно не может быть представлено как сумма степеней двух.Мы можем написать denom = denomMath + eps (с небольшим положительным или отрицательным эпсилоном).После присвоения ему denom неотличимо от ближайшего числа с плавающей запятой!Если вы сейчас попытаетесь разделить некоторое значение denomMath * k = denom * k + eps * k на denom, то для достаточно большого k вы получите неправильный результат математически (то есть в точной арифметике) - у вас нет надежды на этодело.Как скоро это произойдет, зависит от используемых величин (если значения <1, то все ваши <code>div дадут целые части нуля и будут точными, тогда как для значений, больших 2^54, вы даже не сможете представить нечетные числа).

Но даже до этого нет гарантии, что деление (математического) кратного denomMath на denom даст что-то, что может быть floor ed или fmod ed к правильному целому числу.Округление может держать вас в безопасности некоторое время, но, как показано выше, только до тех пор, пока ошибки не станут слишком большими.

Итак:

  • div1сталкивается с проблемой, описанной здесь: https://en.cppreference.com/w/cpp/numeric/math/fmod

    Выражение x - trunc(x/y)*y может не равняться fmod(x,y), когда округление x/y для инициализации аргумента trunc теряет слишком большую точность (пример: x = 30.508474576271183309, y = 6.1016949152542370172)

    В вашем случае 50 / denom дает число, которое немного слишком велико (3) по сравнению с точным результатом (3 - some epsilon, потому что denom немного больше, чем denomMath)

    Нельзя полагаться на std::floor(num / denom) + std::fmod(num, denom) равным num.

  • div2 имеет проблему, описанную выше:В вашем случае это работает, но если вы попробуете больше случаев, вы найдете тот, где num / denom немного слишком маленький, а не слишком большой, и он тоже потерпит неудачу.

  • div3имеет обещание, как упомянуто выше.Это на самом деле дает вам самый точный результат, на который вы могли надеяться.

2 голосов
/ 13 июня 2019

Проблема не в вашем fmod, а в том, что вы вводите floor. Для fmod нормально возвращать что-то близкое к знаменателю из-за нечеткости точности с плавающей точкой. Проблема в том, что вы должны быть осторожны, чтобы относиться к частному с использованием тех же правил, что и к остальным, чтобы получить результаты (используя нечеткое равенство):

x/y == (quot, rem) == quot * y + rem

Для иллюстрации я добавил div4 и div5:

std::pair<double, double> div4( int num,  double denom){
    int quo;
    auto rem = std::remquo(num, denom, &quo );
    return {quo, rem};
}

std::pair<double, double> div5( int num,  double denom){
    auto whole = std::floor(num / static_cast<long double>( denom ) );
    auto remain = std::fmod(num, denom);
    return {whole, remain};
}

Вот уменьшенная версия вашего кода , сосредоточенная только на случае сбоя. Выход:

div1: 50 / 16.6666666666666678509 = (whole, remain) = (3, 16.6666666666666642982) = 66.6666666666666571928
...
div4: 50 / 16.6666666666666678509 = (whole, remain) = (3, -3.55271367880050092936e-15) = 50
div5: 50 / 16.6666666666666678509 = (whole, remain) = (2, 16.6666666666666642982) = 50

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

Если вы используете мой div5, который использует std::remquo для вычисления остатка и частного одновременно, вы получите аналогичную пару (2, ~divisor), которая затем все умножается правильно обратно на 50. (Обратите внимание, что частное возвращается как целое число, а не число с плавающей запятой из этой стандартной функции.) [ Обновление : как отмечено в комментариях, это действительно только для 3 битов точности в частное, то есть оно полезно для периодических функций, нуждающихся в обнаружении квадранта или октанта, но не общего фактора.]

Или, если вы используете мою div4, я использовал вашу div1 логику, но перед операцией деления повысил точность ввода с floor до long double, что дает достаточно цифр для правильной оценки пола. Результат - (3, ~0), который показывает нечеткость в остатке, а не в частном.

Подход long double, в конечном счете, просто парит банку по дороге к той же проблеме с некоторой более высокой точностью. Использование std::remquo является более надежным в численном отношении для ограниченных случаев периодических функций. Какую версию вы выберете, будет зависеть от того, что вас больше волнует: числовые вычисления или симпатичный дисплей.

Обновление : Вы также можете попытаться определить, когда что-то пошло не так, используя исключения FP:

void printError()
{
    if( std::fetestexcept(FE_DIVBYZERO)  ) std::cout << "pole error occurred in an earlier floating-point operation\n";
    if( std::fetestexcept(FE_INEXACT)    ) std::cout << "inexact result: rounding was necessary to store the result of an earlier floating-point operation\n";
    if( std::fetestexcept(FE_INVALID)    ) std::cout << "domain error occurred in an earlier floating-point operation\n";
    if( std::fetestexcept(FE_OVERFLOW)   ) std::cout << "the result of the earlier floating-point operation was too large to be representable\n";
    if( std::fetestexcept(FE_UNDERFLOW)  ) std::cout << "the result of the earlier floating-point operation was subnormal with a loss of precision\n";
}

// ...
// Calling code
std::feclearexcept(FE_ALL_EXCEPT);
const auto res = div(i, denom);
printError();
// ...

Сообщает inexact result: rounding was necessary to store the result of an earlier floating-point operation для функций 1, 2, 3 и 5. Смотрите его в прямом эфире на Coliru .

1 голос
/ 14 июня 2019

Для положительных числителей и знаменателей математически точное частное и остаток могут быть вычислены с помощью следующего кода, при условии, что частное не превышает значения формата с плавающей запятой (2 53 для типичный double):

std::pair<double, double> divPerfect(int num, double denom)
{
    double whole = std::floor(num / denom);
    double remain = std::fma(whole, -denom, num);
    if (remain < 0)
    {
        --whole;
        remain = std::fma(whole, -denom, num);
    }
    return {whole, remain};
}

Обоснование:

  • Если точное num / denom является целым числом, оно представимо, и num / denom должно выдать его, а std::floor(num / denom) имеет то же значение. В противном случае num / denom может слегка округлить вверх или вниз, что не может уменьшить std::floor(num / denom), но может увеличить его на единицу. Следовательно, double whole = std::floor(num / denom) дает нам либо правильный фактор, либо еще один.
  • Если whole является правильным, то std::fma(whole, -denom, num) является точным, поскольку точный математический ответ имеет величину меньше denom или равна whole (если whole <<code>denom), и его наименее значимый бит по крайней мере настолько же велик, как доступная позиция младшего значащего бита в denom или whole, соответственно, поэтому все его биты соответствуют формату с плавающей запятой, поэтому он представим и поэтому должен быть получен в результате. Кроме того, этот остаток неотрицателен.
  • Если whole слишком велико, то std::fma(whole, -denom, num) отрицательно (но все же точно, как указано выше). Затем мы исправляем whole и повторяем std::fma, чтобы получить точный результат.

Я ожидаю, что второго std::fma можно избежать:

std::pair<double, double> divPerfect(int num, double denom)
{
    double whole = std::floor(num / denom);
    double remain = std::fma(whole, -denom, num);
    return 0 <= remain ? std::pair(whole, remain) : std::pair(whole - 1, remain + denom);
}

Однако я хотел бы подумать об этом немного больше, чтобы быть уверенным.

0 голосов
/ 13 июня 2019

Это действительно кажется, что это может быть ошибкой в ​​реализации fmod(). Согласно определению на std :: fmod на cppreference.com:

Остаток с плавающей точкой операции деления x / y, вычисленный этой функцией, в точности равен x - n * y, где n - это x / y с урезанной дробной частью

Поэтому я добавил:

std::pair<double, double> div4(int num, double denom){
    double whole = std::floor(num / denom);
    int n = trunc(num / denom) ;
    double remain = num - n * denom ;
    return {whole, remain};
}

и глядя на вывод просто div1 и div4 от 49 до 51 Я получаю 1 :

== Using div1 for this run ==
49: 2, 15.6667 = 49
50: 3, 16.6667 = 66.6667
51: 3, 1 = 51
50: 3, 16.66666666666666429819088079966604709625244140625 = 3 * 16.666666666666667850904559600166976451873779296875 + 16.66666666666666429819088079966604709625244140625 = 66.666666666666657192763523198664188385009765625

== Using div4 for this run ==
49: 2, 15.6667 = 49
50: 3, 0 = 50
51: 3, 1 = 51
50: 3, 0 = 3 * 16.666666666666667850904559600166976451873779296875 + 0 = 50

Что дает желаемый результат.


1 Поскольку это все, что мне нужно было передать, вышеприведенный вывод был сгенерирован путем запуска исходного кода через Emscripten , который использует clang для преобразования код в JavaScript, который затем запускался с помощью node.js. Поскольку это привело к той же «проблеме» с исходным кодом, я ожидаю / надеюсь, что мой div4 будет делать то же самое, если скомпилирован с нативным кодом.

...