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