class SplittableRandom

[Guy Steele]

On Jul 15, 2013, at 4:13 PM, Martin Buchholz <martinrb at google.com> wrote:

> I'll be your loyal adversary today, trying to break SplittableRandom.

Thanks so much!  This is exactly the sort of skepticism we need.

> Let's make it easier by providing a low-level constructor:
> 
>    /** XXXX Testing */
>    public SplittableRandom(long seed, long gamma, Error XXXX) {
>        this.seed = seed;
>        this.gamma = gamma;
>        this.nextSplit = seed;
>    }
> 
> and provide some debugging:
> 
>     private static int mix32(long z) {
> +        boolean onebit = (Long.bitCount(z) == 1);
> +        if (onebit) System.out.printf("mix32: z=%08x%n", z);
>         z ^= (z >>> 33);
>         z *= 0xc4ceb9fe1a85ec53L;
> +        if (onebit) System.out.printf("mix32: ret=%08x%n", (int)(z >>>
> 32));
>         return (int)(z >>> 32);
>     }
> 
> and then we have sneaky test using weakest args: seed = 0, gamma = 16
> 
>    public void testXXXX() {
>        SplittableRandom r = new SplittableRandom(0L, 16L, new
> Error("XXXX"));
>        System.out.println();
>        for (int i = 0; i < 30; i++)
>            System.out.printf("%08x%n", r.nextInt());
>    }
> 
> And we get in the output:
> 
>     [java] mix32: z=00000010
>     [java] mix32: ret=4ceb9fe1
>     [java] 4ceb9fe1
> ...
>     [java] mix32: z=00000100
>     [java] mix32: ret=ceb9fe1a
>     [java] ceb9fe1a
> ...
> 
> which is not "random enough" for my taste.

And indeed, if we look at more such values, we do see patterns:

mix32: input=0000000000000001 result=c4ceb9fe
mix32: input=0000000000000010 result=4ceb9fe1
mix32: input=0000000000000100 result=ceb9fe1a
mix32: input=0000000000001000 result=eb9fe1a8
mix32: input=0000000000010000 result=b9fe1a85
mix32: input=0000000000100000 result=9fe1a85e
mix32: input=0000000001000000 result=fe1a85ec
mix32: input=0000000010000000 result=e1a85ec5
mix32: input=0000000100000000 result=1a85ec53
mix32: input=0000001000000000 result=ced49520
mix32: input=0000010000000000 result=ed49520d
mix32: input=0000100000000000 result=d49520d4
mix32: input=0001000000000000 result=49520d42
mix32: input=0010000000000000 result=9520d42f
mix32: input=0100000000000000 result=520d42f6

> 

And yet, I wonder what it means to be "random enough".  After all, preselecting the inputs to study to be those with exactly one 1-bit is already a choice of fairly rare birds (64 values out of 2^64, or one out of every 2^58).  Such values come up very rarely.

> It would be nice if we could use mixing to twiddle the seed in addition to
> mixing the return value (instead of throwing away the mixing effort), but
> then it is hard to see how to guarantee 2^64 period.

Yes, I see what you mean, and I agree.

> mix32 looks too simple to me to do "enough mixing".  I'm surprised running
> nextInt through DieHarder would pass - it's close to linear congruential.

I was surprised, too, or perhaps I should say gratified, that this worked.
I was searching semi-methodically for just such a simple mixing function,
testing them by examining avalanche statistics.  The low-order 32 bits produced
by mix32 are pretty bad, but the upper 32 bits appear to be quite well mixed.
It's amazing what a little bit of XORing does to disrupt the uniformities of
the linear-congruential method.

[more below]

> On Mon, Jul 15, 2013 at 9:59 AM, Martin Buchholz <martinrb at google.com>wrote:
> 
>> If we make the wraparound point for seeds Long.MIN_VALUE instead of 0L,
>> then we can optimize addGammaModGeorge.  Any reason the following won't
>> work?
>> 
>> --- src/main/java/util/SplittableRandom.java 14 Jul 2013 08:06:49 -0000
>> 1.10
>> +++ src/main/java/util/SplittableRandom.java 15 Jul 2013 16:25:42 -0000
>> @@ -222,10 +222,10 @@
>>      */
>>     private static long addGammaModGeorge(long s, long g) {
>>         long p = s + g;
>> -        if (Long.compareUnsigned(p, g) >= 0)
>> +        if (p > s)
>>             return p;
>> -        long q = p - 13L;
>> -        return (Long.compareUnsigned(p, 13L) >= 0) ? q : (q + g);
>> +        p -= 13L;
>> +        return (p < s) ? p : p + g;
>>     }
>> 
>>     /**

Yes, thanks, this is a good idea likely to produce speed improvements for
processors/compilers that do not (yet) do a good job with Long.compareUnsigned.
But I don't think that last comparison "p < s" is correct.  The version I came up with,
given just a hint of your technique through Doug, was this:

    private static long addGammaModGeorge(long sx, long g) {
        long px = sx + g;
        return (px >= sx) ? px : ((px >= 0x800000000000000DL) ? px  : px + g) - 13L;
    }

(I used an "x" on variable names to remind me which ones are using the offset representation.)
For some reason, on the particular version of Java and particular processor I used for my test,
this was slightly faster than:

    private static long addGammaModGeorge(long sx, long g) {
        long px = sx + g;
        return (px >= sx) ? px : ((px >= 0x800000000000000DL) ? px - 13L : px + g - 13L);
    }

and I don't know why.

>> Also, if gamma is much less than 2^64 (say 2^56; that number of gammas
>> "should be enough for anybody"), then the above will be a little more
>> efficient since the wraparound code will be rare and well-predicted.  The
>> bits that become available as a result can then be optionally donated to
>> the seed space!

Yeah, I thought about that, but was too scared of introducing some sort of bias.
But now that you have made me think about it more carefully, I think you may be right.

>> Have we run DieHarder tests against adversarial gamma values, that provide
>> as few bits as possible?  Most obviously, try gamma == 16.

Or, even more obviously, gamma == 1.  Yes, I intend to run such tests.

You also wrote:

> The algorithm in SplittableRandom is much better, although even here I'm not
> sure we have enough bits of state to satisfy all non-cryptographic uses.

> I continue to worry that we are producing a PRNG that will end up not being
> acceptable to the Monte Carlo simulation community.

And I agree.  I comfort myself with the thought that even though this algorithm
does not allow any single object to generate the same 64-bit value twice consecutively,
that observation does not apply to double values (which use only 53 bits apiece).
For applications that use doubles rather than longs, SplittableRandom may be okay.

On the whole, I would really prefer to use 128-bit seeds and 128-bit gamma values.
If only support for 128-bit integers were built into Java, with good use of the condition
codes and add-with-carry instructions at the machine level, this would be a very plausible
thing to do.  I view the currently proposed 64-bit, implemented-entirely-in-Java version
as adequate for a lot of purposes, and way better than java.util.Random for a lot of
purposes, and therefore perhaps easy to accept into JDK8.  But we want to avoid
committing to too specific a mechanism; I certainly don't think this algorithm is the
last word, but rather the first step toward getting much better parallel RNGs.
Maybe for JDK9 we could have 128-bit algorithms supported by tightly written
native machine code at very little extra computational expense, but first we need
to get experience with this class of algorithms.  Just a thought.

--Guy