Skip to content

Instantly share code, notes, and snippets.

@plesner
Last active November 26, 2015 10:28
Show Gist options
  • Save plesner/a003f7a108345c56a74a to your computer and use it in GitHub Desktop.
Save plesner/a003f7a108345c56a74a to your computer and use it in GitHub Desktop.
Script for generating xorshift parameters for various set sizes
#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;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment