Implausible Output from Xoshiro256**

It's now been a week since David Blackman and Sebastiano Vigna announced new members of the Xoroshiro family. Although I have been busy with a number of other matters, I recognize that interest in these new PRNGs is likely to be high right now, so I have managed to grab a few stolen moments here and there to take a look at their new work. I plan to write a longer post soon, but my preliminary investigations have turned up enough surprising things that I feel like it's worth sharing some of my discoveries. As with my previous post on these matters, I'll focus in on their best PRNG, xoshiro256**.

Read more…

A Quick Look at Xoshiro256**

On May 4, David Blackman and Sebastiano Vigna announced new members of the Xoroshiro family and a new test for random number generators (based on the z9 test from gjrand) that their previous work fails, all described in a new paper. They claim to have now developed an “all-purpose, rock-solid generator”. In this post, having had less than a day to review their work, I'll present a few preliminary thoughts on this news, mostly looking at their best new generator, xoshiro256**.

Read more…

Xoroshiro128+ Fails PractRand Even When Truncated

Although I know a lot of effort went into Xoroshiro128+, and there are many good things that have come out of its development, I am sad to say that on balance I feel it has too many flaws to be worth recommending—there are many better choices. In this post, I'll dig a little deeper into some of its flaws.

Let's begin with what we already know:

But are the flaws superficial and easily ignored, or more troubling than that?

Read more…

Does It Beat the Minimal Standard?

Suppose that you've written (or just seen someone else announce) a brand new PRNG. Cool! It's nice to have new things. But here's the question you should ask yourself; “Is it better than a reasonable ‘minimal standard’? Does it beat methods devised more than sixty years ago?”

Read more…

On Trivial Predictability

When I wrote the PCG paper back in 2014, I failed really badly when talking about prediction difficulty. When people first started reading the paper and discussing it on the Internet, I realized I had missed the mark, and made sure that the page on this website about predictability had a more nuanced and measured tone, but today I think even that page didn't make the points clearly enough. Possibly I'll fail again today, but let's have another go at trying to articulate the issues.

Read more…

Visualizing the Heart of Some PRNGs

A major point I made in the PCG paper was that we get useful insights by testing small versions of PRNGs. These mini versions may be too small to be useful in practice, but their structure will give us a good sense about the structure of their larger counterparts.

In this post, we'll look at 16-bit versions of several popular PRNGs, and draw some “randomgrams” to get a sense of their structure. In particular, we're going to look at the pattern of occurrences of pairs in the output, in other words which pairs of outputs occur once, which never occur at all, and which occur multiple times.

Read more…

Too Big to Fail

For many PRNGs, the more state bits you give them, the deeper statistical tests need to go to discover their flaws. We'll explore what this phenomenon means, looking at one of the earliest PRNGs ever made, John von Neumann's “Middle Square” method.

Read more…

More PractRand Passes: ChaCha & Truncated XorShift*

Continuing my recent burst of PRNG testing with PractRand, here are a few more passes, this time for the generators I mentioned in my post on reasonable alternatives to PCG.

  • ChaCha<3>
  • ChaCha<4>
  • XorShift* 64/32 (i.e., high 32 bits of 64-bit XorShift*)
  • XorShift* 128/64 (i.e., high 64 bits of 128-bit XorShift*)

None of these results should be a surprise. In the PCG paper, I looked at truncated XorShift* generators and onserved that they passed TestU01 with plenty of headroom. Nevetheless, it's nice to confirm.

Also, none of these generators are trivially predictable (but obviously the smaller XorShift versions can be fairly quickly brute forced). ChaCha obviously has much stronger prediction difficulty, given that with more rounds it is considered cryptographically secure. When simply trying to protect against algorithmic complexity attacks, I think four rounds is fine.

Read more…

128-bit MCG Passes PractRand

As is probably evident, I've been on a bit of a PractRand binge lately. Some of the news hasn't been good, so I'll try to temper the bad news with some better news.

I'm pleased to report that truncated 128-bit multiplicative linear congruential generators (sometimes known as a Lehmer generators) pass PractRand.

Read more…

Critiquing PCG's streams (and SplitMix's too)

PCG allows its generators to optionally select a stream. I discuss the overall concept of streams in the general section on of the site on random number generation here; in essence, streams allow you to choose a generator from a collection of distinct-but-related generators.

Until now I haven't said much about the design decisions behind PCG's streams, but that changes here. At the end I'll also take a brief look at SplitMix's streams.

Read more…

Bugs in SplitMix(es)

In my previous post about testing PCG with the PractRand statistical tests, I also ran PractRand on SplitMix. When I started the testing process, I had a bug in my implementation of SplitMix, and the same bug exists in many SplitMix implementations (e.g., at least four Haskell implementations and an OCaml implementation) because of a small but crucial error in the code for SplitMix given in the SplitMix paper. The specific bug does not exist in Oracle's JDK8 implementation of SplitMix (because that code was written before the paper, and not based on the code in paper).

I'm not the first person to discover this bug (e.g, it's documented in an implementation here), but it caught me out.

I had hoped that I could just correct the code to the JDK version and we'd be all good, but as I thought a little more deeply about what the code is doing, I discovered that even the code in JDK version doesn't successfully address the underlying issues. The flaw runs deeper.

Let's take a look...

Read more…

You don't have to use PCG!

The table on the front page of this site is a double edged sword. It helps people realize that generators they like may have problems, but it also leads some people to think that I'm just trying to aggressively promote my own work.

So, let's be clear, it's certainly nice if you like my work, but the success or otherwise of the PCG family isn't in any way essential to my own career or life success. It's an unexpected side project that I enjoy working on because I find the topic interesting. PCG is free; I don't get any royalties if you use it, and I won't mind if you use another good generator. If you don't see quality in the same way I do, you're entitled to your opinion. In other posts, such as the ones on randutils, I didn't even use my own generator.

So what are some other good generators? I'll mention a couple here...

Read more…

PCG Passes PractRand

There were various questions that people asked when PCG first started being discussed on the Internet; one those questions was whether I had also tested PCG with PractRand. I hadn't. I had done my testing using TestU01, which is considered by most to be the “gold standard”, with the broadest range of tests. Back in 2014, PractRand hadn't been on my radar, but looking into it I discovered that it is TestU01's closest competitor. I put testing with PractRand on my to-do list, but it wasn't a very high priority because I knew that all my PCG family members had been designed to pass TestU01's BigCrush test battery with plenty of headroom, which gave me good reason to believe they would do well in any set of statistical tests.

Finally, this summer I was discussing the best practices for testing random number generators with a colleague and I realized that it was high time for me to finally get around to testing PCG (and a few other recent PRNGs, too!). The short version is, it passes just fine. But for the details, read on…

Read more…