Почему разные алгоритмы суммирования не совпадают?

Предположим, что я хочу получить сумму всех квадратов от M до N. Я немного искал Google и нашел эту формулу:

(1 ^ 2 + 2 ^ 2 + 3 ^ 2 +... + N ^ 2) = (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, но получил тот же результат. Как это можно объяснить? Как получить правильный результат без циклов?

Ответ 1

Второй метод переполняется, потому что вы используете 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), и поэтому он переполнялся.

Ответ 2

Пока вы используете long для результата, вы все еще используете int для операторов. Я бы определил M и N как долго или даже BigInteger, и то же самое для результата. Если вы этого не сделаете, вы, вероятно, все еще выполняете арифметику int, хотя ваш результат имеет тип long.

Я попробовал ваш код и получил полученные результаты. Но потом я изменил каждый int на длинный и получил два числа, чтобы соответствовать, до N 1600000.

Используя BigInteger, я до 160000000 и все еще работаю нормально (результат для m = 10 и n = 160000000 равен 13653333461333333359999715, в обоих направлениях).

Чтобы использовать BigInteger, вам нужно добавить ссылку на dll System.Numerics в свой проект, и вам нужно будет иметь оператор вверху вашего кода, включая эту библиотеку.

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 x 10 ^ 18) и N 4000000000100000000. Этот код по-прежнему работает и дает немедленный результат с помощью первого метода (1600000016040000000400333333338333333350000000). При втором методе это занимает некоторое время (100 миллионов итераций цикла), но дает тот же результат.

Ответ 3

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