Why does x = x * y / z give a different result from x *= y / z for integers?

Question

I have the following function:

pub fn s_v1(n: &u64) -> u64 {
    let mut x: u64 = 1;

    for i in 1..=*n  {
        x = x * (*n + i) / i;
    }

    x
}

This code gives the correct answer for s_v1(&20) == 137846528820

However, if I change the line in the for loop to x *= (*n + i) / i;

The answer changes to s_v1(&20) == 16094453760

Why are the results different? Isn't x = x * y the same as x *= y ?

Answer 1

Because * and / have the same precedence with left associativity, the expression is not

x * ((*n + i) / i)

(which is the same as x *= (*n + i) / i) but

(x * (*n + i)) / i

Answer 2

As others have indicated, there are two contributing factors:

1. a*=b/c is equivalent to a=a*(b/c) and not to a=a*b/c (which is implicitly a=(a*b)/c).
2. / denotes division according to the types of the operands. In this case the operands are both integers, and therefore / denotes integer division discarding any remainder, and therefore (a*b)/c is not the same as a*(b/c) (unless b is an exact multiple of c).

If you want to replace the line in the loop, you'd need to split the two operations:

    for i in 1..=*n  {
        x *= *n + i;
        x /= i;
    }

One disadvantage of this algorithm is that it will not produce correct results when the answer should be between MAXINT/2n and MAXINT. For that, you actually need to take advantage of what you were attempting to do:

    for i in 1..=*n  {
        if (x % i == 0) {
            x /= i;
            x *= *n + i;
        } else if (*n % i == 0) {
            x *= *n / i + 1;
        } else {
            x *= *n + i;
            x /= i;
        }
    }