lib/gauss.c

   1 #include <math.h>
   2 #include <string.h>
   3 #include "../hash.h"
   4 #include "gauss.h"
   5
   6 #define GAUSS_ITERS     12
   7
   8 static int gauss_dev(struct gauss_state *gs)
   9 {
  10         unsigned int r;
  11         int vr;
  12
  13         if (!gs->stddev)
  14                 return 0;
  15
  16         r = __rand(&gs->r);
  17         vr = gs->stddev * (r / (FRAND32_MAX + 1.0));
  18
  19         return vr - gs->stddev / 2;
  20 }
  21
  22 unsigned long long gauss_next(struct gauss_state *gs)
  23 {
  24         unsigned long long sum = 0;
  25         int i;
  26
  27         for (i = 0; i < GAUSS_ITERS; i++)
  28                 sum += __rand(&gs->r) % (gs->nranges + 1);
  29
  30         sum = (sum + GAUSS_ITERS - 1) / GAUSS_ITERS;
  31
  32         if (gs->stddev) {
  33                 int dev = gauss_dev(gs);
  34
  35                 while (dev + sum >= gs->nranges)
  36                         dev /= 2;
  37                 sum += dev;
  38         }
  39
  40         if (!gs->disable_hash)
  41                 sum = __hash_u64(sum);
  42
  43         return sum % gs->nranges;
  44 }
  45
  46 void gauss_init(struct gauss_state *gs, unsigned long nranges, double dev,
  47                 unsigned int seed)
  48 {
  49         memset(gs, 0, sizeof(*gs));
  50         init_rand_seed(&gs->r, seed, 0);
  51         gs->nranges = nranges;
  52
  53         if (dev != 0.0) {
  54                 gs->stddev = ceil((double)(nranges * dev) / 100.0);
  55                 if (gs->stddev > nranges / 2)
  56                         gs->stddev = nranges / 2;
  57         }
  58 }
  59
  60 void gauss_disable_hash(struct gauss_state *gs)
  61 {
  62         gs->disable_hash = true;
  63 }