Deeply flawed PRNG in Random.mod

[alvoskov]

The pseudorandom number generator module contains an obsolete PRNG called minstd. It has a tiny period around 2^31 - 2 that may be exausted almost instantly. It also fails birthday spacings and gap tests. It means that it mustn't be used for any statistical computations or numerical simulation and it better to replace it some good generator (e.g. ChaCha or AES) or add a warning lilke "Warning! This PRNG is a toy suitable only for writing TETRIS".

But there it seems that it is rather difficult to add the most robust general purpose PRNGs to Oberon because things like ChaCha, LEA or Speck128/128 stream ciphers require unsigned integers with wrapping overflow. Even simpler non-cryptographic generators often require such behaviour. And additive/subtractive lagged Fibonacci generators that are friendly to such type system are either toy generators (at least for lags up to 10^6 - 10^7) or will require decimation that will make them slower than AES (i.e. senseless).

[kekcleader]

Hi. Thanks for pointing that out. Let's update Random.Mod with a new implementation.

It is possible to use unsigned integers in Free Oberon. At least, by using C functions.

Do you have a reference implementation of a good PRNG?

[alvoskov]

I think there are several options:

1. Try to adapt some PRNG to the Oberon type system. It was an interesting challenge for me and I've designed Mwc63x2 algorithm (https://github.com/alvoskov/Mwc63x2-obx/tree/main). Its a combination of two large MWC (essentially LCGs) with prime modulo that uses the signed 64-bit integers and doesn't rely on overflows at all that is rather rare for PRNG. The multipliers search procedure was based on prime tests and Knuth's spectral test. The similar design was used in MWC1616 by Marsaglia, but due to the larger state and more advanced output function Mwc63x2 has a much higher quality.

I have also implemented a classical Birthday Spacings test in FreeOberon (see the same repository), your Random.mod fails it, a good PRNG must pass it.

I was unable to make DLL in FreeOberon (don't know how), so I've tested the next C implementation by three different test suites:
https://github.com/alvoskov/SmokeRand/blob/devel/generators/mwc63x2.c. I also don't know how to send PRNG output to stdout in binary form in FreeOberon,. It it possible to send raw binary data in FreeOberon to stdout, especially on Windows?

Mwc63x2 (C version) does pass TestU01 BigCrush, PractRand 0.94 at least up to 8 TiB and my own test battery SmokeRand. Its theoretical period is about 2^122.

2. Use stream cipher like ChaCha20. I have a "naive" C++ implementation for non-crypto purposes.
   https://github.com/alvoskov/SmokeRand/blob/devel/apps/chacha.h
   It is equipped with the original test vectors from RFC and passes PractRand at least up to 1 TiB. The algorithm itself has a very high quality. But the only problem that it is 4-5 cpb, i.e. 5-10 times slower than fast non-crypto PRNGs. Reducing rounds to 12 or even 8 won't cause problems with quality, and performance will be likely comparable to your minstd implementation.

High-performance AVX2 implementations of ChaCha12 may have performance around 0.8-1 cpb. But they are much more bulky and may require hundreds lines of code, I have such implementation but I had no choice because I needed a high-speed state-of-art PRNG for calibration of my statistical tests
https://github.com/alvoskov/SmokeRand/blob/devel/generators/chacha.c

3. Use some simple and fast PRNGs like e.g. xoroshiro++, xoroshiro** or xoshiro++/xoshiro** by Vigna. They have a high quality, widely used (https://prng.di.unimi.it/) but its implementation may be a little bit challenging in Oberon. But it is very simple in C, much simpler than e.g. PCG that often require 128-bit integers that are not portable.