Когда имеешь дело с вещественными числами в первую очередь нужно подумать нельзя ли от них избавиться и перейти к целым. Причём умножение на какую-нибудь степень десятки по сути применимо только к числам из инпута, данным с фиксированной точностью. Если же даблы возникают в процессе вычислений, то стоит постараться преобразовать формулу, так, что бы они не возникали. Например не извлекать корни, не делить что-нибудь и т.д. Классический пример: у нас в процессе вычислений получились 2 числа: a/b и c/d. Нам надо сравнить их. Вместо (double)a / b < (double)c / d. Почти всегда стоит использовать форму a*d < c*b. Здесь погрешностей не будет. Но надо проследить, что бы a*d не переполнилось. И только если это произведение переполняет long long, то можно подумать о даблах... Но скорей всего это означает, что надо вывести другую формулу.
Эпсилон необходимо использовать ВСЕГДА, когда нас интересует равенство двух вещественных чисел. Короче, по сути вообще при любом сравнении. Исключение составляет разве что случай, когда равенство вообще невозможно. Например, когда нас интересует, что больше p^a или q^b, где p и q — простые. Мы напишем a*log(p) > b*log(q). Они точно не могут быть равны, значит эпсилон нам только помешает если значения близки. В остальных случаях — эпсилон обязателен.
Какой выбирать эпсилон? Большинство даже очень опытных команд всё-таки подгоняют эпсилон, когда не могут сдать задачу. По-этому точно разве что Бурундук скажет :) И то в половине случаев сам себя перемудрит :) Эпсилон должен быть меньше, чем точность требуемая в ответе. Но эпсилон должен быть больше чем лучшая точность, которую мы технически можем получить. Дабл вмещает 15 десятичных знаков. Допустим ответ по модулю не превосходит 10^8 и нам надо вывести его с 3 знаками после запятой. Тоесть эпсилон должен быть меньше 10^-3, но при этом больше 10^-7. Почему? Если он будет слишком большим, то мы не получим нужной точности, это очевидно. Если же он будет слишком маленьким, то он не учтётся в дабле. 10^9 + 10^-9 == 10^9. Потому что для того, что бы действительно произвести сложение и сохранить результат надо уже 18 десятичных знаков, а у нас в дабле их только 15, значит младшие (10^-9) отбросятся. В моём предыдущем примере у нас 8 знаков до запятой, соответственно после запятой остаётся только 7. Значит эпсилон не может быть меньше 10^-7. Тут, конечно, очень многое зависит от способов вычислений. Например если писать вещественный бинсёрч так: while (abs(l - r) > eps) {... то всё, что я писал полностью справедливо. Однако если писать его умней: while (d > eps) { c = l + d; d /= 2... то здесь можно взять вообще любое эпсилон. В качестве ещё одного совета — можно прикинуть погрешность и взять эпсилон где-нибудь на 2 разряда больше погрешности. Как прикинуть погрешность — придёт с опытом :)
самые худшие операции при работе с даблами — сложение и вычитание. Потому, что если мы складываем большое число с маленьким, то большое всегда останется, а младшие разряды маленького могут отброситься если не влезут в дабл. По-этому если, например, надо сложить много даблов, то лучше это делать в порядке их возрастания. И вообще стоит всячески избегать последовательных операций с даблами, которые ВСЕГДА приводят к накоплению ошибки. Например у нас есть цикл:
for (d1 = 0, d2 = 0, i = 0; i < 1000000; i ++) {
d1 = d1 + i / 1000000.0;
d2 = i * (i + 1) / 2.0 / 1000000.0
}
d2 будет гораздо точней d1.
Long double имеет смысл не использовать вообще никогда, так как на большинстве компиляторов он равен double. BidDecimal в Java — другое дело.
Даблы в качестве ключей для map тоже лучше не использовать. Обычно вместо них можно создать структуру из нескольких целочисленных полей. Это будет всегда правильно. Если уж использовать, то перегрузить оператор меньше для даблов: bool operator < (double a, dobule b) { return a < b — eps};
UPD: рекомендую обратить внимание на некоторые комментарии:
http://codeforces.net/blog/entry/6345#comment-117294
http://codeforces.net/blog/entry/6345#comment-117339 и комментарии к нему
Comments (0)
