Как суммировать большое количество чисел с плавающей запятой?

Я создаю код суммарной суммы, чтобы суммировать большое количество чисел с плавающей запятой, после чего я обнаружил, что число цифр больше 100000000, результат пойдет не так. Затем я строю серийный код для сравнения. Серийный код также получает неправильный номер. Кто-нибудь знает почему? Спасибо!

мой простой код выглядит следующим образом.

результат "1.67772e + 007". Это должно быть 1e + 008

int main()
{
    size_t N=100000000;
    cout<<"n is : "<<N<<endl;
    clock_t start = clock();
    task_scheduler_init init;
    vector<float> myvec;
    vector<float>* pvec;
    for(int i=0;i<N;i++)
        myvec.push_back(1.0f);
    pvec=&myvec;
    float mysum;
    mysum=parallelSum(pvec);
    cout<<" the p sum is: "<<mysum<<endl;
    clock_t finish = clock();
        cout<<"Time Used  = "<<(finish - start)/CLOCKS_PER_SEC<<endl;
        mysum=0;
       for(int i=0;i<N;i++)
    mysum+=myvec[i];
        cout<<" the s sum is: "<<mysum<<endl;
    return 0;
}

Ответы

Ответ 1

Ваша проблема связана с ограниченной доступной точностью чисел с плавающей запятой.

Пока

1.0f + 1.0f == 2.0f,

Вы обнаружите, что

16777216.0f + 1.0f == 16777216.0f

Дополнительный 1.0f просто выброшен, так как 16777217 не может быть представлен в формате float.

Глядя на ваш результат - 1.67772e + 007 - ясно, что это именно то, что произошло.

Ожидаемый результат, 100000000.0, довольно много (6x) больше, чем 16777216.0f, но как только сумма достигает 16777216.0f, он остается там для остальных 8327884 дополнений 1.0f.

Решение: попробуйте использовать double вместо float, который доходит до 9007199254740992.0, прежде чем ударить эту проблему.

Почему?

В плавающей точке с одинарной точностью доступно только 24 бита точности, а 2 ^ 24 - 16777216. Невозможно кодировать 16777217 в 24 бит, поэтому он просто остается на уровне 16777216, исходя из того, что он достаточно близко к реальный ответ. Реальная проблема возникает, когда вы добавляете большое количество очень маленьких чисел в большое число, где сумма небольших чисел значима по отношению к большой, но индивидуально они не являются.

Обратите внимание, что 16777216.0f не является наибольшее число, которое может быть представлено в float, но просто представляет предел точности. Например, 16777216.0f x 2 ^ 4 + 2 ^ 4 = > 16777216.0f x 2 ^ 4

double имеет 53 бит точности, поэтому он может кодировать до 2 ^ 53 или 9007199254740992.0, прежде чем попасть в точку, в которой сбой 1.0d не выполняется.

Эта проблема также представляет собой еще одну опасность для параллельных операций с плавающей запятой - добавление с плавающей запятой не является ассоциативным, другими словами, ваш последовательный алгоритм:

Sum(A) = (...((((A1 + A2) + A3) + A4) ... A10000)

Может выдавать другой результат из параллелизированной версии:

Sum(A) = (...((((A1 + A2) + A3) + A4) ... A1000)
       + (...((((A1001 + A1002) + A1003) + A1004) ... A2000)
       + (...((((A2001 + A2002) + A2003) + A2004) ... A3000)
       ...
       + (...((((A9001 + A9002) + A9003) + A9004) ... A10000)

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

Это не означает, что это более правильно, но вы можете получить неожиданные результаты.

Если вам действительно нужно использовать float, попробуйте следующее:

  • сортируйте свои номера от большинства отрицательных до самых положительных (порядок (N log N))
  • добавить каждую пару по очереди: B1: = A1 + A2, B2: = A3 + A4, B3: = A5 + A6 это создает новый список B, наполовину длинный начальный
  • повторите эту процедуру на B, чтобы получить C, C, чтобы получить D и т.д.
  • остановитесь, когда осталось только один номер.

Обратите внимание, что это изменяет вашу алгоритмическую сложность от операции O (N) до операции O (N log N), но скорее дает правильное число. Это довольно параллелизуемо. Вы можете объединить операции сортировки и суммы, если вы умны в этом.

Ответ 2

Используйте алгоритм суммирования Kahan

  • Он имеет ту же самую алгоритмическую сложность, что и наивное суммирование
  • Это значительно повысит точность суммирования без необходимости переключения типов данных в два раза.

Я протестировал суммирование 100000000 поплавок 1.0f, используя std:: accumulate - результат был 1.67772e + 007. Однако, используя эту реализацию суммирования Кахана, результат был 1e + 008

template <class Iter>
float kahan_summation(Iter begin, Iter end) {
  float result = 0.f;

  float c = 0.f;
  for(;begin != end; ++begin) {
    float y = *begin - c;
    float t = result + y;
    c = (t - result) - y;
    result = t;
  }
  return result;
}

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

Ответ 3

Неточности IEEE754. Попробуйте GMP.

Ответ 4

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

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

Или найдите хорошую библиотеку для математики с произвольной точностью:)

Ответ 5

Алекс Браун отвечает отлично., Для полного объяснения проблем с плавающей запятой попробуйте this