CODEWITHSUNDEEP
c#algorithminteger-division
user29150577
user29150577

Reputation: 393

Why does a = a * (x + i) / i; and a *= (x + i) / i; return two different results?

I am calculating the number of routes possible in a 20 * 20 grid from top left to bottom right when only down and right moves are possible.

I read about calculating the central binomial coefficient to calculate the routes and implemented it in my code:

public void Code()
{
    Console.WriteLine(countRoutes(20));
}

public long countRoutes(int x)
{
    long result = 1;

    for (int i = 1; i <= x; i++)
    {
        result = result * (x + i) / i;
    }

    return result;
}

It works out and gives the correct result.

The problem is when I try to replace the result calculation with:

result *= (x + i) / i;

which returns an incorrect result.

I tried adding more brackets to clarify the solution. Still didn't fix it. My second guess was that maybe dividing by I would get incorrect result since it would be an integer division, but why is it working in the top code.

Upvotes: 35

Views: 3962

Answers (1)

wohlstad
wohlstad

Reputation: 28084

It is a matter of operator precedence together with the nature of integer division.

*= has lower precedence than normal arithmetic operators (+,-,*,/).

Therefore

result *= (x + i) / i;

is actually:

result = result * ((x + i) / i);

Whereas

result = result * (x + i) / i;

Is actually:

result = (result * (x + i)) / i;

Note that in the first case the integer division by i (which can always lose precision due to truncation to int) is done before multiplying result.

A simple example with ints that illustrates the difference:

10 * (5 / 2) => 5 / 2 is 2 and 10 * 2 is 20.

(10 * 5) / 2 => 10 * 5 is 50 and 50 / 2 is 25.

Note:
Mathematically in this case, as @nocomment mentioned below,
result * (x + i) will always be divisible by i (demonstrated live on .NET fiddle up to number 20).
For those interested, @JiK outlined a mathematical proof for that, in a comment below: after each step result is the binomial coefficient (x+i) over i, and so it's an integer - i.e the division will not yield any remainder.
This means that result * (x + i) / i (used in the 2nd case) will always yield the correct value.

A final note:
A rule of thumb for integer arithmetic with reasonably sized values (see downside below), is to prefer to do multiplications before divisions.
This will not eliminate the problems of integer division entirely but will reduce the cases where it causes problems.
However the downside to keep in mind is that if you have large values multiplying first will increase the chances for an overflow.

Upvotes: 75

Related Questions