Modulo of multiplication of large numbers

Question

Yes I know the question may seem naive but I have searched a lot on google and this site as well but could not find a satisfying answer to it. I simply want to calculate (A*B)%MOD, provided a is long long and so are b and MOD. Suppose MOD is larger than both A and B such that A%MOD = A and B%MOD = B but A*B is larger than 64 bits. How can correct value of (A*B)%MOD be calculated?

Matt: I don't agree with the dup. unrealsoul: A*B = (A-X)*B + X*B, you can always split up A this way, into smaller numbers. E.g. set X = floor(A/2). Then you can apply the same procedure if sub-result still too large. — Cheers and hth. - Alf, Jan 09 '14 at 20:16
This is the comment of the person whose answer is accepted "If the max value of long is 2^63 - 1, then 1768431 * x will not overflow as long as x < 290331368171". But this is exactly my doubt what if the A*B overflows. — unrealsoul007, Jan 09 '14 at 20:18
@Cheersandhth.-Alf Nice one mate. This approach seems promising. I will certainly look into it. — unrealsoul007, Jan 09 '14 at 20:24
You could use the [GMP](https://gmplib.org/) library. This would allow to have integers > 64 bits. — SethB, Jan 09 '14 at 20:34
I believe the best you can do without using more than 3 long longs for storage is ((A % MOD)*(B % MOD)) % MOD — Taylor Brandstetter, Jan 09 '14 at 21:06
Not a dupe of the mod 1000000007 question, as OP noted. None of the answers to the other questions are entirely appropriate since they all suggest just using GMP or doing something that's slow, wrong, or x86-specific. Y'all should leave this one open. — tmyklebu, Jan 10 '14 at 00:03

Matt · Accepted Answer · 2014-01-10T00:09:22.510

3

Basic idea here is to first define a non-overflowing addmod function which takes advantage of negative numbers in its arithmetic. Then define timesmod in terms of it also using bit operations. The time complexity is O(N) where N is the number of bits used (64 in this case).

#include <iostream>
using namespace std;

typedef long long BigInt; // must be signed, to detect overflow

BigInt A = 0x7fffffffffffff01;
BigInt B = 0x7fffffffffffff02;
BigInt M = 0x7fffffffffffff03;

// For simplicity it is assumed x, y, and m are all positive.
BigInt addmod( BigInt x, BigInt y, BigInt m )
{
  x %= m;
  y %= m;
  BigInt sum = x-m+y; // -m <= sum < m-1
  return sum < 0 ? sum + m : sum;
}

BigInt timesmod( BigInt x, BigInt y, BigInt m )
{
  x %= m;
  y %= m;
  BigInt a = x < y ? x : y; // min
  BigInt b = x < y ? y : x; // max
  BigInt product = 0;
  for (; a != 0; a >>= 1, b = addmod(b,b,m) )
    if (a&1) product = addmod(product,b,m);
  return product;
}

int main()
{
  cout << "A = " << A << endl;
  cout << "B = " << B << endl;
  cout << "M = " << M << endl;
  cout << "A*B mod M = " << timesmod(A,B,M) << endl;
  return 0;
}

Output:

A = 9223372036854775553
B = 9223372036854775554
M = 9223372036854775555
A*B mod M = 2

This is easily confirmed since A=-2 and B=-1 mod M.

Note: this code is not optimized.

edited Jan 10 '14 at 00:09

answered Jan 09 '14 at 22:16

Matt

20,108
1
57
70

The problem is that you're using a signed type for `BigInt`, so you can't reliably detect overflow (it causes undefined behavior). You need to use an unsigned type to get reliable overflow behavior. – Chris Dodd Jan 09 '14 at 23:52
@ChrisDodd You're absolutely right; thanks for pointing that out. I've updated the `addMod` function to fix this. – Matt Jan 10 '14 at 00:10
Your method is almost identical to the final method I wrote which is: `long long int multiply(long long a, long long b, long long mod) { long long result; if(b==0) return 0LL; result = multiply(a,b>>1,mod); result = (result+result)%mod; if(b&1) result = (result+a)%mod; return result; }` – unrealsoul007 Jan 20 '14 at 21:30
@unrealsoul007 I get `multiply(0x7fffffffffffff01,0x7fffffffffffff02,0x7fffffffffffff03)` returning `-9223372036854711038`. What do you get? (I believe the answer should be `2`.) – Matt Jan 21 '14 at 00:52
@Matt Just edit the code a little bit and replace long long with unsigned long long and you will get the ans 2. – unrealsoul007 Jan 21 '14 at 16:05

score 0 · Answer 2 · answered Jan 10 '14 at 00:27

I think you can form the 128-bit product in two pieces (high 64 bits and low 64 bits) and reduce each piece modulo p. Supposing p is around 4^k, you can then figure out roughly how many p's are in this number by dividing hi64 / (p>>k); this should give you about k-1 bits of the right answer. Subtract off that many p's from the whole thing and now hi64 has about k-1 fewer bits. Do this again, but compute (hi64 << k-1) / (p >> k). Then do it again, computing (hi64 << k+k-2) / (p >> k).

Schrage's trick, suggested by another poster, sounds like a better deal, but I don't understand it. Hopefully that poster returns and completes his answer!

Modulo of multiplication of large numbers

2 Answers2