为什么不同的求和算法不匹配

本文关键字：算法 不匹配 求和 为什么不 | 更新日期: 2023-09-27 18:14:48

假设我想得到从M到n的所有平方和，我在谷歌上搜索了一下，找到了这个公式:

(1^2 + 2^2 + 3^2 +…+ N²= (N * (N + 1) * (2N + 1))/6

所以我写这段代码:

static void Main(string[] args)
{
    const int from = 10;
    const int to = 50000;
    Console.WriteLine(SumSquares(from, to));
    Console.WriteLine(SumSquares2(from, to));
}
static long SumSquares(int m, int n)
{
    checked
    {
        long x = m - 1;
        long y = n;
        return (((y*(y + 1)*(2*y + 1)) - (x*(x + 1)*(2*x + 1)))/6);
    }
}
static long SumSquares2(int m, int n)
{
    long sum = 0;
    for (int i = m; i <= n; ++i)
    {
        sum += i * i;
    }
    return sum;
}

在40k之前工作得很好，但是当N变成50k时它就失败了。50k输出:

41667916674715
25948336371355
Press any key to continue . . .

我认为这是一个溢出或什么的，所以我添加了checked关键字，并试图将long更改为double，但我得到了相同的结果。这怎么解释呢?如何得到正确的结果没有循环?

为什么不同的求和算法不匹配

第二个方法溢出，因为您在循环中使用了int。将其更改为long，如下所示(并添加checked):

static long SumSquares2(int m, int n)
{
    checked
    {
        long sum = 0;
        for (long i = m; i <= n; ++i)
        {
            sum += i*i;
        }
        return sum;
    }
}

出了什么问题是i*i被内部计算为int数据类型，即使结果被转换为long数据类型(即变量sum)，所以它溢出。

虽然对结果使用long，但对操作符仍然使用int。我将M和N定义为long或BigInteger，结果也一样。如果你不这样做，你可能仍然在做int算术，即使你的结果是long类型的。

我试过你的代码，结果和你一样。但随后我将每个int都改为long，并使两个数字匹配，直到N为160000。

使用BigInteger，我高达160000000，仍然工作正常(m=10和n=160000000的结果是13653333461333333359999715，两种方式)。

要使用BigInteger，您需要向System添加一个引用。您需要在您的代码顶部有一个包含该库的语句。

using System.Numerics;
namespace ConsoleFiddle
{
  class Program
  {
    static void Main(string[] args)
    {
        BigInteger from = 10;
        BigInteger to = 160000000;
        Console.WriteLine(SumSquares(from, to));
        Console.WriteLine(SumSquares2(from, to));
        Console.ReadKey();
    }
    static BigInteger SumSquares(BigInteger m, BigInteger n)
    {
        checked
        {
            BigInteger x = m - 1;
            BigInteger y = n;
            return (((y * (y + 1) * (2 * y + 1)) - (x * (x + 1) * (2 * x + 1))) / 6);
        }
    }
    static BigInteger SumSquares2(BigInteger m, BigInteger n)
    {
      checked
      {
        BigInteger sum = 0;
        for (BigInteger i = m; i <= n; ++i)
        {
            sum += i * i;
        }
        return sum;
      }
    }

对于M = 4000000000000000000 (4 × 10^18)， N = 4000000000100000000。这段代码仍然可以工作，并且使用第一个方法(16000000160400000004003333338333333350000000)立即给出结果。对于第二种方法，它需要一点时间(1亿次循环迭代)，但得到相同的结果。

很可能您遇到了整数溢出，因为long的范围是有限的。可能您已经禁用了整数溢出异常，因此不会抛出异常。整数溢出的异常可以在Visual Studio的项目属性中禁用和启用，如果我没弄错的话。

相关文章：