8215441: Increase uniformity of the distribution of BigIntegers constructed by BigInteger(int, Random)

[Adam Petcher]

I'm not sure what the problem is. If X is uniform, then "the number of 
leading zero bits" of X is exponential. The probability of getting a 
"small" number, in which the first (say) 32 bits are 0 is 2^-32. If this 
is what is measured by the histrogram[5], then the current 
implementation looks correct to me.

On 12/19/2018 11:01 PM, Brian Burkhalter wrote:
> https://bugs.openjdk.java.net/browse/JDK-8215441
>
> This issue was filed to cover improving the uniformity of randomly generated BigIntegers. It is not intended to resolve [1] which is deliberately left open. The proposed patch implements a modified version of the “workaround” suggested in [1].
>
> The problem is that the magnitude of the random BigInteger is created from a sequence of bytes generated by Random.nextBytes() [2]. The likelihood that any of these bytes is zero is small so the distribution of the resulting random BigIntegers is skewed towards values close to the maximum bit size “numBits” specified to the constructor.
>
> The workaround suggested in [1] is to randomly change numBits to the value numBits = Random.nextInt(numBits + 1) [3]. (Actually the suggested workaround is nextInt(numBits) which is incorrect as the parameter is an exclusive upper bound.) This greatly improves the uniformity of the distribution. A remaining problem however is that now the very largest numbers in the interval [0,2^numBits) are underrepresented. A modification of this approach is to increment the new value of numBits as numBits = Random.nextInt(numBits + 1) + 1 [4]. This was empirically observed to improve the underrepresentation of the largest values.
>
> The distribution of the random BigIntegers was estimated using [5]. For a given maximum bit length, bin size, and number of random values to generate, this creates a histogram and calculates the coefficient of variation of the numbers generated. The histogram bin at index zero represents the largest valued bin in the result. The count in a given histogram bin is the number of values for which that bin is the leftmost (largest valued) with at least one non-zero bit. The bin of maximum index represents zero.
>
> Results for the current and two modified approaches for 256 bits with a 1-bit bin size and for 4096 bits with a 4-bit bin size are given at [6-11]. As may be observed, the original histogram is clustered towards the largest possible value 2^numBits - 1, and the coefficient of variation is small. The results for the two variants of the patch show a flattened distribution, i.e., more uniform, and a significantly larger coefficient of variation. The second approach shows better flattening of both ends of the histogram. These results are samples only but are exemplary of the results observed over numerous runs of this code.
>
> The test ModPow is modified as the modPow() method throws an ArithmeticException for a zero modulus. The current algorithm never generates a random BigInteger equal to zero however so that exception never occurs. That is not the case for either modified version.
>
> Thanks,
>
> Brian
>
> [1] https://bugs.openjdk.java.net/browse/JDK-8146153
> [2] https://docs.oracle.com/en/java/javase/11/docs/api/java.base/java/util/Random.html#nextBytes(byte[])
> [3] http://cr.openjdk.java.net/~bpb/8146153/webrev.00/
> [4] http://cr.openjdk.java.net/~bpb/8146153/webrev.01/
> [5] http://cr.openjdk.java.net/~bpb/8146153/StatsBigIntegerRandom.java
> [6] http://cr.openjdk.java.net/~bpb/8146153/before-256-1.txt
> [7] http://cr.openjdk.java.net/~bpb/8146153/after-256-1.txt
> [8] http://cr.openjdk.java.net/~bpb/8146153/after-extra-bit-256-1.txt
> [9] http://cr.openjdk.java.net/~bpb/8146153/before-4096-4.txt
> [10] http://cr.openjdk.java.net/~bpb/8146153/after-4096-4.txt
> [11] http://cr.openjdk.java.net/~bpb/8146153/after-extra-bit-4096-4.txt