class SplittableRandom

[Martin Buchholz]

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

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.

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.

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.




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;
>      }
>
>      /**
>
> 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!
>
> Have we run DieHarder tests against adversarial gamma values, that provide
> as few bits as possible?  Most obviously, try gamma == 16.
>