Суммирование массива чисел с плавающей точкой

1 min


Добавить массив чисел просто: просто зациклите массив, добавив каждый элемент в аккумулятор.

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

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

Мы суммируем список чисел несколькими способами, используя C float тип, 32-разрядное целое число. Некоторые могут возразить, что это искусственно. Кто-нибудь использует floatбольше? Не двигался от float в double избавиться от всех наших проблем с точностью? Нет и нет

На самом деле, использование 32-разрядных float типы на подъеме. Перемещение данных в нехватку памяти – теперь узкое место, а не арифметические операции как таковые, и float позволяет вам упаковать больше данных в объем памяти. Кроме того, растет интерес к типам с плавающей запятой, даже меньшим, чем 32-разрядные числа с плавающей запятой. Смотрите следующие сообщения для примеров:

И хотя иногда вам нужна меньшая точность, чем 32 бита, иногда вам нужна большая точность, чем 64 бита. Смотрите, например, эта почта,

Теперь немного кода. Вот очевидный способ суммировать массив в C:

    float naive(float x(), int N) {
        float s = 0.0;
        for (int i = 0; i 

Kahan's algorithm is not much more complicated, but it looks a little mysterious and provides more accuracy.

    float kahan(float x(), int N) {
        float s = x(0);
        float c = 0.0;
        for (int i = 1; i 

Now to compare the accuracy of these two methods, we'll use a third method that uses a 64-bit accumulator. We will assume its value is accurate to at least 32 bits and use it as our exact result.

    double dsum(float x(), int N) {
        double s = 0.0;
        for (int i = 0; i 

For our test problem, we'll use the reciprocals of the first 100,000 positive integers rounded to 32 bits as our input. This problem was taken from (2).

    #include This produces the following output.

    12.0908508300781
    12.0901460647583
    12.0901461953972

Наивный метод верен до 6 значащих цифр, а метод Кахана верен до 9 значащих цифр. Ошибка в первом в 5394 раза больше. В этом примере метод Кахана максимально точен с использованием 32-битных чисел.

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

Но что если мы сделал хотите вычислить номер сотой гармоники? Есть методы для вычисления гармонических чисел напрямую, как описано Вот,

Похожие сообщения

(1) Число условий задачи в основном является мерой того, сколько ошибок с плавающей запятой умножаются в процессе вычисления результата. У хорошо обусловленной проблемы есть малое число условий, а у плохо обусловленной проблемы – большое число условий. При плохо обусловленных проблемах вам, возможно, придется использовать дополнительную точность в своих промежуточных вычислениях, чтобы получить результат, который является точным для обычной точности.

(2) Справочник по арифметике с плавающей точкой Джен-Мишель Мюллер и др.


0 Comments

Ваш e-mail не будет опубликован. Обязательные поля помечены *