1 #include <math.h> 2 #include <string.h> 3 #include <inttypes.h> 4 #include <stdio.h> 5 #include <unistd.h> 6 #include <sys/types.h> 7 #include <fcntl.h> 8 #include "ieee754.h" 9 #include "zipf.h" 10 #include "../minmax.h" 11 #include "../hash.h" 12 13 #define ZIPF_MAX_GEN 10000000UL 14 15 static void zipf_update(struct zipf_state *zs) 16 { 17 unsigned long to_gen; 18 unsigned int i; 19 20 /* 21 * It can become very costly to generate long sequences. Just cap it at 22 * 10M max, that should be doable in 1-2s on even slow machines. 23 * Precision will take a slight hit, but nothing major. 24 */ 25 to_gen = min(zs->nranges, (uint64_t) ZIPF_MAX_GEN); 26 27 for (i = 0; i < to_gen; i++) 28 zs->zetan += pow(1.0 / (double) (i + 1), zs->theta); 29 } 30 31 static void shared_rand_init(struct zipf_state *zs, unsigned long nranges, 32 unsigned int seed) 33 { 34 memset(zs, 0, sizeof(*zs)); 35 zs->nranges = nranges; 36 37 init_rand_seed(&zs->rand, seed, 0); 38 zs->rand_off = __rand(&zs->rand); 39 } 40 41 void zipf_init(struct zipf_state *zs, unsigned long nranges, double theta, 42 unsigned int seed) 43 { 44 shared_rand_init(zs, nranges, seed); 45 46 zs->theta = theta; 47 zs->zeta2 = pow(1.0, zs->theta) + pow(0.5, zs->theta); 48 49 zipf_update(zs); 50 } 51 52 unsigned long long zipf_next(struct zipf_state *zs) 53 { 54 double alpha, eta, rand_uni, rand_z; 55 unsigned long long n = zs->nranges; 56 unsigned long long val; 57 58 alpha = 1.0 / (1.0 - zs->theta); 59 eta = (1.0 - pow(2.0 / n, 1.0 - zs->theta)) / (1.0 - zs->zeta2 / zs->zetan); 60 61 rand_uni = (double) __rand(&zs->rand) / (double) FRAND32_MAX; 62 rand_z = rand_uni * zs->zetan; 63 64 if (rand_z < 1.0) 65 val = 1; 66 else if (rand_z < (1.0 + pow(0.5, zs->theta))) 67 val = 2; 68 else 69 val = 1 + (unsigned long long)(n * pow(eta*rand_uni - eta + 1.0, alpha)); 70 71 val--; 72 73 if (!zs->disable_hash) 74 val = __hash_u64(val); 75 76 return (val + zs->rand_off) % zs->nranges; 77 } 78 79 void pareto_init(struct zipf_state *zs, unsigned long nranges, double h, 80 unsigned int seed) 81 { 82 shared_rand_init(zs, nranges, seed); 83 zs->pareto_pow = log(h) / log(1.0 - h); 84 } 85 86 unsigned long long pareto_next(struct zipf_state *zs) 87 { 88 double rand = (double) __rand(&zs->rand) / (double) FRAND32_MAX; 89 unsigned long long n; 90 91 n = (zs->nranges - 1) * pow(rand, zs->pareto_pow); 92 93 if (!zs->disable_hash) 94 n = __hash_u64(n); 95 96 return (n + zs->rand_off) % zs->nranges; 97 } 98 99 void zipf_disable_hash(struct zipf_state *zs) 100 { 101 zs->disable_hash = true; 102 } 103