Средняя функция без исключения переполнения

Question

.NET Framework 3.5.
Я пытаюсь вычислить среднее значение некоторых довольно больших чисел.
Например:

using System;
using System.Linq;

class Program
{
    static void Main(string[] args)
    {
        var items = new long[]
                        {
                            long.MaxValue - 100, 
                            long.MaxValue - 200, 
                            long.MaxValue - 300
                        };
        try
        {
            var avg = items.Average();
            Console.WriteLine(avg);
        }
        catch (OverflowException ex)
        {
            Console.WriteLine("can't calculate that!");
        }
        Console.ReadLine();
    }
}

Очевидно, математический результат - 9223372036854775607 (long.MaxValue - 200), но я получаю исключение. Это связано с тем, что реализация (на моей машине) метода среднего расширения, проверенного .NET Reflector, выглядит следующим образом:

public static double Average(this IEnumerable<long> source)
{
    if (source == null)
    {
        throw Error.ArgumentNull("source");
    }
    long num = 0L;
    long num2 = 0L;
    foreach (long num3 in source)
    {
        num += num3;
        num2 += 1L;
    }
    if (num2 <= 0L)
    {
        throw Error.NoElements();
    }
    return (((double) num) / ((double) num2));
}

Я знаю, что могу использовать библиотеку BigInt (да, я знаю, что она включена в .NET Framework 4.0, но я привязан к 3.5).

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

Спасибо !!

---

UPDATE:

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

Спасибо всем !!

Answer 1

Используйте библиотеку IntX в CodePlex.

Answer 2

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

Answer 3

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

var items = new long[] { long.MaxValue - 100, long.MaxValue - 200, long.MaxValue - 300 };
var avg = items.Average(i => i / items.Count()) * items.Count();

Answer 4

Если вы готовы пожертвовать точностью, вы можете сделать что-то вроде:

long num2 = 0L;
foreach (long num3 in source)
{
    num2 += 1L;
}
if (num2 <= 0L)
{
    throw Error.NoElements();
}
double average = 0;
foreach (long num3 in source)
{
    average += (double)num3 / (double)num2;
}
return average;

Answer 5

Пусть Avg (n) будет средним в первом n числе, а data [n] - это n-е число.

Avg(n)=(double)(n-1)/(double)n*Avg(n-1)+(double)data[n]/(double)n

Может избежать переполнения значения, однако точность потери при n очень велика.

Answer 6

Усреднение чисел определенного числового типа безопасным способом, в то же время используя только этот числовой тип, действительно возможно, хотя я бы посоветовал использовать помощь BigInteger в практической реализации.Я создал проект для Безопасных числовых вычислений , который имеет небольшую структуру (Int32WithBoundedRollover), которая может суммировать до 2 ^ 32 int32 без каких-либо переполнений (структура внутренне использует два поля int32 для этого, поэтому больших данных нет.используются типы).

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

При этом текущая реализация не предназначена для этого (дляНапример, в Int32WithBoundedRollover нет оператора сравнения, хотя добавить его будет несложно).Причина в том, что в конце гораздо проще использовать BigInteger для выполнения вычислений.С точки зрения производительности это не имеет большого значения для больших средних, так как это будет сделано только один раз, и слишком просто и легко понять, чтобы беспокоиться о том, чтобы придумать что-нибудь умное (по крайней мере, пока ...).

Что касается вашего первоначального вопроса, касающегося длинного типа данных, Int32WithBoundedRollover можно преобразовать в LongWithBoundedRollover, просто поменяв местами ссылки int32 для длинных ссылок, и он должен работать точно так же.Для Int32s я заметил довольно большую разницу в производительности (на случай, если это будет интересно).По сравнению с методом BigInteger, который я создал, он на 80% быстрее для больших (как и в общем количестве точек данных) выборок, которые я тестировал (код для этого включен в модульные тесты для класса Int32WithBoundedRollover).Это, вероятно, в основном из-за разницы между операциями int32, выполняемыми аппаратно, а не программно, как операции BigInteger.

Answer 7

Как насчет BigInteger в Visual J #.