Hello Dean,
It may be true that the bias is of the same magnitude as FP multiply, but it is not of the same nature. With FP multiply, the more-likely-to-be-chosen values are more-or-less evenly distributed across the range, whereas modulo concentrates them all at one end, making it more likely to bias test results.
Yes, that is true.
It's worth paying attention to how other languages/libraries implement this, and basically no one chooses the modulo method, which ought to raise alarm bells. Of the biased methods, it has the worst kind of bias and the worst performance.
Hmmm. That is not exactly how I interpreted the figures in the blog.
If a biased method is OK, then the biased integer multiply method seems to be the clear winner. This requires the high part of a 64x64-bit product, which is trivial if 128-bit integers are available, but would need a little more work otherwise. There's some code in common/d2s that might be suitable.
And yes, modulo is expensive. If we allow 128 bits integers operations, I would not choose this RNPG in the first place, I'd take PCG with a 128 bits state.
That does not change the discussion about bias, though.
Most other implementations tend to use an unbiased method though, and I think it's worth doing the same. It might be a bit slower, or even faster depending on implementation and platform, but in the context of the DB as a whole, I don't think a few extra cycles matters either way.
Ok ok ok, I surrender!
The method recommended at the very end of that blog seems to be pretty good all round, but any of the other commonly used unbiased methods would probably be OK too.
That does not address my other issues with the proposed methods, in particular the fact that the generated sequence is less deterministic, but I think I have a simple way around that. I'm hesitating to skip to the the bitmask method, and give up performance uniformity. I'll try to come up with something over the week-end, and also address Tom's comments in passing.
-- Fabien.
