Re: [9front] [PATCH] libc: replace lrand's algorithm

[Eolien55 <eolien55@disroot.org>]

qwx@sciops.net wrote:
> I think at this point it would be better to look at a patch, with the
> changes mentioned after the first post, and a sweep through the other
> implementations.  There are some odd occurrences as you found; libc's
> frand() is also somewhat suspect but will likely need to change if
> lrand() does.  We need a 16bit, 32bit, floating point, and possibly
> 64bit variant; this will clean up some code and remove some
> redundancies which is always nice.  Perhaps take the extreme route and
> do *all* of the changes you'd like to see, so we could more easily
> discuss each case.

I don't currently have the time, but I think I'll work on it, probably
next week. Having a good double/float PRNG surprisingly hard to implement.
See [1] for multiple approaches.

> We then need to check if there's a performance impact on non-amd64
> arches.  For xoroshiro128+ vs. pcg I'd be interested to know if
> there's any significant difference between the two in statistical
> properties and performance; if we make a change, it'd be nice to
> pick the best alternative and make it once and for all.  Code size
> and simplicity also counts.  Is there any other variant that should
> be assessed?

I believe PCG has the smallest code size, and is also the one with
best statistical properties, all things considered.  Other
alternatives of xoroshiro have better statistical properties, such as
xoroshiro128**.  However, if we plan on having 64-bit generators,
xoroshiro256** will probably be simpler and shorter to implement.
PCG64 requires 128-bit operations, which need to be emulated (and that
is quite complex).  xoroshiro256** would be simpler, since it uses 4
32-bit integers.  I am a bit skeptic of xoroshiro256**'s statistical
quality.  Its output function can be easily inversed, by multiplying
by 57 for example, which reveals the inner LFSR, with all its
statistical flaws.  Multiplying it by 57 yields very very
statistically bad generator (it fails within 4MB!).  It is also "too
big to fail", in that empirical tests cannot reasonably show its
flaws, for its period is simply too large for it to be fully tested.
See [2] for more material on the matter.

But that's very much "my opinion man" territory. I think I'd choose
PCG because its quality is good despite its small state, and because
reduced versions of it pass statistical tests (whereas many other
'reduced' (as in, with smaller state as normal) PRNGs fail them even
with larger state). In the end, both are very comparable. If statistical
quality matters more than code size, and if emulating 128-bit addition
and multiplication isn't a problem, then I believe PCG should be chosen.
If it's the other way around, I'd probably go for xoroshiro**.

Cheers,
Elie Le Vaillant

[1] http://mumble.net/~campbell/tmp/random_real.c
[2] https://pcg-random.org/blog/