Integer overflow during modulo division

Question

I am trying to compute the following value.

prod = 1;
for(int i=1;i<N;i++){
    prod = prod*i;
}

Since N can be large, I was asked to compute modulo 10^9+7 and I did.

int prod =1;    
for(int i=1;i<N;i++)
{
    prod = ((prod%1000000007) * (i%1000000007))%1000000007;     
}

Some one else did.

long ways=1;    
for(int j=1;j<N;j++)
{
    ways = (int)(j * ways % 1000000007);    
}

The online judge is taking the second as correct. Why is it?

So I ran this

int prod = 1;
long ways = 1;

for(int j=1;j<14;j++){
     prod = ((prod%1000000007) * (j%1000000007))%1000000007;

     ways = (int)(j * ways % 1000000007);

     if(prod!=ways){

            System.out.println(prod+" "+ways);
            System.exit(0);
        }
     System.out.println(prod+" "+ways+" "+j);
}

And when prod or ways is 479001600 and j is 12 in the next iteration they are not equal. Both of which are less than int max which is 2147483647

So I do this and they are equal

 prod = ((479001600%1000000007) * (12%1000000007))%1000000007;

         ways = (int)(12 * 479001600 % 1000000007);

         if(prod!=ways){

                System.out.println(prod+" "+ways);
                System.exit(0);
            }
         System.out.println(prod+" "+ways);

I think it is something something casting. But cannot figure out. Please tell me if I am doing something wrong?

Why the downvote. Dint I try anything? Is this a trivial question? — WannaBeCoder, Dec 02 '16 at 14:31
it is a trivial question, given that you already know that Integer has an overflow. searching for Integer overflow will most likely result in a dozent of answeres to your question. — Tom Wellbrock, Dec 02 '16 at 14:35
Actually, you need to check how Java stores operation result when you have `long * int` — AxelH, Dec 02 '16 at 14:37
@Maarten Bodewes you might notice, that op asked why his question got downvoted. Also the beholder is me as I saw it as trivial even for beginners. your reasoning makes no sence to me and dosent help either so leave it be — Tom Wellbrock, Dec 02 '16 at 14:54
@TomWellbrock Ah, OK, I overlooked the question in the comments. It may not be trivial to everybody that `x * y (mod 2^32) (mod 1000000007) != x * y (mod 1000000007)` (and that's disregarding sign bits) so I think the downvote was premature. If it has an answer elsewhere it should be closed as a dupe. But you're right, it could be that *somebody* downvoted for the reason you gave. — Maarten Bodewes, Dec 02 '16 at 15:04
that might help as well: http://stackoverflow.com/questions/3001836/how-does-java-handle-integer-underflows-and-overflows-and-how-would-you-check-fo — Tom Wellbrock, Dec 02 '16 at 15:11

Benjamin Podszun · Accepted Answer · 2016-12-02T14:35:01.857

3

Haven't done Java for a while, but this seems language agnostic (and not related to modulo): You are using an int (prod), the other solution uses a long (ways).

The multiplication of your variable (either prod or ways) with j (here 12) is what overflows. 479001600 * 12 is 5,748,019,200. If both arguments are an int this will overflow. The largest 32bit value is 4,294,967,295.

If one side of the expression is a long, the result will be a long instead -> No overflow.

edited Dec 02 '16 at 14:35

answered Dec 02 '16 at 14:29

Benjamin Podszun

9,679
3
34
45

Note that the solution could run into sign related problems before overflowing 32 bits (i.e. when overflowing 31 bits, of course). Java basic types are all signed (except char, but that's not for doing these kind of calculations) and Java doesn't have a modulo operator, only a *remainder* operator. – Maarten Bodewes Dec 02 '16 at 14:40
Thank you @Benjamin Podszun , I was missing,if one side is long result will be long. So in `ways = (int)(j * ways % 1000000007)` cast to int is unnecessary and that should be `((j * (ways%1000000007)) % 1000000007);` since long can also overflow. – WannaBeCoder Dec 02 '16 at 15:45
Yes, the cast to int was unnecessary if the result is assigned to a long again. I don't understand the second change: ```ways``` is the result of a previous iteration and therefor (correct me if I'm wrong) always < 1000000007. The additional operation seems just as unnecessary. The original code (sans the cast) already multiplied j with a number that is always less than the prime. – Benjamin Podszun Dec 02 '16 at 16:20

Aimee Borda · Answer 2 · 2016-12-02T14:34:46.600

0

The casting is not the problem but your data-types changing prod to long will solve your problem. The reason for this is that the multiplication will overflow when j=13 even tough you are taking the modulus of the result afterwards.

edited Dec 02 '16 at 14:34

answered Dec 02 '16 at 14:28

Aimee Borda

842
2
11
22

Integer overflow during modulo division

2 Answers2