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
6 it under the terms of the GNU General Public License as published
7 by the Free Software Foundation; either version 3, or (at your
8 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 General Public License for more details.
15 You should have received a copy of the GNU General Public License
16 along with GNUnet; see the file COPYING. If not, write to the
17 Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
18 Boston, MA 02110-1301, USA.
23 * @brief implementation of simulation for invertible bloom filter
24 * @author Florian Dold
26 * This code was used for some internal experiments, it is not
27 * build or shipped as part of the GNUnet system.
33 #define MAX_IBF_DECODE 16
35 /* report average over how many rounds? */
38 /* enable one of the three below */
41 // possibly slightly better fix for large IBF_DECODE values
49 // avoid assembly? (ASM is about 50% faster)
53 main(int argc, char **argv)
56 unsigned int buckets[31]; // max is 2^31 as 'random' returns only between 0 and 2^31
61 unsigned long long total;
65 srandom (time (NULL));
67 want = atoi (argv[1]);
68 for (round=0;round<ROUNDS;round++)
70 memset (buckets, 0, sizeof (buckets));
73 /* FIXME: might want to use 'better' PRNG to avoid
74 PRNG-induced biases */
79 for (j=0;(j < 31) && (0 == (r & (1 << j)));j++) ;
81 /* use assembly / gcc */
82 j = __builtin_ffs (r) - 1;
88 for (j=31;j >= 0; j--)
91 /* improved algorithm, for 1000 elements with IBF-DECODE 8, I
92 get 990/1000 elements on average over 1 million runs; key
93 idea being to stop short of the 'last' possible IBF as
94 otherwise a "lowball" per-chance would unduely influence the
97 (buckets[j - 1] > MAX_IBF_DECODE) )
99 ret *= (1 << (j + 1));
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 */
109 ( (buckets[j - 1] > MAX_IBF_DECODE) ||
110 (predict > MAX_IBF_DECODE) ) )
112 ret *= (1 << (j + 1));
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)
126 predict = (buckets[j] + 2.0 * predict) / 2.0;
129 fprintf (stderr, "%u ", ret);
133 fprintf (stderr, "\n");
134 fprintf (stdout, "average %llu\n", total / ROUNDS);
138 /* TODO: should calculate stddev of the results to also be able to
139 say something about the stability of the results, outside of
140 large-scale averages -- gaining 8% precision at the expense of
141 50% additional variance might not be worth it... */