mixedmath

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 1}The 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.

Leave a comment

Comment via email