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

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

В проведенном мною эксперименте кажется, что ограничения 1e-11 достаточно.

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

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

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

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

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


java rounding floating-point floating-accuracy rounding-error
person user2340939    schedule 17.06.2015    source источник
comment
Каков диапазон величин ваших чисел?   -  person Patricia Shanahan    schedule 17.06.2015
comment
Это имеет значение? Разве не единственное, что имеет значение десятичная часть, не имеющая отношения к тому, насколько велики числа? Но чтобы ответить вам, он может быть разным в зависимости от ввода. Диапазон может быть [0–100] или [0–10000].   -  person user2340939    schedule 17.06.2015
comment
en.wikipedia.org/wiki/Machine_epsilon Machine Epsilon - это технический термин, который вам нужен; на странице Википедии также обсуждаются некоторые способы вычисления машинного эпсилон. Не уверен, что это то, что вы ищете.   -  person lmcphers    schedule 17.06.2015
comment
Да, это имеет значение, поскольку это числа с плавающей запятой. Если у вас есть числа около 1e90, вы не увидите, чтобы что-либо изменилось в районе 10e-11 или даже 10e30.   -  person Sami Kuhmonen    schedule 17.06.2015
comment
Вы правы. @lmcphers, похоже, это именно то, что я ищу.   -  person user2340939    schedule 17.06.2015
comment
Я знаком с проблемами округления и их логикой, в любом случае спасибо.   -  person user2340939    schedule 17.06.2015
comment
В этом случае вы можете найти этот вопрос и ответы на StackOverflow, которые проливают свет на дальнейшее исследование этой темы. Извините, я ничем не могу больше помочь, кроме как указывать вам в правильном направлении. Удачи в вашей программе! stackoverflow.com/questions/28743401/   -  person lmcphers    schedule 17.06.2015
comment
@ user2340939: Зависит от того, насколько увеличиваются ваши числа. Если вы дойдете до верхних границ того, что может представлять double, ваша абсолютная ошибка для одной операции может быть порядка 10 ^ 292.   -  person Louis Wasserman    schedule 17.06.2015
comment
Как вы думаете, почему одна граница ошибки будет работать во всех ситуациях? Численный анализ немного сложнее. :-)   -  person Mark Dickinson    schedule 17.06.2015

Ответы (2)


arrow_upward
2
arrow_downward

Наихудшая ошибка округления для одиночной простой операции - это половина разрыва между парой двойных чисел, которые заключают в скобки результат действительного числа операции. Результаты метода nextDouble от Random: "из диапазон от 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

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

person Patricia Shanahan    schedule 17.06.2015

arrow_upward
0
arrow_downward

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

  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)

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

person kutschkem    schedule 17.06.2015
comment
Итак, в основном, что вам нужно сделать, это просто суммировать конкретные задействованные числа (или, если числа находятся в определенном диапазоне, сумму наименьших возможных значений чисел в операции), и вы получите наибольшую возможную ошибку для указанного числа с плавающей запятой. точечные операции (или экспериментируя, как я)? - person user2340939; 18.06.2015
comment
@ user2340939 Являются ли числа, которые вы используете в своем эксперименте (случайно сгенерированные из nextDouble ()), репрезентативными для чисел, которые действительно будут встречаться в вашей программе? Если да, то как вы оцениваете ошибку? Вычислить один раз с BigDecimal и один раз с двойным? Кроме того, действительно ли это самая большая возможная ошибка, которую вы ищете, или что-то вроде того, с вероятностью 99,99% ошибка не больше x? - person kutschkem; 18.06.2015
comment
После прочтения комментариев ошибка с вероятностью 99,99% не превышает x. И да, я вычисляю один раз с BigDecimal и один раз с двойным. - person user2340939; 08.07.2015