Why do different algorithms of summing not match?

Question

Assume that I want to get sum of all squares from M to N. I googled a bit and found this formula:

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

so I write this code:

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;
}

it works fine until 40k, but when N becomes 50k it fails. Output for 50k:

41667916674715
25948336371355
Press any key to continue . . .

I think it's an overflow or something, so I added checked keyword and tried to change long to double, but I got the same result. How can it be explained? How to get correct result without loops?

Answer 1

Your second method is overflowing because you are using an int in the loop. Change it to a long as follows (and also add checked):

static long SumSquares2(int m, int n)
{
    checked
    {
        long sum = 0;

        for (long i = m; i <= n; ++i)
        {
            sum += i*i;
        }
        return sum;
    }
}

What was going wrong is that i*i was being calculated internally as an int data type even though the result was being cast to a long data type (i.e. the variable sum), and so it overflowed.