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.
15 You should have received a copy of the GNU Affero General Public License
16 along with this program. If not, see <http://www.gnu.org/licenses/>.
18 SPDX-License-Identifier: AGPL3.0-or-later
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));
71 for (i = 0; i < want; i++)
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++)
82 /* use assembly / gcc */
83 j = __builtin_ffs (r) - 1;
89 for (j = 31; j >= 0; j--)
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))
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)
121 ret *= (1 << (j + 1));
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);
139 /* TODO: should calculate stddev of the results to also be able to
140 say something about the stability of the results, outside of
141 large-scale averages -- gaining 8% precision at the expense of
142 50% additional variance might not be worth it... */