lib/gauss.c

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