Что такое хорошее решение для вычисления среднего числа, где сумма всех значений превышает пределы double?

(n ₁ + n ₂ + ... + n _k ) / k = (n ₁ + n ₂ ) / k + (n ₃ + n ₄ ) / k + ... + (n _{k- 1} + n _k ) / k, если k четно

(n ₁ + n ₂ + ... + n _{] k} ) / k = n ₁ / k + (n ₂ + n ₃ ) / k + ... + (n _k-1 + n _k ) / k, если k нечетное

См. Раздел кумулятивное скользящее среднее

Подумайте об этом:

avg(n1)         : n1                               = a1
avg(n1, n2)     : ((1/2)*n1)+((1/2)*n2)            = ((1/2)*a1)+((1/2)*n2) = a2
avg(n1, n2, n3) : ((1/3)*n1)+((1/3)*n2)+((1/3)*n3) = ((2/3)*a2)+((1/3)*n3) = a3

Итак, для любого набора удвоений произвольного размера вы можете сделать это (это в C #, но я почти уверен, что его можно легко перевести на Java):

static double GetAverage(IEnumerable<double> values) {
    int i = 0;
    double avg = 0.0;
    foreach (double value in values) {
        avg = (((double)i / (double)(i + 1)) * avg) + ((1.0 / (double)(i + 1)) * value);
        i++;
    }

    return avg;
}

На самом деле, это красиво упрощается до (уже предоставлено martinus):

static double GetAverage(IEnumerable<double> values) {
    int i = 1;
    double avg = 0.0;
    foreach (double value in values) {
        avg += (value - avg) / (i++);
    }

    return avg;
}

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

static IEnumerable<double> GetRandomDoubles(long numValues, double maxValue, int seed) {
    Random r = new Random(seed);
    for (long i = 0L; i < numValues; i++)
        yield return r.NextDouble() * maxValue;

    yield break;
}

И вот результаты нескольких тестовых испытаний:

long N = 100L;
double max = double.MaxValue * 0.01;

IEnumerable<double> doubles = GetRandomDoubles(N, max, 0);
double oldWay = GetAverage_old(doubles); // 1.00535024998431E+306
double newWay = GetAverage(doubles); // 1.00535024998431E+306

doubles = GetRandomDoubles(N, max, 1);
oldWay = GetAverage_old(doubles); // 8.75142021696299E+305
newWay = GetAverage(doubles); // 8.75142021696299E+305

doubles = GetRandomDoubles(N, max, 2);
oldWay = GetAverage_old(doubles); // 8.70772312848651E+305
newWay = GetAverage(doubles); // 8.70772312848651E+305

Хорошо, но как насчет значений 10 ^ 9?

long N = 1000000000;
double max = 100.0; // we start small, to verify accuracy

IEnumerable<double> doubles = GetRandomDoubles(N, max, 0);
double oldWay = GetAverage_old(doubles); // 49.9994879713857
double newWay = GetAverage(doubles); // 49.9994879713868 -- pretty close

max = double.MaxValue * 0.001; // now let's try something enormous

doubles = GetRandomDoubles(N, max, 0);
oldWay = GetAverage_old(doubles); // Infinity
newWay = GetAverage(doubles); // 8.98837362725198E+305 -- no overflow

Естественно, насколько приемлемо это решение, будет зависеть от ваших требований к точности. Но это стоит учитывать.

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

-

Подведите итог подсерии, отслеживая, сколько чисел вы съели, пока не приблизитесь к переполнению , затем возьмите среднее. Это даст вам среднее значение a0 и посчитайте n0. Повторяйте, пока не закончите список. Теперь у вас должно быть много ai, ni.

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

Вы можете комбинировать любое подмножество этих ai, ni, выбрав любой ni в подмножестве (назовем его np) и разделив все ni в подмножестве на это значение. Максимальный размер подмножеств для объединения - это примерно постоянное значение n.

ni / np должно быть близко к единице. Теперь просуммируйте ni / np * ai и умножьте на np / (sum ni), отслеживая сумму ni. Это дает вам новую комбинацию ni, ai, если вам нужно повторить процедуру.

Если вам нужно будет повторить (т. Е. Количество пар ai, ni намного больше, чем типичное ni), постарайтесь сохранить относительный n размеров константы путем объединения всех средних сначала на одном уровне n, затем объединения на следующем уровне и т. д.

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

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

Здесь мы переходим к алгоритму

public static double sum(double[] numbers) { 
  double eachSum, tempSum;
  double factor = Math.pow(2.0,30); // about as large as 10^9
  for (double each: numbers) {
    double temp = each / factor;
    if (t * factor != each) {
      eachSum += each;
    else {
      tempSum += temp;
    }
  }
  return (tempSum / numbers.length) * factor + (eachSum / numbers.length);
}

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

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

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

Двойное число можно разделить на степень 2 без потери точности. Итак, если ваша единственная проблема, это абсолютный размер суммы, вы можете предварительно масштабировать свои числа перед их суммированием. Но с набором данных такого размера все еще существует риск того, что вы столкнетесь с ситуацией, когда вы добавляете маленькие числа к большому, а маленькие числа в конечном итоге будут в основном (или полностью) игнорироваться.

, например, когда вы добавляете 2.2e-20 к 9.0e20, результат будет 9.0e20, потому что после того, как шкалы настроены так, что числа можно складывать вместе, меньшее число будет 0. Двойные числа могут содержать только около 17 цифр, и вам потребуется более 40 цифр, чтобы сложить эти два числа вместе без потерь.

Итак, в зависимости от вашего набора данных и того, сколько цифр точности вы можете позволить себе потерять, вам, возможно, придется сделать другие вещи. Разделение данных на наборы поможет, но лучший способ сохранить точность - это определить приблизительное среднее значение (возможно, вы уже знаете это число). затем вычтите каждое значение из приблизительного среднего, прежде чем суммировать его. Таким образом, вы суммируете расстояния от среднего, поэтому ваша сумма никогда не должна быть очень большой.

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

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

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

Уточните возможные диапазоны значений.

Учитывая, что у двойника диапазон ~ = +/- 10 ^ 308, и вы суммируете 10 ^ 9 значений, очевидное диапазон, предложенный в вашем вопросе, - это значения порядка 10 ^ 299.

Это кажется несколько, ну, маловероятным ...

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

Я также хотел бы отметить (поскольку никто другой не имеет ), что для любого набора чисел X :

mean(X) = sum(X[i] - c)  +  c
          -------------
                N

для любой произвольной константы c .

В этой конкретной задаче установка c = min (X) может резко снизить риск переполнения во время суммирования.

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

Вариант 1 - использовать библиотеку произвольной точности, чтобы у вас не было верхней границы.

Другие варианты (которые теряют точность) - это суммирование по группам, а не по всем один раз или разделить перед суммированием.

ИМХО, самый надежный способ решения ваша проблема

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

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

Самая первая проблема, которую я хотел бы задать вам, это:

• Вы заранее знаете количество значений?

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

     2   5   7/3
     - + - + ---
     y   y    y

Если y равно 3 для всех наборов, вы получите следующее:

     2   5   7/3
     - + - + ---
     3   3    3

что дает:

2*3   5*3    7
--- + --- + ---
 9     9     9

что составляет:

6   15   7
- + -- + -
9    9   9

что в сумме:

28
-- ~ 3,1111111111111111111111.........1111111.........
 9

Среднее значение 1-7, это 4. Очевидно, что это выиграло не работает. Обратите внимание: если вы выполните указанное выше упражнение с числами 1, 2, 3, 4, 5, 6, 7, 0, 0 (обратите внимание на два нуля в конце), то вы получите указанный выше результат.

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

Итак, вам нужны наборы одинакового размера . Не повезло, если исходный набор входных данных состоит из простого числа значений.

Но меня беспокоит потеря точности. Я'

разделите все значения на установленный размер и затем просуммируйте

Помимо использования уже предложенных более эффективных подходов, вы можете использовать BigDecimal для выполнения своих вычислений. (Имейте в виду, что это неизменный)

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

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

Я разместил ответ на вопрос , возникший из этого вопроса, понимая, что мой ответ лучше подходит на этот вопрос, чем на этот. Я воспроизвел его ниже. Однако я заметил, что мой ответ похож на комбинацию Bozho's и Anon_^.'s.

Так как другой вопрос был помечен языковой диагностикой, я выбрал C# для включенного мною примера кода. Относительная простота использования и легкий синтаксис, наряду с включением пары функций, облегчающих эту рутину (функция DivRem в BCL и поддержка итераторных функций), а также мое собственное знакомство с ним, сделали его хорошим выбором для этой задачи. Так как ОП здесь заинтересована в решении Java, Но я не достаточно хорошо владею Java, чтобы писать его эффективно, было бы неплохо, если бы кто-нибудь добавил перевод этого кода на Java.

Некоторые математические решения здесь очень хороши. Вот простое техническое решение.

Используйте больший тип данных. Это разбивается на две возможности:

1. Использовать высокоточную библиотеку с плавающей точкой. Тот, кто сталкивается с необходимостью усреднения миллиарда чисел, вероятно, имеет ресурсы для покупки, или мощность мозга для записи, 128-битной (или более) библиотеки с плавающей запятой.

   Я понимаю недостатки здесь. Это, безусловно, было бы медленнее, чем использование собственных типов. Вы все равно можете переплюнуть/не переплюнуть, если количество значений вырастет слишком высоко. Yada yada.

2. Если ваши значения являются целыми числами или могут быть легко масштабированы до целых чисел, держите вашу сумму в списке целых чисел. Когда вы переполните список, просто добавьте еще одно целое число. Это, по сути, упрощенная реализация первого варианта. Простой (непроверенный) пример на C# следует

class BigMeanSet{
    List<uint> list = new List<uint>();

    public double GetAverage(IEnumerable<uint> values){
        list.Clear();
        list.Add(0);

        uint count = 0;

        foreach(uint value in values){
            Add(0, value);
            count++;
        }

        return DivideBy(count);
    }

    void Add(int listIndex, uint value){
        if((list[listIndex] += value) < value){ // then overflow has ocurred
            if(list.Count == listIndex + 1)
                list.Add(0);
            Add(listIndex + 1, 1);
        }
    }

    double DivideBy(uint count){
        const double shift = 4.0 * 1024 * 1024 * 1024;

        double rtn       = 0;
        long   remainder = 0;

        for(int i = list.Count - 1; i >= 0; i--){
            rtn *= shift;
            remainder <<= 32;
            rtn += Math.DivRem(remainder + list[i], count, out remainder);
        }

        rtn += remainder / (double)count;

        return rtn;
    }
}

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

Это должно обеспечить столько точности, сколько может представить двойник, и должно работать для любого количества 32-битных элементов, до 2³² - 1. Если нужно больше элементов, то переменная count должна быть расширена и функция DivideBy будет усложнена, но я оставлю это упражнением для читателя.

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

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

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

Я протестировал его, сначала пропустив через 1000 наборов случайной длины (в диапазоне от 1 до 1000), заполненных случайными числами (в диапазоне от 0 до 2³² - 1). Это были наборы, для которых я мог легко и быстро проверить точность, также запустив на них каноническое среднее.

Затем я тестировал с помощью 100^* больших серий, со случайной длиной от 10⁵ до 10⁹. Нижняя и верхняя границы этих рядов также были выбраны случайным образом, ограниченным так, чтобы ряд укладывался в диапазон 32-битного целого. Для любых серий результаты легко поддаются проверке как (нижняя граница + верхняя) / 2.

_{^{*Хорошо, это небольшая белая ложь. Я прервал тест большой серии примерно после 20 или 30 успешных запусков. Серия длиной 109 заняла чуть меньше полутора минут на моей машине, так что примерно получаса тестирования этой рутины хватило на мои вкусы.}}

Для тех, кому интересно, мой тестовый код приведен ниже:

static IEnumerable<uint> GetSeries(uint lowerbound, uint upperbound){
    for(uint i = lowerbound; i <= upperbound; i++)
        yield return i;
}

static void Test(){
    Console.BufferHeight = 1200;
    Random rnd = new Random();

    for(int i = 0; i < 1000; i++){
        uint[] numbers = new uint[rnd.Next(1, 1000)];
        for(int j = 0; j < numbers.Length; j++)
            numbers[j] = (uint)rnd.Next();

        double sum = 0;
        foreach(uint n in numbers)
            sum += n;

        double avg = sum / numbers.Length;
        double ans = new BigMeanSet().GetAverage(numbers);

        Console.WriteLine("{0}: {1} - {2} = {3}", numbers.Length, avg, ans, avg - ans);

        if(avg != ans)
            Debugger.Break();
    }

    for(int i = 0; i < 100; i++){
        uint length     = (uint)rnd.Next(100000, 1000000001);
        uint lowerbound = (uint)rnd.Next(int.MaxValue - (int)length);
        uint upperbound = lowerbound + length;

        double avg = ((double)lowerbound + upperbound) / 2;
        double ans = new BigMeanSet().GetAverage(GetSeries(lowerbound, upperbound));

        Console.WriteLine("{0}: {1} - {2} = {3}", length, avg, ans, avg - ans);

        if(avg != ans)
            Debugger.Break();
    }
}

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

long int i = 0; двойное среднее = 0; пока (есть еще элементы) { среднее = среднее * (i / i + 1) + X [i] / (i + 1); i ++; } средний доход;