1

I try to solve some simple algorithmic task and I got problem with modulo operation.

I need to calc this kind of operation: (100003 - 200003*x + 300007*x*x*x) % 1000000

Of course both 300007*x*x*x and 200003*x can easily overflow that 1000000 so I neeed to 'make' modulo on all parts.

I have found sth like this: Sum and multiplication modulo And tried to "do a mod P after every step." like this:

res = 100003
res = (100003 - 200003*x) % 1000000) % 1000000
...

Is that correct? Couse I haven't got right result.

ziyiyituxe
  • 177
  • 1
  • 9
  • 2
    Can you show your actual code, with inputs that produce a wrong result? – Paul Hankin Jul 29 '20 at 15:44
  • It can't overflow in python, so the platform you're working with matters. However, yes, what you're doing should work, unless even a single multiply will cause an overflow. – President James K. Polk Jul 29 '20 at 17:30
  • what data type is `res,x` (bits, signed)? what value is `x`? google `modadd,modsub,modmul` you most likely overflow during `200003*x` so you need a propper `modmul` which requires double the bitwidth for subresults. In order to avoid this you can use Karatsuba or Naive `O(n^2)` multiplication... if `x` is really big you can do `200003*(x%1000000)` instead but still if you are on 32 bits it could overflow easily without `modmul` – Spektre Jul 30 '20 at 06:34

1 Answers1

0

To calculate (100003 - 200003*x + 300007*x*x*x) % 1000000 I would do:

  1. y = x % 1000000
  2. res = (100003 - (200003 * y) % 1000000 + (((300007 * y) % 1000000) * y) % 1000000) * y) % 1000000
  3. if (x > 0 && res < 0) res += 1000000
  4. if (x < 0 && res > 0) res -= 1000000

The way the formula is written we know that the result has to have the same sign as x. This is probably where you are going wrong, you omit step 3 and 4. Although as mentioned using 32 bit it can still overflow. You can omit step 4 if you need a positive modulo and just add 1000000 if res is negative.

maraca
  • 8,468
  • 3
  • 23
  • 45