Что является подходящим допуском для того, чтобы рассчитывать n чисел с плавающей запятой до 1 - PullRequest
Новая
       19

Что является подходящим допуском для того, чтобы рассчитывать n чисел с плавающей запятой до 1

0 голосов
/ 02 января 2019

У меня есть n чисел с плавающей точкой, которые должны равняться 1, каждый из которых может принимать любое значение от 0 до 1. Я хочу проверить, что они суммируют с 1, но учитывая неточности с числами FP, проверяя, что сумма == 1 не будет всегда работать.

Поэтому я хочу проверить, что Math.abs (sum - 1)

ОБНОВЛЕНИЕ: я понимаю, почему числа с плавающей точкой неточны, и я знаю, что могу обработать вероятности более точным способом. Я просто хочу понять немного больше о поплавках в частности.

ОБНОВЛЕНИЕ 2: числа с плавающей запятой суммируются с 1, если я рассматриваю их математически (например, 0,1 + ... + 0,1)

Ответы [ 2 ]

0 голосов
/ 04 января 2019

Этот вопрос поднимает ряд случаев, которые интересно исследовать.Ниже я написал некоторый материал, но это только отправная точка.

В этом ответе я использую условия:

  • Числа представлены в и арифметика выполняется в некотором IEEE-754 двоичный формат с плавающей запятой, использующий округление до ближайшего числа, связанного с четностью.
  • У нас есть последовательность чисел s 0 , с 1 , с 2 ,… с n -1 , в том формате, каждый из которых находится в (0, 1] и чья точная математическая сумма равна 1.

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

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

Определение: u - округление единицы, наибольшая ошибка, которая может возникнуть из-за округления чисел в [1, 2).В режиме округления до ближайшего значения u равно ½?.В режиме направленного округления, например, к бесконечности или к нулю, u равно ?.(В настоящее время я не рассматриваю иные режимы направленного округления.)

Порядок по наименьшему биту является точным.

Определение: завершающий один бит числа - это позициязначение наименее значимого 1 в его представлении.Например, если двоичное число с плавающей запятой равно 1,011 • 2 −5 , его завершающий один бит равен 0,001 • 2 −5 = 2 −8 .

Предположим, мы используем этот алгоритм для суммирования чисел:

  • Пусть S - набор, содержащий числа в последовательности.
  • Выберите любые два элемента a и b в S, у которых один завершающий бит не больше, чем у любых других элементов.
  • Замените a и b в S с вычисленной суммой a и b .
  • Повторяйте, пока S не содержит один элемент.

Число, оставшееся в Sравно 1, без ошибок.

Доказательство:

  • Если какой-то элемент a в S имеет завершающий бит, который меньше 1 и не больше чемзавершающий бит любого другого элемента в S, должен быть какой-то другой элемент b в S с таким же завершающим битом.Это необходимо, поскольку сумма всех элементов равна 1, поэтому сумма наименьших ненулевых битов должна быть равна нулю в этой позиции - не может быть нечетного числа 1 бит.
  • Сумма двухчисло не более чем в два раза больше большего числа, поэтому старший бит суммы a и b не более чем на одну позицию выше, чем старший бит любого из них.Но их завершающие однобитные суммы равны нулю, поэтому конечный бит суммы по меньшей мере на одну позицию выше, поэтому ширина точной суммы составляет самое большее ширины более широкого операнда, поэтому она точно представима, а вычисленная суммаявляется точным.
  • Таким образом, все арифметические операции в алгоритме являются точными, поэтому окончательная сумма является точной.

Сортировка по величине

Предположим, что числасортируются в порядке возрастания, и мы добавляем их последовательно: S 0 = s 0 , S 1 = S 0 + s 1 , S 2 = S 1 + s 2 ,… S n −1 = S n −2 + s n −1 .Здесь S i представляют точные математические суммы.Пусть T i будут значения, которые мы получим, выполняя тот же алгоритм с использованием арифметики с плавающей точкой.Это хорошо известная методика уменьшения ошибки округления при вычислении суммы набора чисел.

Ограничение на ошибку в сложении, которое выдает каждый T i - UT i .Для этого начального анализа я буду считать, что США i адекватно приблизительно США i .Тогда предел общей ошибки составляет сШ i , суммированных по i , исключая i = 0 (посколькунет ошибки в настройке S 0 до s 0 ; первое добавление происходит с S 1 ), который я напишу как сумму( США i ).

Это равно u сумме ( S я ).И сумма ( S i ) = S 1 + S 2 +… S n −1 = ( s 0 ) + (с 0 + с 1 ) + ( с 0 + с 1 + с 2 ) + ... = ( n -2) • с 0 + ( n -2) • с 1 + ( n −3) • с 2 + 1 • с n -1 .Допуская любые действительные значения в [0, 1], эта сумма максимизируется, когда с 0 и оставшиеся с i все 1 / ( n -1).Этого нельзя достичь, учитывая наше требование, что значения находятся в (0, 1], и ограничения формата с плавающей запятой могут также предотвратить это, но это дает большую сумму, чем могли бы обеспечить значения с плавающей запятой, поэтому он остаетсядействительная граница (без учета более ранней идентификации T i с S i ).

Тогда сумма (S i ) является суммой арифметической последовательности n −1 чисел из 1 / (n -1) до 1, поэтому их сумма равна ½ (1 / ( n -1) + 1) • ( n -1), и наша оценка вошибка u • ½ (1 / ( n -1) + 1) • ( n -1) = ½ un .

Таким образом, при добавлении миллиона чисел мы можем ожидать максимальную ошибку около 250 000 (. (Опять же, мы приблизились, приняв S i заменяет T i .) Типичная ошибка, конечно, будет намного меньше.

Обратите внимание, что это только вывод одной границы,Другие соображения, не рассмотренные выше, могут дополнительно ограничить ошибку.Например, если n равно 2 149 при использовании базовой 32-разрядной двоичной плавающей запятой IEEE-754, предел выше будет 2 147 .Однако ограничения проблемы требуют, чтобы каждый s i был точно 2 -149 , в этом случае T 2 24 -1 равно 2 −125 (ошибки еще не было), но затем каждый последующий T i также равно 2 −125 из-за округления (добавление 2 −149 к 2 −125 дает 2 -125 из-за точности), поэтому конечный результат равен 2 -125 , что означает ошибку 1-2 -125 , что намного меньше, чем 2 147 .

Произвольный порядок

Предположим, что мы не контролируем заказ и должны добавить числа в указанном порядке.Максимальная ошибка при добавлении любых двух чисел в (0, 1) составляет ½ u , поэтому общая ошибка при первом добавлении n -2 составляет ½ u (* 1 407 * п -2).Окончательное добавление может привести к 1, поэтому его ошибка округления ограничена u , необязательно ½ u , поэтому общая ошибка связана с ½ u ( n −2) + u = ½ un .

Обсуждение

Такая же оценка была получена для отсортированного сложения, какдля произвольного порядка.Одна из причин заключается в том, что в отсортированном сложении используется ошибка округления u алгебраически, в uS i , в то время как произвольное упорядочение дает преимуществоиз того факта, что все числа в [½, 1) имеют ошибку округления не более ½u - в нем используется нижняя часть интервала, тогда как в отсортированном проходе сложения используется пропорция.Таким образом, сортированный сложный вывод может быть улучшен.Кроме того, в худшем случае все числа равны, что означает, что сортировка не приносит никакой пользы.В целом сортировка улучшит ошибки.

Поведение отрицательных и положительных ошибок будет асимметричным, поэтому их следует рассматривать отдельно.

0 голосов
/ 02 января 2019

Да, можно определить максимально возможную «ошибку», используя числа с плавающей запятой фиксированной точности для сложения.

Однако результат этого анализа не будет полезным значением для эпсилона.

Рассмотрим следующий пример: 

float a = 1.0E-37f;
float b = Float.MIN_VALUE;

System.out.println((a+b) == a);
System.out.println(a);
System.out.println(1.0f - a);

Это печатает: 

true
1.0E-37
1.0

Итак, если вы выполните произвольное количество сложений от Float.MIN_VALUE до 1.0E-37f, разница в сумме с 1.0f все равно будет 1.0f.

Это показывает, что максимальная ошибка, вносимая конечной точностью, равна сумме, которая может составить 1.0 при использовании бесконечной точности, на самом деле 1.0f - очевидно, что это бесполезно в качестве эпсилона.Определение полезного эпсилона возможно только тогда, когда известны требования к тому, что является «достаточно хорошим» - это зависит от того, для чего вы хотите использовать результат, и на него нельзя ответить вообще.

Конечновышеприведенный пример немного надуманный, поскольку он подчеркивает наихудший сценарий, который может оказаться невозможным в вашем случае, в зависимости от фактических значений n.

, как @EricPostpischil упоминает в комментариях

максимальная ошибка добавления любых двух чисел в [0, 1] равна ½ ULP (½), и существует n − 1 сложений, поэтому общая ошибка не более (n − 1)• ½ • ULP (½).

Как видно из этой формулы, для значения n требуется большое значение *1033*.(Возможно, вы заметили, что я выбрал относительно небольшие значения в моем примере - их нужно сложить, чтобы сложить до 1).

Ввод некоторых чисел: 

int n = 33554433;
System.out.println((n-1)*0.5*Math.ulp(0.5f));

Выход 

1.0

Если ваш n намного ниже или вы знаете о дополнительных ограничениях ваших входных чисел, о которых вы еще не сказали, возможно, можно получить гораздо более полезную верхнюю границу для ошибки.

Однако моя точка зрения остается неизменной - хотя знание об этой верхней границе может быть полезным, ее нельзя использовать в качестве эпсилона для проверки того, что значение в целом "достаточно хорошо".

...