Максимально возможная ошибка округления при вычислении чисел с плавающей точкой

Question

Я разрабатываю критичный ко времени алгоритм в Java и поэтому не использую BigDecimal, Для обработки ошибок округления я установил верхнюю границу ошибки, ниже которой разные числа с плавающей запятой считаются абсолютно одинаковыми. Теперь проблема в том, какой должна быть эта граница? Или, другими словами, что является самой большой возможной ошибкой округления, которая может возникнуть при выполнении вычислительных операций с числами с плавающей точкой (сложение с плавающей точкой, вычитание, умножение и деление)?

С экспериментом, который я сделал, кажется, что граница 1e-11 достаточно.

PS: эта проблема не зависит от языка.

РЕДАКТИРОВАТЬ: я использую double тип данных. Числа генерируются с Random"s nextDouble() метод.

РЕДАКТИРОВАТЬ 2: Кажется, мне нужно рассчитать ошибку на основе того, как генерируются числа с плавающей запятой, которые я использую. nextDouble() Метод выглядит так:

public double nextDouble() {
    return (((long)(next(26)) << 27) + next(27))
        / (double)(1L << 53); }

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

Answer 1

Наихудшая ошибка округления для одной простой операции - это половина промежутка между парой двойных чисел, которые ограничивают результат операции действительным числом. Результаты от метода nextDouble Рэндома " от диапазона 0,0d (включительно) до 1,0d (исключая)". Для этих чисел наибольший разрыв составляет около 1e-16, а наихудшая ошибка округления составляет около 5e-17.

Вот программа, которая печатает пробел для некоторых чисел выборки, включая наибольший результат для nextDouble Random:

public class Test {
  public static void main(String[] args) {
    System.out.println("Max random result gap: "
        + Math.ulp(Math.nextAfter(1.0, Double.NEGATIVE_INFINITY)));
    System.out.println("1e6 gap: "
        + Math.ulp(1e6));
    System.out.println("1e30 gap: "
        + Math.ulp(1e30));
  }
}

Выход:

Max random result gap: 1.1102230246251565E-16
1e6 gap: 1.1641532182693481E-10
1e30 gap: 1.40737488355328E14

В зависимости от выполняемого вами вычисления ошибки могут накапливаться в нескольких операциях, что дает большую общую ошибку округления, чем можно было бы предсказать из этого упрощенного подхода, состоящего из одной операции. Как отметил Марк Дикинсон в комментарии: "Численный анализ немного сложнее".

Answer 2

Это зависит от:

1. Ваш алгоритм
2. величина участвующих чисел

Например, рассмотрим функцию f(x) = a * ( b - ( c+ d))Ничего страшного или нет?

Оказывается, это когда d << c, b = c и все что угодно, но давайте просто скажем, что оно большое.

Скажем так:

a = 10e200
b = c = 5
d = 10e-90

Это полностью выдумано, но вы понимаете. Дело в том, что разница величин между c и d означает, что

c + d = c (small rounding error because d << c)
b - (c + d) = 0 (should be 10e-90)
a * (b - (c + d)) = 0 (where it really should be 10e110)

Короче говоря, некоторые операции (особенно вычитания) (могут) убить вас. Кроме того, вам нужно смотреть не столько на генерирующую функцию, сколько на операции с числами (ваш алгоритм).