I have three integers A, B (less than 10^12) and C (less than 10^15). I want to calculate (A * B) % C. I know that
(A * B) % C = ((A % C) * (B % C)) % C
but say if A = B = 10^11 then above expression will cause an integer overflow. Is there any simple solution for above case or I have to use fast multiplication algorithms.
If I have to use fast multiplication algorithm then which algorithm I should use.
EDIT: I have tried above problem in C++ (which does not cause overflow, not sure why), but isn't the answer should be zero?
Thanks in advance.
You can solve this using Schrage's method. This allows you to multiply two signed numbers a
and z
both with a certain modulus m
without generating an intermediate number greater than that.
It's based on an approximate factorisation of the modulus m
,
m = aq + r
i.e.
q = [m / a]
and
r = m mod a
where []
denotes the integer part. If r < q
and 0 < z < m − 1
, then both a(z mod q)
and r[z / q]
lie in the range 0,...,m − 1
and
az mod m = a(z mod q) − r[z / q]
If this is negative then add m
.
[This technique is frequently used in linear congruential random number generators].