2 This file is part of GNUnet
3 Copyright (C) 2013 GNUnet e.V.
5 GNUnet is free software: you can redistribute it and/or modify it
6 under the terms of the GNU Affero General Public License as published
7 by the Free Software Foundation, either version 3 of the License,
8 or (at your option) any later version.
10 GNUnet is distributed in the hope that it will be useful, but
11 WITHOUT ANY WARRANTY; without even the implied warranty of
12 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
13 Affero General Public License for more details.
18 * @brief implementation of simulation for invertible bloom filter
19 * @author Florian Dold
21 * This code was used for some internal experiments, it is not
22 * build or shipped as part of the GNUnet system.
28 #define MAX_IBF_DECODE 16
30 /* report average over how many rounds? */
33 /* enable one of the three below */
36 // possibly slightly better fix for large IBF_DECODE values
44 // avoid assembly? (ASM is about 50% faster)
48 main(int argc, char **argv)
51 unsigned int buckets[31]; // max is 2^31 as 'random' returns only between 0 and 2^31
56 unsigned long long total;
60 srandom (time (NULL));
62 want = atoi (argv[1]);
63 for (round=0;round<ROUNDS;round++)
65 memset (buckets, 0, sizeof (buckets));
68 /* FIXME: might want to use 'better' PRNG to avoid
69 PRNG-induced biases */
74 for (j=0;(j < 31) && (0 == (r & (1 << j)));j++) ;
76 /* use assembly / gcc */
77 j = __builtin_ffs (r) - 1;
83 for (j=31;j >= 0; j--)
86 /* improved algorithm, for 1000 elements with IBF-DECODE 8, I
87 get 990/1000 elements on average over 1 million runs; key
88 idea being to stop short of the 'last' possible IBF as
89 otherwise a "lowball" per-chance would unduely influence the
92 (buckets[j - 1] > MAX_IBF_DECODE) )
94 ret *= (1 << (j + 1));
99 /* another improvement: don't just always cut off the last one,
100 but rather try to predict based on all previous values where
101 that "last" one is; additional prediction can only really
102 work if MAX_IBF_DECODE is sufficiently high */
104 ( (buckets[j - 1] > MAX_IBF_DECODE) ||
105 (predict > MAX_IBF_DECODE) ) )
107 ret *= (1 << (j + 1));
112 /* original algorithm, for 1000 elements with IBF-DECODE 8,
113 I get 920/1000 elements on average over 1 million runs */
114 if (buckets[j] > MAX_IBF_DECODE)
121 predict = (buckets[j] + 2.0 * predict) / 2.0;
124 fprintf (stderr, "%u ", ret);
128 fprintf (stderr, "\n");
129 fprintf (stdout, "average %llu\n", total / ROUNDS);
133 /* TODO: should calculate stddev of the results to also be able to
134 say something about the stability of the results, outside of
135 large-scale averages -- gaining 8% precision at the expense of
136 50% additional variance might not be worth it... */