Решения для ошибок округления с плавающей запятой

18

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

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

JNL
источник
2
Есть ли конкретная проблема, с которой вы столкнулись? Есть много способов сделать тестирование, хорошо для какой-то проблемы. Вопросы, которые могут иметь несколько ответов, плохо подходят для формата вопросов и ответов. Было бы лучше, если бы вы могли определить имеющуюся проблему таким образом, чтобы можно было получить один правильный ответ, а не создавать сеть для идей и рекомендаций.
Я строю приложение с большим количеством математических вычислений. Я понимаю, что тестирование NUNIT или JUNIT было бы хорошо, но хотелось бы иметь представление о том, как подходить к решению проблем с помощью математических вычислений.
JNL
1
Можете ли вы привести пример расчета, который вы будете тестировать? Обычно это не модульное тестирование по математике (если вы не тестируете свои собственные числовые типы), но тестирование чего-то подобного distanceTraveled(startVel, duration, acceleration)будет проверено.
Один пример будет иметь дело с десятичными точками. Например, скажем, мы строим стену со специальными настройками для dist x-0 до x = 14.589, а затем некоторые меры от x = 14.589 до x = конец стены. Расстояние .589 при преобразовании в двоичный файл не совпадает .... Особенно, если мы добавим несколько расстояний ... например, 14,589 + 0,25 не будет равно 14,84 в двоичном коде .... Надеюсь, это не смущает?
JNL
1
@MichaelT спасибо за редактирование Вопроса. Очень помогло. Поскольку я новичок в этом, не слишком хорош в том, как сформулировать вопросы. :) ... но скоро будет хорошо.
JNL

Ответы:

22

Существует три основных подхода к созданию альтернативных числовых типов, которые не имеют округления с плавающей запятой. Общая тема с ними заключается в том, что они используют целочисленную математику вместо этого различными способами.

Рациональные

Представьте число как целую часть и рациональное число с числителем и знаменателем. Число 15.589будет представлено как w: 15; n: 589; d:1000.

При добавлении к 0,25 (то есть w: 0; n: 1; d: 4) это включает вычисление LCM, а затем добавление двух чисел. Это хорошо работает во многих ситуациях, хотя может привести к очень большим числам, когда вы работаете со многими рациональными числами, которые взаимно просты между собой.

Фиксированная точка

У вас есть целая часть и десятичная часть. Все числа округлены (есть это слово - но вы знаете, где оно) с такой точностью. Например, вы могли бы иметь фиксированную точку с 3 десятичными знаками. 15.589+ 0.250становится добавлением 589 + 250 % 1000десятичной части (и затем любого переноса на целую часть). Это очень хорошо работает с существующими базами данных. Как уже упоминалось, есть округление, но вы знаете, где оно находится, и можете указать его так, чтобы оно было более точным, чем необходимо (вы измеряете только до 3 десятичных знаков, поэтому сделайте его фиксированным 4).

Плавающая фиксированная точка

Сохраните значение и точность. 15.589сохраняется как 15589для значения, так и 3для точности, а 0.25сохраняется как 25и 2. Это может обрабатывать произвольную точность. Я полагаю, что это то, что использует внутреннее устройство Java BigDecimal (не рассматривало его недавно). В какой-то момент вы захотите вернуть его из этого формата и отобразить его - и это может потребовать округления (опять же, вы контролируете, где оно находится).


Как только вы определились с выбором для представления, вы можете либо найти существующие сторонние библиотеки, которые используют это, либо написать свою собственную. При написании своего собственного текста обязательно протестируйте его и убедитесь, что вы правильно выполняете математику.


источник
2
Это хорошее начало, но, конечно, оно не полностью решает проблему округления. Иррациональные числа типа π, e и √2 не имеют строго числового представления; вам нужно представлять их символически, если вы хотите точное представление, или оценивать их как можно позже, если вы просто хотите минимизировать ошибку округления.
Калеб
@ Калеб для иррациональных чисел нужно было бы оценить их за пределы, где любое округление может вызвать проблемы. Например, 22/7 с точностью до 0,1% от пи, 355/113 с точностью до 10 ^ -8. Если вы работаете только с числами до 3 десятичных разрядов, наличие 3.141592653 должно избежать любых ошибок округления в 3 десятичных разрядах.
@MichaelT: для добавления рациональных чисел вам не нужно находить LCM, и это быстрее не делать (и быстрее отменять "LSB нули" после, и полностью упрощать только когда это абсолютно необходимо). В целом, для рациональных чисел обычно используется только «числитель / знаменатель» или «числитель / знаменатель << экспонента» (а не «целая часть + числитель / знаменатель»). Также ваша «плавающая фиксированная точка» является представлением с плавающей запятой, и ее лучше описать как «плавающую точку произвольного размера» (чтобы отличить ее от «плавающей запятой фиксированного размера»).
Брендан
некоторые из вашей терминологии немного сомнительны - плавающая фиксированная точка не имеет смысла - я думаю, вы пытаетесь сказать плавающая десятичная дробь.
JK.
10

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

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

Мейсон Уилер
источник
Я использую VC ++ прямо сейчас ... Но я был бы признателен за дополнительную информацию о других языках программирования.
JNL
Даже без значений с плавающей точкой вы все равно столкнетесь с круглыми проблемами.
Чад
2
@ Правда, но цель не в том, чтобы устранить проблемы округления (которые будут существовать всегда, потому что в любой используемой вами базе есть некоторые числа, которые не имеют точного представления, и у вас нет бесконечной памяти и вычислительной мощности), это уменьшите его до такой степени, что он не влияет на вычисления, которые вы пытаетесь выполнить.
Икер
@ Айкер Ты прав. Хотя вы, ни человек, задающий вопрос, не уточнили, каких именно расчетов они пытаются достичь и какую точность они хотят. Он должен ответить на этот вопрос, прежде чем перейти к теории чисел. Просто говорить lot of mathematical calculationsне полезно, ни ответы даны. В подавляющем большинстве случаев (если вы не имеете дело с валютой), тогда float должно быть достаточно.
Чад
@ Честно говоря, данных от ОП недостаточно, чтобы сказать, какой именно уровень точности им нужен.
Икер
7

Арифметика с плавающей точкой обычно довольно точна (15 десятичных цифр для a double) и довольно гибка. Проблемы возникают, когда вы занимаетесь математикой, что значительно уменьшает количество разрядов точности. Вот некоторые примеры:

  • Отмена на вычитание: 1234567890.12345 - 1234567890.12300 результат 0.0045имеет только две десятичных цифры точности. Это поражает всякий раз, когда вы вычитаете два числа одинаковой величины.

  • Глотание точности: 1234567890.12345 + 0.123456789012345 оценивается 1234567890.24691, последние десять цифр второго операнда теряются.

  • Умножение: если вы умножите два 15-значных чисел, результат будет иметь 30 цифр, которые необходимо сохранить. Но вы не можете хранить их, поэтому последние 15 бит потеряны. Это особенно утомительно, когда в сочетании сsqrt() (как в sqrt(x*x + y*y): Результат будет иметь только 7,5 цифр точности.

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

for(double f = f0; f < f1; f += df) {

После нескольких итераций большая fчасть поглотит часть точностиdf . Хуже того, ошибки будут накапливаться, что приведет к противоречивой ситуации, что меньшее dfможет привести к худшим общим результатам. Лучше напиши это:

for(int i = 0; i < (f1 - f0)/df; i++) {
    double f = f0 + i*df;

Поскольку вы комбинируете приращения в одном умножении, полученное значение fбудет с точностью до 15 десятичных цифр.

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

cmaster - восстановить монику
источник
2

Как убедиться, что у вас нет проблем: узнайте о арифметических задачах с плавающей точкой, или наймите кого-нибудь, кто имеет, или используйте здравый смысл.

Первая проблема - точность. Во многих языках у вас есть «float» и «double» (двойное положение для «двойной точности»), и во многих случаях «float» дает вам точность около 7 цифр, в то время как double дает вам 15. Здравый смысл заключается в том, что если у вас есть В ситуации, когда точность может быть проблемой, 15 цифр намного лучше, чем 7 цифр. Во многих слегка проблемных ситуациях использование «double» означает, что вам это сойдет с рук, а «float» означает, что вы этого не сделаете. Допустим, рыночная капитализация компании составляет 700 миллиардов долларов. Представьте это в формате с плавающей запятой, и младший бит составляет $ 65536. Представьте его, используя double, а младший бит составляет около 0,012 цента. Поэтому, если вы действительно, действительно не знаете, что делаете, вы используете double, а не float.

Вторая проблема в большей степени принципиальная. Если вы делаете два разных вычисления, которые должны давать один и тот же результат, они часто этого не делают из-за ошибок округления. Два результата, которые должны быть равны, будут «почти равны». Если два результата близки друг к другу, то реальные значения могут быть равны. Или они могут не быть. Вы должны помнить об этом и должны писать и использовать функции, которые говорят «x определенно больше, чем y» или «x определенно меньше, чем y» или «x и y могут быть равны».

Эта проблема становится намного хуже, если вы используете округление, например, «округлить x до ближайшего целого числа». Если вы умножите 120 * 0,05, результат должен быть 6, но вы получите «некоторое число, очень близкое к 6». Если затем вы «округлите до ближайшего целого числа», это «число, очень близкое к 6», может быть «немного меньше 6» и округлено до 5. И обратите внимание, что не имеет значения, насколько точна ваша точность. Не имеет значения, насколько близок к 6 ваш результат, если он меньше 6.

И в-третьих, некоторые проблемы сложны . Это означает, что нет простого и быстрого правила. Если ваш компилятор поддерживает «long double» с большей точностью, вы можете использовать «long double» и посмотреть, имеет ли это значение. Если это не имеет значения, то либо у вас все в порядке, либо у вас есть действительно сложная проблема. Если это имеет значение, которое вы ожидаете (например, изменение с 12-го знака после запятой), то вы, вероятно, в порядке. Если это действительно меняет ваши результаты, то у вас есть проблема. Просить помощи.

gnasher729
источник
1
В математике с плавающей запятой нет ничего «здравого смысла».
whatsisname
Узнайте больше об этом.
gnasher729
0

Большинство людей совершают ошибку, когда видят двойное, они кричат ​​BigDecimal, хотя на самом деле они просто перенесли проблему в другое место. Double дает знак бита: 1 бит, экспонента ширина: 11 бит. Значимость и точность: 53 бита (52 явно хранятся). Из-за двойного характера, чем больше целое число, вы теряете относительную точность. Для расчета относительной точности мы используем здесь ниже.

Относительная точность удвоения в расчете мы используем следующую foluma 2 ^ E <= abs (X) <2 ^ (E + 1)

epsilon = 2 ^ (E-10)% для 16-разрядного числа с плавающей запятой (половина точности)

 Accuracy Power | Accuracy -/+| Maximum Power | Max Interger Value
 2^-1           | 0.5         | 2^51          | 2.2518E+15
 2^-5           | 0.03125     | 2^47          | 1.40737E+14
 2^-10          | 0.000976563 | 2^42          | 4.39805E+12
 2^-15          | 3.05176E-05 | 2^37          | 1.37439E+11
 2^-20          | 9.53674E-07 | 2^32          | 4294967296
 2^-25          | 2.98023E-08 | 2^27          | 134217728
 2^-30          | 9.31323E-10 | 2^22          | 4194304
 2^-35          | 2.91038E-11 | 2^17          | 131072
 2^-40          | 9.09495E-13 | 2^12          | 4096
 2^-45          | 2.84217E-14 | 2^7           | 128
 2^-50          | 8.88178E-16 | 2^2           | 4

Другими словами, если вы хотите Точность +/- 0,5 (или 2 ^ -1), максимальный размер, который может быть числом, составляет 2 ^ 52. Любое значение больше этого, а расстояние между числами с плавающей точкой больше 0,5.

Если вы хотите получить точность +/- 0,0005 (около 2 ^ -11), максимальный размер, который может быть указан, равен 2 ^ 42. Любое значение больше этого, а расстояние между числами с плавающей запятой больше 0,0005.

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

Хотя это то, что нужно сказать, если вы стремитесь симулировать мир размером 100 на 100 метров, у вас будет где-то порядок порядка 2 ^ -45. Это даже не относится к тому, как современные FPU внутри процессоров будут выполнять вычисления вне собственного размера шрифта, и только после завершения вычисления они будут округлять (в зависимости от режима округления FPU) до собственного размера шрифта.

Чад
источник