Блог пользователя HaabyHings

conceptual doubt
Автор HaabyHings, история, 8 лет назад, По-английски

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

  • Проголосовать: нравится
  • -1
  • Проголосовать: не нравится

»
8 лет назад, # |
  Проголосовать: нравится +16 Проголосовать: не нравится

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.

→ Ответить
  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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 ?

    → Ответить
    • »
      »
      »
      8 лет назад, # ^ |
      ← Rev. 2   Проголосовать: нравится +16 Проголосовать: не нравится

      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.

      → Ответить
      • »
        »
        »
        »
        8 лет назад, # ^ |
          Проголосовать: нравится +15 Проголосовать: не нравится

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

        → Ответить