Минимизация влияния ошибок округления, вызванных повторяющимися операциями, эффективно - PullRequest
7 голосов
/ 14 сентября 2010

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

Спасибо

Ответы [ 3 ]

6 голосов
/ 14 сентября 2010

Вычитание обычно обрабатывается с помощью метода Кахана.

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

Если у вас есть FMA (слитное умножение-сложение), это легко сделать следующим образом:

p = a*b;
r = fma(a,b,-p);

После этих двух операций, если переполнение или переполнение не происходит, p + r точно равно a * b без округления.Это также может быть достигнуто без FMA, но это гораздо сложнее.Если вас интересуют эти алгоритмы, вы можете начать с загрузки crlibm документации , в которой подробно описаны некоторые из них.

Деление ... ну, лучше избегать деления.Деление происходит медленно, а компенсированное деление происходит еще медленнее.Вы можете сделать это, но это безжалостно сложно без FMA, и нетривиально с этим.Лучше разрабатывать свои алгоритмы, чтобы как можно больше избегать его.

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

2 голосов
/ 14 сентября 2010

Разработка алгоритмов так, чтобы они были численно устойчивыми - это самостоятельная академическая дисциплина и область исследований. Это не то, что вы можете делать (или изучать) осмысленно с помощью «шпаргалок» - это требует определенных математических знаний и должно быть сделано для каждого конкретного алгоритма. Если вы хотите узнать, как это сделать, ссылка в статье в Википедии звучит довольно неплохо: Николас Дж. Хайам, Точность и стабильность численных алгоритмов, Общество промышленной и прикладной математики, Филадельфия, 1996. ISBN 0-89871-355- 2.

Относительно простой способ диагностики стабильности алгоритма заключается в использовании интервальной арифметики .

0 голосов
/ 14 сентября 2010

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

...