State of PRNG code in GMP

[Pedro Gimeno]

Torbjörn Granlund wrote on 2020-06-01 12:10:

> Question 1: Why is _mp_lc wrapped in a union?

Historical reasons. It was that way when I implemented MT.

> Question 2: "_lc" = Linear Congruential? This is supposed to be a
> generic structure, right?

Historical reasons again :)

Unfortunately, my old Balsa mail client destroyed all my emails with you and Kevin Ryde, by setting under my back the default mail purge time to a few days, so I'll try to put together what I remember from... about 18 years ago. The patch is dated June 2002. I remember there was some discussion in the ML but the archives only go back to October 2002.

Yes, LC is Linear Congruential. It was the only available generator when I started working on the MT one. The struct had the exact same shape before I took it, and I fitted the new generator into that struct trying to use the available fields in a backwards compatible way. Kevin went quite paranoid about ABI compatibility, to the point of not wanting to add another pointer member to the union for fear of changing the size of the structure. I think his words were along the lines of "I don't know if it would be compatible, it should be, but better safe than sorry". So my patch included these changes:

-/* Random state struct.  */
+/* Random state struct.  The meaning of its fields has changed but the
+   structure is kept unchanged for compatibility.  */

-/* Available random number generation algorithms.  */
+/* Available random number generation algorithms (obsolete.) */

-/* Linear congruential data struct.  */
+/* Linear congruential state struct (obsolete.) */

Somehow these changes either have been removed, or didn't make it past the review, but they would have helped you understand what was going on. Here's the patch as I submitted it for review (I believe), which has some patch comments that I added to facilitate the review:

http://www.formauri.es/personal/pgimeno/temp/gmp_snap_mt.diff

The pre-existing random structure was very limited, and building a compatible generic generator layer on top of it while keeping backwards compatibility needed some compromises, like having to allocate a function pointers struct instead of using the random state struct itself to store them; abusing the pointer field in the seed's mpz_t for the state, and using the macros RNG_FNPTR() and RNG_STATE() to access those in a more programmer-friendly way.

The plan was to get rid of the struct issues in the next ABI breakage, but I guess no one took note of that with respect to the generators, or at least no one did anything about it (we've broken the ABI since GMP 4.0.1, right?)

> So LC is the default?  And that's the one choice?

LC (2exp) is the default and the only choice for gmp_randinit, which is considered obsolete. When I implemented the MT patch, there was also a disabled and probably non-functional Blum-Blum-Shub generator.

I'm not too sure why I removed gmp_randinit_lc, but something about it being broken rings a bell, so it's possible that Kevin told me to do that.

> Let's look at what functions we have for initialising a gmp_randstate_t:
> 
>      void gmp_randinit (gmp_randstate_t, gmp_randalg_t, ...);
> 
>      void gmp_randinit_default (gmp_randstate_t);

Also gmp_randinit_mt and gmp_randinit_lc_2exp.

>> Twister.  One would expect
> 
>    gmp_randinit (my_randstate, GMP_RAND_ALG_DEFAULT)
> 
> to also choose Mersenne Twister.  But GMP_RAND_ALG_DEFAULT =
> GMP_RAND_ALG_LC as per the enum definition.

No, gmp_randinit is declared obsolete. You're supposed to use the algorithm-specific gmp_randinit_xxxx for any supported algorithm xxxx.

I don't know for sure why gmp_randinit was not adapted to the new generators. Probably Kevin told me to do that but I don't remember the rationale.

> Question 3: What algorithm does the call
>    gmp_randinit (my_randstate, GMP_RAND_ALG_DEFAULT)
> choose?  Is it Mersenne Twister?

No, it should be LC if it hasn't changed since the time I wrote the patch.

> Question 4: How should a user who really wants LC choose that?

Besides gmp_randinit, there's still a gmp_randinit_lc_2exp.

> Perhaps we should start anew with a new set of random state functions
> and a new type (where all fields are actually used!).  The name
> gmp_prngstate_t might be useful.

That would not be off the mark. Trying to build on the existing facilities is what led to the current mess.