A cautionary tale of PRNGs.

[deltarho[1859]]

When at PowerBASIC I wrote implementations of xorshift128+ and xoroshiro128+ by David Blackman and Sebastiano Vigna. PowerBASIC has no idea what uint64_t (Ulongint) is so I used SSE. However, both had a weakness, acknowledged by the authors, which caused them to fail a PractRand test. I reckoned that requesting up to half of the failure value would be OK but I also reckoned that most, if not all, folk would not be persuaded and simply would not use them.

Since then the authors have been busy and knocked out a range of new generators. What caught my eye was the four new ones using 64 bit internal arithmetic. Two of them were designed for floating point work and are slightly faster than their general purpose versions but they have weaknesses. These weaknesses will be masked when only the floating point bits are used but extracting them will have an effect on the throughput so I ignored them. Of the two remaining, xoshiro256** and xoroshiro128**, the latter uses three rotations but the former uses only two rotations resulting in the former being faster. I opted, then, for xoshiro256**.

Now, I have written a few generators for FreeBASIC so why bother writing another one. As with FB, my generators use 32 bit internal arithmetic and output a Double so as to keep the 32 bit granularity. To get a genuine Double, ie with 53 bit granularity, we have to request two 32 bit numbers. When using 64 bit internal arithmetic we only need to request one 64 bit number. With this approach, I am getting a throughput of about 310MHz which is pretty good compared with PCG32II's throughput of 495MHz using 32 bit internal arithmetic.

This is what the authors say about xoshiro256**:

This is xoshiro256** 1.0, our all-purpose, rock-solid generator. It has excellent (sub-ns) speed, a state (256 bits) that is large enough for any parallel application, and it passes all tests we are aware of.

My initial tests always include an average generator output, Ulong or Ulongint, and an average Double precision output and some range tests. Obviously, if I got 0.6 for 10^7 double precision instead of close to 0.5 then my implementation is 'out of kelter'. Everything seemed fine so the next job was to dust down PractRand.

xoshiro256** failed spectacularly within a few seconds with more FAIL!!!!!!!! than you can shake a stick at. FAIL!!!!!!!! is the worst failure PractRand reports with p values of zero. I spent some time going through my code and could not find anything wrong. So, I looked at xoroshiro128**. That went down the tubes as well.

Searched the internet and found that I am not alone.

I then found a discussion at reddit.com/r/programming which included posts by Melissa O'Neill ( Username: ProfONeill ), author of my PCG32II, and Sebastiano Vigna ( Username: sebastianovigna ), joint author of xoroshiro128** and xoshiro256**. These two were going at each 'hammer and tongs' and Vigna was bordering being vitriolic. Here is a link to the thread - it is a long one. I always knew that rivalry existed within the world of academia but I had not realized how heated it could be.

Needless to say, I shall not post any code, not that you could stand another generator from me <smille., which fails PractRand on the first hurdle.

So, why did I dust down PractRand after reading "rock-solid generator" and "it passes all tests we are aware of". It is sad but when you get to my age you probably won't believe anything you read and I want to see proof with my own eyes. I saw nothing of the sort.

I am sure that I have mentioned this but PractRand does not prove randomness. The null hypothesis is that a generator is random and if a PractRand test succeeds to 1TB or more then no evidence has been found to question the null hypothesis. Whatever O'Neill and Vigna say about each other's work O'Neill's PCG32, in particular, passes PractRand and Vigna's latest offerings do not. Having said that, I must admit that on reading some of O'Neill's blogs I have sometimes found myself stretching for the salt cellar figuring that a 'pinch of salt' was needed. <smile>

[deltarho[1859]]

I used to pop over to O'Neill's PCG Blog quite often but have not been there this year. I took a little time out to catch up. She has been busy and some blogs are devoted to attacking Sebastiano Vigna's work. I also have not been to Vigna's website this year either. He now has a page entitled The wrap-up on PCG generators
where he rips into O'Neill's work.

Blackman and Vigna wrote, with regard xoshiro256**: "The state must be seeded so that it is not everywhere zero. If you have a 64-bit seed, we suggest to seed a splitmix64 generator and use its output to fill s." O'Neill, on the other hand, attacks the use of splitmix64.

George Marsaglia suggested using the KISS algorithm for seeding his CMWC lag~4096.

What I cannot understand is why none of them suggest using a cryptographic generator for seeding their PRNGs which yours truly has been doing for some years. Since I appear to be the only one who does then I must be wrong, right? Perhaps it is because it is not available on all platforms - it is on Windows and Linux so why not mention it in their regard.

Anyway, O'Neill vs Vigna is quite extraordinary.

[srvaldez]

hello deltarho[1859]
saw this at code project, perhaps it may be of interest to you https://www.codeproject.com/Articles/11 ... ng-Methods

[deltarho[1859]]

Hi srvaldez. Thanks for that - it is a long read but it will be read.

I noticed that he mentions the von Mises Distribution in the Specific Non-Uniform Distributions section.

A few years ago a guy at the PowerBASIC forum wrote some code that displayed a fly flying around in a square. Unfortunately, it behaved nothing like how a fly would behave. He was using Rnd which, because it is uniformly distributed, meant that the likelihood of the fly turning left, say, by 5º was the same as turning left by 45º or, even 90º. Well, a fly suddenly changing direction by 90º looked terrible to say nothing about it being impossible.

So, I replaced Rnd with the von Mises Distribution. The likelihood of turning left, say, by 5º was now greater than 10º, greater than 15º and so on up to 90º which had a likelihood very close to zero. I had to play around with the distributions parameters but eventually, we ended up with an image which did look like a fly flying around in a square. This guy is a prolific coder and has knocked some pretty good stuff over the years. What possessed him to consider a fly flying around a square is something that I never found out. I didn't have the heart to ask him.

In fact, I have a PowerBASIC CMWC lag~256 which has a von Mises function. Needless to say, it has other uses besides a fly flying around a square. <smile>. In fact, there is a lot of graphics code on this forum which would benefit ditching Rnd in favour of a Non-Uniform Distribution; the Normal Distribution is not called normal without reason.