Saturday, May 25, 2013

Почему в современных языках программирование нет типа данных для рациональных чисел?

Если используется арифметика с плавающей запятой, там все вычисления производятся с округлениями. Более того, ни всякое действительно число может быть адекватно представлено как машинный тип данных. Начнем с того, что действительные числа "недискретны", в то время как числа с плавающей запятой таковыми являются. В частности, можно представить действительные числа с точностью до одного ULP-a (или половины, я уже точно не помню...). Т.е. машина не различает целые интервалы чисел, при чём длина такого интервала различна, зависит от "масштаба". Можно и не лезть в такие дебри, а рассмотреть более простые примеры. Классический пример, число 0.1, которое в двоичной системе счисления имеет бесконечное (периодическое) представление (та же проблема с числом 1/3, которое 0.333333...).

Ниже есть продолжение.

В случае с числом 0.1, при использование fix-point arithmetic, такое число легко представимо (пример, BigDecimal). Но у BigDecimal-а есть свои минусы, в частности, тоже число 1/3 не представимо

BigDecimal one = new BigDecimal("1");
BigDecimal three = new BigDecimal("3");
BigDecimal result = one.divide(three);
System.out.println(result);

Exception in thread "main" java.lang.ArithmeticException: Non-terminating decimal expansion; no exact representable decimal result.
   at java.math.BigDecimal.divide(BigDecimal.java:1616)

нужно использовать RoundingMode (или MathContext), т.е. мы возвращаемся опять к округлениям. Правда, в отличие от floating-point arithmetic, где у нас нет контроля как именно и куда они будут делаться, здесь у нас такой контроль появляется. Но это не особо помогает из-за следующих проблем. Допустим, наш input известен с точностью два знака после запятой, точность output тоже должна быть 2 знака после запятой, с какой точностью нужно делать вычисления? Тут мы наталкиваемся на две проблемы:

- техническая, BigDecimal (MathContext) оперируют термином precision - The number of digits to be used for an operation - количеством знаков используемых при операции, т.е. это включает в себя все знаки и до и после запятой, таким образом если мы оперируем как числами в диапазоне "тысяч" так и числами в диапазоне "миллиардов", нам нужен разный precision...

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

Всех этих сложностей можно избежать, если оперировать рациональными числами, почему этого не далают?

P.S. Мой друг получил разные ответы под Linux и Windows запустив один и тот же код на C++ из-за различий в округлениях типа double...

См. также:
Неожиданные эффекты арифметики с плавающей запятой с кодом на Java и ссылками на документацию.
О вреде округления
Rounding error on Professional Entry Test Sample Questions - тригером к написанию этого поста была математическая ошибка в "каком-то" тесте. В конце поста я привожу реальный пример, который иллюстрирует почему при input-е и output-е с заданной точностью промежуточные вычисления должны быть с большей точностью.
Пи равно трём. Часть II. - начинается с обсуждения об отличии рациональных и иррациональных чисел и заканчивается с описания эффекта "накопления погрешности" (см. предыдущею ссылку) при работе с калькулятором.


No comments:

Post a Comment