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

Question

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

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

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

EDIT: Я использую double тип данных. Числа генерируются с помощью метода .

EDIT 2: Кажется, мне нужно вычислить ошибку, основанную на том, как генерируются числа с плавающей запятой, которые я использую. Метод nextDouble() выглядит следующим образом:

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

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

Answer 1

Ошибка наихудшего случая округления при одной простой операции составляет половину разрыва между парой удвоений, которая скопирует результат действительного числа операции. Результаты метода RandomDouble от «from the range 0.0d (inclusive) to 1.0d (exclusive)». Для этих чисел наибольший разрыв составляет около 1e-16, а наихудшая ошибка округления - около 5e-17.

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

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 

Это полностью сделано, но вы получите точку.Дело в том, разница в величине между с и 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) 

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