GNUnet  0.11.x
Macros | Functions
ibf_sim.c File Reference
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
Include dependency graph for ibf_sim.c:

Go to the source code of this file.

Macros

#define MAX_IBF_DECODE   16
 
#define ROUNDS   100000
 
#define FIX1   0
 
#define FIX2   1
 
#define STRATA   0
 
#define VERBOSE   0
 
#define SLOW   0
 

Functions

int main (int argc, char **argv)
 

Macro Definition Documentation

◆ MAX_IBF_DECODE

#define MAX_IBF_DECODE   16

Definition at line 33 of file ibf_sim.c.

Referenced by main().

◆ ROUNDS

#define ROUNDS   100000

Definition at line 36 of file ibf_sim.c.

Referenced by main().

◆ FIX1

#define FIX1   0

Definition at line 40 of file ibf_sim.c.

◆ FIX2

#define FIX2   1

Definition at line 42 of file ibf_sim.c.

◆ STRATA

#define STRATA   0

Definition at line 45 of file ibf_sim.c.

◆ VERBOSE

#define VERBOSE   0

Definition at line 48 of file ibf_sim.c.

◆ SLOW

#define SLOW   0

Definition at line 50 of file ibf_sim.c.

Function Documentation

◆ main()

int main ( int  argc,
char **  argv 
)

Definition at line 53 of file ibf_sim.c.

References MAX_IBF_DECODE, ret, and ROUNDS.

54 {
55  unsigned int round;
56  unsigned int buckets[31]; // max is 2^31 as 'random' returns only between 0 and 2^31
57  unsigned int i;
58  int j;
59  unsigned int r;
60  unsigned int ret;
61  unsigned long long total;
62  unsigned int want;
63  double predict;
64 
65  srandom (time (NULL));
66  total = 0;
67  want = atoi (argv[1]);
68  for (round = 0; round < ROUNDS; round++)
69  {
70  memset (buckets, 0, sizeof(buckets));
71  for (i = 0; i < want; i++)
72  {
73  /* FIXME: might want to use 'better' PRNG to avoid
74  PRNG-induced biases */
75  r = random ();
76  if (0 == r)
77  continue;
78 #if SLOW
79  for (j = 0; (j < 31) && (0 == (r & (1 << j))); j++)
80  ;
81 #else
82  /* use assembly / gcc */
83  j = __builtin_ffs (r) - 1;
84 #endif
85  buckets[j]++;
86  }
87  ret = 0;
88  predict = 0.0;
89  for (j = 31; j >= 0; j--)
90  {
91 #if FIX1
92  /* improved algorithm, for 1000 elements with IBF-DECODE 8, I
93  get 990/1000 elements on average over 1 million runs; key
94  idea being to stop short of the 'last' possible IBF as
95  otherwise a "lowball" per-chance would unduely influence the
96  result */if ((j > 0) &&
97  (buckets[j - 1] > MAX_IBF_DECODE))
98  {
99  ret *= (1 << (j + 1));
100  break;
101  }
102 #endif
103 #if FIX2
104  /* another improvement: don't just always cut off the last one,
105  but rather try to predict based on all previous values where
106  that "last" one is; additional prediction can only really
107  work if MAX_IBF_DECODE is sufficiently high */
108  if ((j > 0) &&
109  ((buckets[j - 1] > MAX_IBF_DECODE) ||
110  (predict > MAX_IBF_DECODE)))
111  {
112  ret *= (1 << (j + 1));
113  break;
114  }
115 #endif
116 #if STRATA
117  /* original algorithm, for 1000 elements with IBF-DECODE 8,
118  I get 920/1000 elements on average over 1 million runs */
119  if (buckets[j] > MAX_IBF_DECODE)
120  {
121  ret *= (1 << (j + 1));
122  break;
123  }
124 #endif
125  ret += buckets[j];
126  predict = (buckets[j] + 2.0 * predict) / 2.0;
127  }
128 #if VERBOSE
129  fprintf (stderr, "%u ", ret);
130 #endif
131  total += ret;
132  }
133  fprintf (stderr, "\n");
134  fprintf (stdout, "average %llu\n", total / ROUNDS);
135  return 0;
136 }
static int ret
Return value of the commandline.
Definition: gnunet-abd.c:81
#define ROUNDS
Definition: ibf_sim.c:36
#define MAX_IBF_DECODE
Definition: ibf_sim.c:33