Performance Zone is brought to you in partnership with:

Peter is a DZone MVB and is not an employee of DZone and has posted 154 posts at DZone. You can read more from them at their website. View Full User Profile

A Use for Overflow

12.17.2012
| 1148 views |
  • submit to reddit

 There is simple, but expansive problem in cryptography which can be written as

Calculate y = (p^n) mod (2^32) where p is a prime number and n is a large integer.

Using BigInteger

You can use the obvious way using BigInteger.
BigInteger answer = BigInteger.valueOf(prime)
                              .pow(number)
                              .mod(BigInteger.valueOf(2).pow(32));

This works, but is very expensive for large numbers.  This can take minutes/hours for large number.

Fortunately BigInteger has a method which is useful in the situation. Instead of generating a very large numebr only to modulus back into a smaller one, it has a combined method called
 BigInteger modPow(BigInteger power, BigInteger mod)  

This method is much faster and can take milli-seconds.

Using Overflow

If you look at the magic number 2^32 this appears to be an odd choice at first.  The trick is to realise this is the same as & 0xFFFFFFFFL or just keeping the lowest 32-bits. One type does this naturally which is the int type.  Technically, it should be an unsigned int but Java doesn't support this. 

Fortunately the difference can be compensated for by masking the result.
    public static long powMod2_32(int prime, int number) {
        int answer2 = 1;
        int p = prime;
        for (int n = number; n > 0; n >>>= 1) {
            if ((n & 1) != 0)
                answer2 *= p;
            p *= p;
        }
        return answer2 & 0xFFFFFFFFL;
    }
This only calculates the lowest 32-bit by making use of the fact it overflows (discarding any higher bits)  It also calculates squares of squares so it doesn't need to iterate each power, as does BigInteger.  The main gain is using a very efficient type and not needing to do anything extra to get the "mod 2^32"

Performance Comparison

The BigInteger.modPow is fast, but using the loop above is much faster.  For this test, the warmed up results look like
True answer 4,231,348,777 took 5.169 μs, quick answer 4,231,348,777 took 0.051 μs
True answer 1,807,631,477 took 4.922 μs, quick answer 1,807,631,477 took 0.051 μs
True answer 3,579,038,417 took 3.974 μs, quick answer 3,579,038,417 took 0.052 μs
True answer 3,923,287,037 took 4.679 μs, quick answer 3,923,287,037 took 0.051 μs
True answer 2,169,903,033 took 5.381 μs, quick answer 2,169,903,033 took 0.051 μs

Summary

Normally, you would not want overflows and you need to ensure they are avoided, but in this cause the original algorithm was designed to exploit it, and it can make a big difference.


Published at DZone with permission of Peter Lawrey, author and DZone MVB. (source)

(Note: Opinions expressed in this article and its replies are the opinions of their respective authors and not those of DZone, Inc.)