Handling overflow with %

Question

I have a function Java which looks like this:

private static long fieldPrime = 4294967291L; // 2^32-5
public final static long modMult(long a, long b) {
    long r = (a*b) % fieldPrime;        
    return r;
}

It multiplies two values (which are guaranteed to be between 0 and 2^32-5) and then does modulo a large prime.

It works for most numbers but sometimes a*b overflows and this causes the function to return the wrong value. Unfortunately Java doesn't support unsigned longs (which would have solved the issue) and BigInteger is too slow. Can I solve this some other way? I.e. can I adjust r somehow when I detect overflow (in this case a*b < 0 always means it has overflowed).

x22 · Accepted Answer · 2011-10-20 15:04:02Z

4

This should work (if both a and b are between 0 and fieldPrime-1):

  private static long fieldPrime = 4294967291L; // 2^32-5
  private static long correctionFactor = fieldPrime+25; //fieldPrime + (2^64) mod fieldPrime 

  public final static long modMult(long a, long b) {
      long r = (a*b);
      if (r>=0)
      {
        return r % fieldPrime;
      }
      else
      {
        return ((r% fieldPrime)+correctionFactor)%fieldPrime;  
      }
  }

When overflow occurs a*b will actually be a * b - 2^64 so adding (2^64 mod fieldPrime) is what is needed. Adding one more fieldPrime and one more % operation is needed to make the result in range 0 to fieldPrime-1 (otherwise it may be negative).

(It won't work this way if fieldPrime>2^32.)

EDIT The else part can also be changed to:

    return (fieldPrime-a)*(fieldPrime-b)%fieldPrime;

(I don't known which is faster.)

edited Oct 20, 2011 at 15:04

answered Oct 20, 2011 at 14:38

x22

5412 silver badges7 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

Vala · Accepted Answer · 2011-10-20 14:19:34Z

0

You could convert a, b, and fieldPrime to doubles and cast the result back to a long once you know you're in a safe range again (after modulo). However it's possible that doubles could cause rounding errors in some cases.

Other than that I'd say BigInteger is your best bet, if it's too slow, maybe you could make something that would work with byte arrays instead of longs, but I doubt that would be much quicker.

answered Oct 20, 2011 at 14:19

Vala

5,7041 gold badge32 silver badges56 bronze badges

2 Comments

Vala Over a year ago

If you're going to down vote me for an answer that is at least trying to be helpful you should probably tell me why to give me a chance to check it out...

Yrlec Over a year ago

I didn't down-vote it. I agree with you, down-votes should be followed by a comment.

Collectives™ on Stack Overflow

Handling overflow with %

2 Answers 2

Comments

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related