Over a million developers have joined DZone.
Platinum Partner

A Use for Overflow

· Performance Zone

The Performance Zone is brought to you in partnership with New Relic. New Relic APM provides constant monitoring of your apps so you don't have to.

 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)

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


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.

The Performance Zone is brought to you in partnership with New Relic. New Relic’s SaaS-based Application Performance Monitoring helps you build, deploy, and maintain great web software.


Published at DZone with permission of Peter Lawrey , DZone MVB .

Opinions expressed by DZone contributors are their own.

{{ parent.title || parent.header.title}}

{{ parent.tldr }}

{{ parent.urlSource.name }}