c# - 无溢出异常的平均函数

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 中是 included，但我只能使用 3.5)。

但我仍然想知道是否有一个非常直接的实现来计算整数的平均值而无需外部库。你碰巧知道这样的实现吗？

谢谢!!

---

更新:

前面的三个大整数示例只是说明溢出问题的示例。问题是关于计算任何 一组数字的平均值，这些数字的总和可能会超过该类型的最大值。很抱歉造成这种困惑。我还更改了问题的标题以避免更多的混淆。

谢谢大家!!

Answer 1

这个答案曾经建议分别存储商和余数(mod count)。该解决方案的空间效率较低且代码更复杂。

为了准确计算平均值，您必须跟踪总数。没有办法解决这个问题，除非您愿意牺牲准确性。您可以尝试以奇特的方式存储总数，但如果算法正确，您最终必须跟踪它。

对于单遍算法，这很容易证明。假设在处理这些项目后给定算法的整个状态，您无法重建所有前面项目的总数。但是等等，我们可以模拟算法然后接收一系列 0 项直到我们完成序列。然后我们可以将结果乘以计数并得到总数。矛盾。因此，单遍算法必须在某种意义上跟踪总数。

因此，最简单的正确算法只是将项目相加并除以计数。您所要做的就是选择一个具有足够空间来存储总数的整数类型。使用 BigInteger 保证没有问题，所以我建议使用它。

var total = BigInteger.Zero
var count = 0
for i in values
    count += 1
    total += i
return total / (double)count //warning: possible loss of accuracy, maybe return a Rational instead?