HaabyHings's blog

conceptual doubt
By HaabyHings, history, 7 years ago, In English

let there be 3 integers x, y, z
their multiplication (x * y * z) is can be calculated either as (x * y) * z or x * (y * z) // associativity holds
now assume x / (y * z) = x * (1 / y) * (1 / z)
let Y and Z be the multiplicative modular inverse of (1 / y) and (1 / z) respectively
then result can be written as x * Y * Z
here (x * Y) * Z != x * (Y * Z) { WHY ? } // associativity does not holds

  • Vote: I like it
  • -1
  • Vote: I do not like it

»
7 years ago, # |
  Vote: I like it +16 Vote: I do not like it

Why do you think associativity does not hold on the last line? It does.

For example, let x = 3, y = 7, and z = 9, and let the modulo be 10. We have Y = 3 (since ) and Z = 9 (since ). After you have the values which you are going to multiply, the order does not matter again: .

Now, if you have different results with different orders, it probably means you have an error elsewhere. For example, you may be trying to multiply integers of order 109 in an int32 type, which is wrong since the result can of the order 1018.

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Gassa Sir, thanks for reply, but I am still confused.
    I was refering to this question on codechef.
    here is the accepted solution link.
    here is the wrong one link.
    only difference in the above submissions is different association while calculating answer.
    I am pretty sure that i am taking care of overflow.
    Where am I wrong then ?

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
      ← Rev. 2   Vote: I like it +16 Vote: I do not like it

      In the second one, the expression is essentially

      res += (A * (B * C) % M) % M;

      which is evaluated as

      res += ((A * (B * C)) % M) % M;

      See, since * and % have the same priority, it goes as follows: first calculate temp = B * C, then multiply A by temp (here is the overflow), and only then take the result modulo M. Perhaps you meant

      res += (A * ((B * C) % M)) % M;

      The (B * C) parens don't matter for the compiler, but (B * C % M) do.

      → Reply
      • »
        »
        »
        »
        7 years ago, # ^ |
          Vote: I like it +15 Vote: I do not like it

        Thanks.
        That was very silly on my part.
        It would have cost me lots of wrong submissions in future.

        → Reply