Over a million developers have joined DZone.
{{announcement.body}}
{{announcement.title}}

A Use for Overflow

DZone's Guide to

A Use for Overflow

· Performance Zone ·
Free Resource

SignalFx is the only real-time cloud monitoring platform for infrastructure, microservices, and applications. The platform collects metrics and traces across every component in your cloud environment, replacing traditional point tools with a single integrated solution that works across the stack.

 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.


SignalFx is built on a massively scalable streaming architecture that applies advanced predictive analytics for real-time problem detection. With its NoSample™ distributed tracing capabilities, SignalFx reliably monitors all transactions across microservices, accurately identifying all anomalies. And through data-science-powered directed troubleshooting SignalFx guides the operator to find the root cause of issues in seconds.

Topics:

Published at DZone with permission of

Opinions expressed by DZone contributors are their own.

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

{{ parent.tldr }}

{{ parent.urlSource.name }}