CODEWITHSUNDEEP
c#.netalgorithmmathinteger-arithmetic
Alex Zhukovskiy
Alex Zhukovskiy

Reputation: 10025

Why do different algorithms of summing not match?

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?

Upvotes: 18

Views: 1766

Answers (3)

Matthew Watson
Matthew Watson

Reputation: 109792

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.

Upvotes: 31

user4843530
user4843530

Reputation:

While you are using long for the result, you are still using int for the operators. I would define M and N as long or even BigInteger, and the same for the result. If you do not, you are probably doing int arithmetic still, even though your result is of type long.

I tried your code, and got the results you got. But then I changed every int to long and got the two numbers to match, up to an N of 1600000.

Using BigInteger, I am up to 160000000 and still working ok (result for m=10 and n=160000000 is 13653333461333333359999715, both ways).

To use BigInteger, you will need to add a reference to the System.Numerics dll to your project, and you will need to have a statement at the top of your code including that library.

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

For an M of 4000000000000000000 (4 x 10^18), and an N of 4000000000100000000. This code still works and gives an immediate result with the first method (1600000016040000000400333333338333333350000000). With the second method it takes it a little while (100 million loop iterations) but gives the same result.

Upvotes: 12

Codor
Codor

Reputation: 17605

Most probably you are experiencing integer overflow, as the range of long is limited. Probably you have disabled exceptions for integer overflow, so no exception is thrown. The exceptions for integer overflow can be disabled and enabled in the project properties in Visual Studio, if I'm not mistaken.

Upvotes: 3

Related Questions