I was bitten by a randomness bug. Large random integers made by flint aren't random. I don't mean that they're not sufficiently random. That would be expected as there are all sorts of subtleties with PRNGs that are weird. But instead, once a number has $63$ or more bits,1 1The exact number will be dependent on the machine, but there is a number. flint's random numbers behave deterministically and don't change on separate program runs or by seeding the random number generator differently.
Here is a sample program.
#include <flint/fmpz.h>
#include <flint/flint.h>
#include <time.h>
#include <stdio.h>
void rand_num(int nbits) {
flint_rand_t state;
flint_randinit(state);
flint_randseed(state, time(NULL), time(NULL) + 1);
fmpz_t n;
fmpz_init(n);
fmpz_randbits(n, state, nbits);
fmpz_abs(n, n);
fmpz_print(n);
printf(" %d bits\n", nbits);
fmpz_clear(n);
}
int main() {
for (int nbits = 60; nbits < 70; nbits++) {
rand_num(nbits);
}
}
Here are the outputs from three consecutive runs.
60 bits 759446736344329039
822779313571414777
886111895093467810
61 bits 1335907488647752527
1975700818178261753
1462572647396891298
62 bits 3641750497861446479
4281543827391955705
2615494152003738274
63 bits 6400306986398558324
6400306986398558324
6400306986398558324
64 bits 6400306986398558324
6400306986398558324
6400306986398558324
65 bits 24847051060108109940
24847051060108109940
24847051060108109940
66 bits 61740539207527213172
61740539207527213172
61740539207527213172
67 bits 135527515502365419636
135527515502365419636
135527515502365419636
68 bits 283101468092041832564
283101468092041832564
283101468092041832564
69 bits 283101468092041832564
283101468092041832564
283101468092041832564
Note that I reset the random state at the start of the function, so it's not a surprise that we sometimes get the same number with different bits. This corresponds to the additional bit being $0$ (and I guess the bits are generated from most-significant-bit to least-significant-bit).
But it is surprising that the sequences generated are the same across different runs.
Using flint_randseed(state, a, b); for various integers a and b changes
the generated numbers with $62$ or fewer bits as expected, but also has no
effect on generated numbers with $63$ or more bits.
For my purposes, it sufficed to generate random bitstrings elsewhere and then convert these to flint integers. I did this using code that boils down essentially to
// setup
auto do_this_somewhere() {
std::random_device rd;
std::mt19937 rng = std::mt19937(rd());
return rng
}
std::string generate_random_bits(int nbits, std::mt19937 & gen) {
std::bernoulli_distribution dist(0.5);
std::string bitstring;
bitstring.reserve(nbits);
for (int i = 0; i < nbits; ++i) {
bitstring += (dist(gen) ? '1' : '0');
}
return bitstring;
}
void random_flint_int(fmpz_t n, int nbits, std::mt19937 & gen) {
std::string bitstring = generate_random_bits(nbits, gen);
fmpz_set_str(n, bitstring.c_str(), 2);
}
Explanation of the Bug
The source indicates different behaviors for different sizes.
It turns out that when the number of bits is above SMALL_FMPZ_BITCOUNT_MAX
(which on my setup is apparently 62), flint will use a GMP random
construction,
which always default constructs
state.
The fault then falls on GMP's
gmp_randinit_default,
which apparently has a fixed default value. This was noted in this question on
StackOverflow.
What surprised me was that flint allows one to set the seed, but this is independent of GMP's seeding. To be fair, the ability to set the PRNG seed is not advertised on the online documentation — who can blame the system for undocumented behavior?
It is possible to directly set the GMP seed in the state, but this feels fragile. Instead, know that large integers in flint aren't random.
Directly setting the GMP seed
It turns out that I would like to be able to set the GMP seed. The only nontrivial aspect here is that the internal GMP state isn't initialized until the first call for its random bits — this makes sense, as why initialize work that might not be necessary to do? It is necessary to initialize the state.
#include <flint/fmpz.h>
#include <flint/flint.h>
#include <time.h>
#include <stdio.h>
void rand_num(int nbits) {
flint_rand_t state;
flint_randinit(state);
flint_randseed(state, time(nullptr), time(nullptr) + 1);
_flint_rand_init_gmp(state);
gmp_randseed_ui(state->gmp_state, (unsigned long)time(nullptr));
fmpz_t n;
fmpz_init(n);
fmpz_randbits(n, state, nbits);
fmpz_abs(n, n);
fmpz_print(n);
printf(" %d bits\n", nbits);
fmpz_clear(n);
}
int main() {
for (int nbits = 60; nbits < 70; nbits++) {
rand_num(nbits);
}
}
Info on how to comment
To make a comment, please send an email using the button below. Your email address won't be shared (unless you include it in the body of your comment). If you don't want your real name to be used next to your comment, please specify the name you would like to use. If you want your name to link to a particular url, include that as well.
bold, italics, and plain text are allowed in comments. A reasonable subset of markdown is supported, including lists, links, and fenced code blocks. In addition, math can be formatted using
$(inline math)$or$$(your display equation)$$.Please use plaintext email when commenting. See Plaintext Email and Comments on this site for more. Note also that comments are expected to be open, considerate, and respectful.