Script for generating xorshift parameters for various set sizes

xorshift.cc

#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>
#include <time.h>

class Xorshift {
public:
  Xorshift(uint32_t x, uint32_t y, uint32_t z, uint32_t w)
    : ox_(x), oy_(y), oz_(z), ow_(w)
    , x_(x), y_(y), z_(z), w_(w) { }
  Xorshift();
  uint32_t next();
  uint32_t exhaust(uint32_t limit, uint32_t dups_allowed, uint32_t *loops_out);
  static uint32_t new_seed();
public:
  uint32_t ox_, oy_, oz_, ow_;
  uint32_t x_, y_, z_, w_;
};

Xorshift::Xorshift()
  : x_(new_seed())
  , y_(new_seed())
  , z_(new_seed())
  , w_(new_seed()) { }

uint32_t Xorshift::next() {
  uint32_t t = x_ ^ (x_ << 11);
  x_ = y_;
  y_ = z_;
  z_ = w_;
  w_ = w_ ^ (w_ >> 19) ^ t ^ (t >> 8);
  return w_;
}

uint32_t Xorshift::exhaust(uint32_t limit, uint32_t dups_allowed, uint32_t *loops_out) {
  bool *seen = new bool[limit];
  for (int i = 0; i < limit; i++)
    seen[i] = false;
  uint32_t seen_count = 0;
  uint32_t dups_remaining = dups_allowed;
  uint32_t loops_at_last = 0;
  uint32_t loops = 0;
  while (seen_count < limit) {
    uint32_t v = next() % limit;
    loops++;
    if (seen[v]) {
      if (dups_remaining == 0) {
        break;
      } else {
        dups_remaining--;
      }
    } else {
      seen[v] = true;
      seen_count++;
      loops_at_last = loops;
    }
  }
  delete[] seen;
  *loops_out = loops_at_last;
  return seen_count;
}

uint32_t Xorshift::new_seed() {
  uint32_t candidate = 0;
  while (candidate == 0)
    candidate = rand() * (0xFFFFFFFF / RAND_MAX);
  return candidate;
}

static const int kTries = 10000000;
int main(int argc, char *argv[]) {
  double fractions[4] = {0.0, 0.0625, 1.0, 1024.0};
  int limits[6] = {32, 64, 128, 256, 512, 1024};
  srand(12323);
  int32_t a = Xorshift::new_seed();
  int32_t b = Xorshift::new_seed();
  int32_t c = Xorshift::new_seed();
  int32_t d = Xorshift::new_seed();
  for (int ia = 0; ia < 4; ia++) {
    double dup_amount = fractions[ia];
    printf("--- dups: %g ---\n", dup_amount);
    for (int il = 0; il < 6; il++) {
      int limit = limits[il];
      Xorshift seeder(a, b, c, d);
      int best_size = 0;
      int best_x, best_y, best_z, best_w;
      int dups_allowed = int(dup_amount * limit);
      int best_loops = limit + dups_allowed;
      for (int it = 0; it < kTries; it++) {
        Xorshift gen(seeder.next(), seeder.next(), seeder.next(), seeder.next());
        uint32_t loops = 0;
        int size = gen.exhaust(limit, dups_allowed, &loops);
        if (size > best_size || (size == best_size && loops < best_loops)) {
          best_size = size;
          best_loops = loops;
          best_x = gen.ox_;
          best_y = gen.oy_;
          best_z = gen.oz_;
          best_w = gen.ow_;
        }
      }
      float coverage = 100 * float(best_size) / limit;
      float density = float(best_loops) / best_size;
      printf("0x%08x 0x%08x 0x%08x 0x%08x: %i/%i %i (%.3g%% %.2gx) \n", best_x, best_y, best_z, best_w, best_size, limit, best_loops, coverage, density);
    }
  }
  return 0;
}