Java 8 RFC 7189139: BigInteger's staticRandom field can be a source of bottlenecks

[Paul Sandoz]

On Aug 26, 2013, at 3:15 PM, Paul Sandoz <Paul.Sandoz at oracle.com> wrote:
>> As discussed in the relevant threads in the original bug report, the
>> actual fix should be a very accurate replacement of SR with some other
>> faster and reliable RNG to avoid the inherent scalability bottlenecks.
>> 
> 
> I don't know about the PRNG requirements for Miller-Rabin but the changes to TLR in review might be a possible substitute for SR in this case, since TLR will be updated to use the same PRNG algorithm as SplittableRandom, which passes DieHarder tests.  Otherwise, i think we may just be stuck with SR.
> 

FYI the updates to ThreadLocalRandom are now in tl, so it is possible to more easily investigate whether this can substitute SecureRandom.

<ponder>

IIUC the Miller-Rabin algorithm seems almost embarrassingly parallel.

One could write a Spliterator in combination with SplittableRandom to generate an appropriate source of BigInteger instances hooked up to a stream:

  Stream<BigInteger> s = BigInteger.randomStream(pp.bitLength(), n);
  return s.filter(b -> b.compareTo(ONE) > 0 && b.compareTo(pp) < 0).map(b -> test(b, pp)).allMatch(r -> r == true);

I suppose in some respects it is unfortunate to have to write a Spliterator instead of piggybacking off IntStream.range(0, n) and associating with functions to create a SplittableRandom and split based on how the range is split.

Another way could be to write a Spliterator for a source of depth and SplittablleRandom, then hook that up to flatMap:

  Stream<Pair<Integer, SplittableRandom>> s = ...;  
  return s.flatMap((d, sr) -> bigInts(sr, pp.bitLength(), n / (1 << d)).map(b -> test(b, pp)).allMatch(r -> r == true);

</ponder>

Paul.