Fast multiplication of large numbers modulo n

Question

Possible Duplicate:
Need help in mod 1000000007 questions

I have a set of numbers for which i want to compute total product modulo 1000007. e.g if my array contains 1000 numbers then i need to compute the following.

int product = 1;
for(int i=0;i<Array_Max;i++)
  product = product * Array[i]

then product modulo 1000007 = ?

Is there any algorithm to optimize the above pseudo code ? Right now i am unable to store the product because of overflow.

Any suggestion appreciated.

The `1000007`... Is this related the problem from this question: http://stackoverflow.com/questions/9169167/need-help-in-mod-1000000007-questions — Mysticial, Jun 10 '12 at 16:39
I'm math challenged. Are we saying that `(a mod x) * (b mod x) * (c mod x) == ((a*b*c) mod x)` ? — Tony Ennis, Jun 10 '12 at 16:44
@TonyEnnis: Not quite. We're saying that `((a * b) mod x) * c) mod x == (a * b * c) mod x`. — Oliver Charlesworth, Jun 10 '12 at 16:47
Alok, what is the largest value you expect to be in `Array[]`? This will help us determine the type of the result. — Tony Ennis, Jun 10 '12 at 16:50
@Tony we are calculating something like (a[0]*a[1]*a[2]...a[n-1])modulo 1000007. Overflow will appear once the product exceeds the max limit of integer or long whatever we choose. — Alok, Jun 10 '12 at 16:53

score 3 · Answer 1 · answered Jun 10 '12 at 16:42

3

Use longs for the product - this will be enough to hold the result of multiplying two integers.

You also will want to compute the modulo on each iteration so that you avoid overflow (this is safe to do from a mathematical perspective, as it doesn't change the result modulo 1000007 at the end).

You could also use BigIntegers if you wanted, but it would be much slower.

answered Jun 10 '12 at 16:42

mikera

105,238
25
256
415

How do you know the `long` is big enough for the multiplication of 2 integers? – Tony Ennis Jun 10 '12 at 16:45
@TonyEnnis: Because `int` is 32-bit and `long` is 64-bit. – Oliver Charlesworth Jun 10 '12 at 16:46
@TonyEnnis What Oli says. Or, in another words, [MAX_INTEGER * MAX_INTEGER = 4.6 × 10^18](http://www.wolframalpha.com/input/?i=%282^31-1%29+*+%282^31-1%29), but [MAX_LONG is 9.2 × 10^18](http://www.wolframalpha.com/input/?i=2^63-1) – Petr Janeček Jun 10 '12 at 16:48
@OliCharlesworth If the OP is asking this question, I would think his use of an `int` is suspect to begin with. – Tony Ennis Jun 10 '12 at 16:48
+1 `long` it is, according to a clarification from the OP. – Tony Ennis Jun 10 '12 at 16:53

Fast multiplication of large numbers modulo n

1 Answers1