Нередко в базах данных и вообще любой работы с массивами возникают сложения чисел с плавающей точкой. С ними вроде всё хорошо, IEEE 754 стандарт давно устоялся, но чем больше вы складываете чисел, тем больше накапливается ошибка. Ещё хуже, если вы суммируйте в разных потоках или машинах, результаты могут быть разные и надо писать отдельные проверки на сравнения. Ошибка, конечно же, идёт из округлений.
Кейс: вы работаете с данными и считайте порог для их удаления. Доверять только одному процессу с удалением строго нельзя, поэтому часто делают кворумные джобы, где запускают много одинаковых бинарей, которые обязаны договориться о том, что данные можно удалять. Это позволяет выкладывать новый код на staging, не боясь, что данные удалятся (например, кворум не наберётся, если из 3 реплик мы выложим новый плохой код только на одну). Нередкие проблемы, которые я видел в проде своими глазами были связаны с тем, что удаления не могли договориться из-за того, что вокруг порога X одни джобы считали X - eps, другие X + eps. В итоге данные не удалялись и репортились в алёрт о том, что всё разъехалось, не страшно для людей, но бесит разработчиков.
Я настоятельно рекомендую, конечно же, сравнивать с eps в общем случае, но если уж не получается, то наука приготовила для нас интересные алгоритмы, которые позволяют уменьшить ошибку очень сильно. В наивном сложении после сложения n чисел будет ошибка ~machine_eps * n * сумму_модулей, где machine_eps — машинный эпсилон, для float это примерно 6*10^-8, для double это примерно 10^-16.
Самый лёгкий способ, это конечно, отсортировать числа с плавающей точкой как-нибудь и просуммировать, но как говорилось выше, это не всегда возможно из-за распределённых оптимизаций суммирования.
Другой способ это использовать алгоритм от Shewchuk, который просто сохраняет все ошибки в массив и их складывает, пока не договорится, что ошибка после всех округлений нулевая, тоже использует O(n) памяти. Прелесть этого алгоритма, что он работает за линейное время в отличие от сортировки.
Часто забывают об алгоритме Кахана, который не требует ни дополнительной памяти, ни почти не зависит от порядка сложения, зато достигает намного меньшей ошибки, а именно ~(2 * machine_eps + n * machine_eps^2)*сумму_модулей. Самый сок идёт от квадрата машинного эпсилон, что перебить количеством элементов становится уже сложнее (надо 10^16 и 10^32 элементов соответственно).
Сам алгоритм выглядит как переливание значений, но основная идея в том, что в наивном алгоритме большинство проблем происходят из-за сложения больших чисел с маленькими, надо подвигать мантиссу достаточно сильно и ошибка накапливается.
[1] Kahan summation wikipedia
[2] Лекция в Hamburg University про округления и KahanSummation доказательства
[3] Rust Kahan Summation crate
[4] ClickHouse KahanSum и документация по функции sumKahan
[5] Schewchuk algorithm for exact floating sum
[6] Theory behind floating point comparison
[7] What Every Computer Scientist Should Know About Floating-Point Arithmetic
Кейс: вы работаете с данными и считайте порог для их удаления. Доверять только одному процессу с удалением строго нельзя, поэтому часто делают кворумные джобы, где запускают много одинаковых бинарей, которые обязаны договориться о том, что данные можно удалять. Это позволяет выкладывать новый код на staging, не боясь, что данные удалятся (например, кворум не наберётся, если из 3 реплик мы выложим новый плохой код только на одну). Нередкие проблемы, которые я видел в проде своими глазами были связаны с тем, что удаления не могли договориться из-за того, что вокруг порога X одни джобы считали X - eps, другие X + eps. В итоге данные не удалялись и репортились в алёрт о том, что всё разъехалось, не страшно для людей, но бесит разработчиков.
Я настоятельно рекомендую, конечно же, сравнивать с eps в общем случае, но если уж не получается, то наука приготовила для нас интересные алгоритмы, которые позволяют уменьшить ошибку очень сильно. В наивном сложении после сложения n чисел будет ошибка ~machine_eps * n * сумму_модулей, где machine_eps — машинный эпсилон, для float это примерно 6*10^-8, для double это примерно 10^-16.
Самый лёгкий способ, это конечно, отсортировать числа с плавающей точкой как-нибудь и просуммировать, но как говорилось выше, это не всегда возможно из-за распределённых оптимизаций суммирования.
Другой способ это использовать алгоритм от Shewchuk, который просто сохраняет все ошибки в массив и их складывает, пока не договорится, что ошибка после всех округлений нулевая, тоже использует O(n) памяти. Прелесть этого алгоритма, что он работает за линейное время в отличие от сортировки.
Часто забывают об алгоритме Кахана, который не требует ни дополнительной памяти, ни почти не зависит от порядка сложения, зато достигает намного меньшей ошибки, а именно ~(2 * machine_eps + n * machine_eps^2)*сумму_модулей. Самый сок идёт от квадрата машинного эпсилон, что перебить количеством элементов становится уже сложнее (надо 10^16 и 10^32 элементов соответственно).
Сам алгоритм выглядит как переливание значений, но основная идея в том, что в наивном алгоритме большинство проблем происходят из-за сложения больших чисел с маленькими, надо подвигать мантиссу достаточно сильно и ошибка накапливается.
float Naive(const std::vector<float>& v) {
float sum = 0;
for (const float f : v) {
sum += f; // Problem that 'sum' can be big and 'f' is small.
}
return sum;
}
float KahanSum(const std::vector<float>& v) {
float sum = 0.0; // Final sum
float err = 0.0; // Error compensation
float y; // v[i] - C
float t; // Temporary for sum
for (const float f : v) {
y = f - err; // Magic is here, error is compensated from input.
t = sum + y;
err = t - sum - y;
sum = t;
}
return sum;
}
Алгоритм требует в 4 раза больше float операций, но всё ещё векторизируется. Доказательство ошибки я выношу за рамки одного поста, оно сложное и даже написано в Кнуте. Плюсы от этого алгоритма в том, что теперь сравнивать можно с машинным epsilon, а не с достаточно большим как это было в обычном суммировании. Можно меньше боятся расхождений и делать более мягкие пороги на оценку с миллиардами элементов.[1] Kahan summation wikipedia
[2] Лекция в Hamburg University про округления и KahanSummation доказательства
[3] Rust Kahan Summation crate
[4] ClickHouse KahanSum и документация по функции sumKahan
[5] Schewchuk algorithm for exact floating sum
[6] Theory behind floating point comparison
[7] What Every Computer Scientist Should Know About Floating-Point Arithmetic