Проблема с точной работой с плавающей запятой в C

Ответ 1

Ваша проблема вызвана тем, что вы собираете слишком много условий без учета их размера. Одним из решений является логарифмы. Другое - сортировать свои индивидуальные условия. Во-первых, перепишем уравнение как 1/p = 1 + ∏((1-p_i)/p_i). Теперь ваша проблема в том, что некоторые из этих терминов малы, а другие большие. Если у вас слишком много мелких терминов подряд, вы будете переполнены, и при слишком большом количестве терминов вы переполните промежуточный результат.

Итак, не ставьте слишком много одного порядка в строке. Отсоедините термины (1-p_i)/p_i. В результате первым будет наименьший срок, последний самый большой. Теперь, если вы сразу их размножаете, у вас все равно будет недостаток. Но порядок расчета не имеет значения. Используйте два итератора в свою временную коллекцию. Один начинается с начала (т.е. (1-p_0)/p_0), другой в конце (т.е. (1-p_n)/p_n), а ваш промежуточный результат начинается с 1.0. Теперь, когда ваш промежуточный результат равен >= 1.0, вы берете термин с фронта, и когда ваш итоговый результат равен < 1.0 вы берете результат со спины.

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

Там, конечно, реальная возможность переполнения. Если вход совершенно не является спамом (p = 1E-1000), тогда 1/p будет переполняться, потому что ∏((1-p_i)/p_i) переполняется. Но поскольку термины сортируются, мы знаем, что промежуточный результат будет переполняться только, если ∏((1-p_i)/p_i) переполняется. Таким образом, если промежуточный результат переполняется, то последующая потеря точности отсутствует.

Ответ 2

Это часто случается в машинах. AFAIK, вы ничего не можете поделать с потерей точности. Поэтому, чтобы обойти это, мы используем функцию log и преобразуем деления и умножения в вычитания и дополнения, соответственно.

Я решил сделать математику,

Исходное уравнение:

Я немного изменяю его:

Взятие журналов с обеих сторон:

Пусть,

Подставив,

Следовательно, альтернативная формула для вычисления комбинированной вероятности:

Если вам нужно, чтобы я расширил это, оставьте комментарий.

Ответ 3

Вот трюк:

for the sake of readability, let S := p_1 * ... * p_n and H := (1-p_1) * ... * (1-p_n), 
then we have:

  p = S / (S + H)
  p = 1 / ((S + H) / S)
  p = 1 / (1 + H / S)

let`s expand again:

  p = 1 / (1 +  ((1-p_1) * ... * (1-p_n)) / (p_1 * ... * p_n))
  p = 1 / (1 + (1-p_1)/p_1 * ... * (1-p_n)/p_n)

Итак, в основном вы получите произведение довольно больших чисел (между 0 и, для p_i = 0.01, 99). Идея состоит в том, чтобы не умножать тонны небольших чисел друг на друга, чтобы получить, ну, 0, но сделать частное из двух небольших чисел. Например, если n = 1000000 and p_i = 0.5 for all i, указанный выше метод даст вам 0/(0+0), который равен NaN, тогда как предлагаемый метод даст вам 1/(1+1*...1), который равен 0.5.

Вы можете получить еще лучшие результаты, когда все p_i будут отсортированы, и вы соедините их в противоположном порядке (допустим p_1 < ... < p_n), тогда следующая формула получит еще лучшую точность:

  p = 1 / (1 + (1-p_1)/p_n * ... * (1-p_n)/p_1)

таким образом вы делите большие числители (малые p_i) с большими знаменателями (большие p_(n+1-i)) и малые числители с малыми знаменателями.

edit: MSalter предложил полезную дальнейшую оптимизацию в своем ответе. Используя это, формула выглядит следующим образом:

  p = 1 / (1 + (1-p_1)/p_n * (1-p_2)/p_(n-1) * ... * (1-p_(n-1))/p_2 * (1-p_n)/p_1)

Ответ 4

Попробуйте вычислить обратный 1/p. Это дает вам уравнение вида 1 + 1/(1-p1) * (1-p2)...

Если вы посчитаете появление каждой вероятности - похоже, что у вас есть небольшое количество возвращаемых значений, вы можете использовать функцию pow() - pow (1-p,хождения_of_p) * pow (1 -q, occences_of_q) - и избегать индивидуального округления с каждым умножением.

Ответ 5

Вы можете использовать вероятность в процентах или обещаниях:

doc_spam_prob= (numerator*100/(denom1+denom2));

или

doc_spam_prob= (numerator*1000/(denom1+denom2));

или используйте какой-либо другой коэффициент

Ответ 6

Я не силен в математике, поэтому не могу комментировать возможные упрощения формулы, которые могут устранить или уменьшить вашу проблему. Тем не менее, я знаком с прецизионными ограничениями длинных двойных типов, и я знаю несколько произвольных и расширенных математических библиотек точности для C. Проверьте:

http://www.nongnu.org/hpalib/ а также http://www.tc.umn.edu/~ringx004/mapm-main.html