предотвратить долгосрочное усреднение от переполнения?

Question

предположим, что я хочу вычислить среднее значение набора данных, например

class Averager {
   float total;
   size_t count;
   float addData (float value) {
       this->total += value;
       return this->total / ++this->count;
   }
}

рано или поздно значение total или count будет переполнено, поэтому я делаю так, чтобы общее значение не запоминалось на:

class Averager {
   float currentAverage;
   size_t count;
   float addData (float value) {
       this->currentAverage = (this->currentAverage*count + value) / ++count;
       return this->currentAverage;
   }
}

кажется, что они будут переполняться дольше, но умножение между average и count приводит к проблеме переполнения, поэтому следующее решение:

class Averager {
   float currentAverage;
   size_t count;
   float addData (float value) {
       this->currentAverage += (value - this->currentAverage) / ++count;
       return this->currentAverage;
   }
}

кажется лучше, следующая проблема - как предотвратить переполнение count?

Answer 1

Агрегированные ведра.

Мы выбираем размер корзины, который комфортно меньше, чем squareRoot (MAXINT). Для простоты давайте выберем 10.

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

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

Чтобы вычислить общее среднее значение, мы сначала вычисляем среднее значение «10», а затем объединяем это с «100». Этот шаблон повторяется для "1000", "10 000" и так далее. На каждом этапе нам нужно рассмотреть только два уровня, на 10 раз больше предыдущего.

Answer 2

Используйте double total; unsigned long long count;.Вы все еще должны беспокоиться о точности, но это будет гораздо меньше проблем, чем с float.

Answer 3

Вы хотите использовать алгоритм суммирования Кахана:

http://en.wikipedia.org/wiki/Kahan_summation_algorithm

См. Также раздел об ошибках суммирования в " Что должен знать каждый специалист по вычислительной технике об арифметике с плавающей точкой "

http://docs.sun.com/source/806-3568/ncg_goldberg.html#1262

Answer 4

А как насчет использования арифметики с произвольной точностью?

В Википедии есть список библиотек, которые вы можете использовать: http://en.wikipedia.org/wiki/Bignum#Libraries

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

Answer 5

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