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 / (FRAND32_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         if (!gs->disable_hash)
  42                 sum = __hash_u64(sum);
  43
  44         return sum % gs->nranges;
  45 }
  46
  47 void gauss_init(struct gauss_state *gs, unsigned long nranges, double dev,
  48                 unsigned int seed)
  49 {
  50         memset(gs, 0, sizeof(*gs));
  51         init_rand_seed(&gs->r, seed, 0);
  52         gs->nranges = nranges;
  53
  54         if (dev != 0.0) {
  55                 gs->stddev = ceil((double) (nranges * 100.0) / dev);
  56                 if (gs->stddev > nranges / 2)
  57                         gs->stddev = nranges / 2;
  58         }
  59 }
  60
  61 void gauss_disable_hash(struct gauss_state *gs)
  62 {
  63         gs->disable_hash = true;
  64 }