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 ?

Cchaddie

x = x * y is the same as x *= y but your expressions do not have this form. There is a division in there. x = x * y / z is not the same as x *= y / z. The order of operations is different – Jeffryjeffy

If / is integer division, then there's a difference between a * (b /c) and (a * b) / c, because of how the remainder is thrown away – Tara

@qrsngky: yes, all 3 variables involved have type u64, so this is integer division. (The function arg is a u64 by reference for no apparent reason or benefit, so *n dereferences it to get a u64.) – Openwork

You may safely change x = x * (*n + i) / i; to x *= (*n + i); x /= i; – Obrien

Note that the function appears to be calculating nCr(2*n,n), the number of unordered combinations in which n elements may be drawn (without replacement) from a set of 2n – Obrien

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

Buonomo

Those 2 things are the same in exact arithmetic, so the root cause is not (just) precedence per se but integer arithmetic. – Vorticella

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

Rural