-
Notifications
You must be signed in to change notification settings - Fork 2
/
Copy pathSimpleIndex.cpp
370 lines (325 loc) · 51.7 KB
/
SimpleIndex.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
#include "SimpleIndex.h"
#include <random>
#include <numeric>
#include "cryptoTools/Crypto/PRNG.h"
#include "cryptoTools/Common/Log.h"
#include "cryptoTools/Common/CuckooIndex.h"
#include <cassert>
#ifdef ENABLE_BOOST
#include <boost/math/special_functions/binomial.hpp>
#include <boost/multiprecision/cpp_bin_float.hpp>
#endif
namespace volePSI
{
void SimpleIndex::print()
{
for (u64 i = 0; i < mBins.size(); ++i)
// for (u64 i = 0; i <1; ++i)
{
std::cout << "Bin #" << i << std::endl;
std::cout << " contains " << mBinSizes[i] << " elements" << std::endl;
for (u64 j = 0; j < mBinSizes[i]; ++j)
{
std::cout << " idx=" << mBins(i, j).idx() << " hIdx=" << mBins(i, j).hashIdx() << std::endl;
// std::cout << " " << mBins[i].first[j] << " " << mBins[i].second[j] << std::endl;
}
std::cout << std::endl;
}
std::cout << std::endl;
}
// template<unsigned int N = 16>
double getBinOverflowProb(u64 numBins, u64 numBalls, u64 getBinSize, double epsilon = 0.0001)
{
#ifdef ENABLE_BOOST
if (numBalls <= getBinSize)
return std::numeric_limits<double>::max();
if (numBalls > std::numeric_limits<i32>::max())
{
auto msg = ("boost::math::binomial_coefficient(...) only supports " + std::to_string(sizeof(unsigned) * 8) + " bit inputs which was exceeded." LOCATION);
std::cout << msg << std::endl;
throw std::runtime_error(msg);
}
// std::cout << numBalls << " " << numBins << " " << binSize << std::endl;
typedef boost::multiprecision::number<boost::multiprecision::backends::cpp_bin_float<16>> T;
T sum = 0.0;
T sec = 0.0; // minSec + 1;
T diff = 1;
u64 i = getBinSize + 1;
while (diff > T(epsilon) && numBalls >= i /*&& sec > minSec*/)
{
sum += numBins * boost::math::binomial_coefficient<T>(i32(numBalls), i32(i)) * boost::multiprecision::pow(T(1.0) / numBins, i) * boost::multiprecision::pow(1 - T(1.0) / numBins, numBalls - i);
// std::cout << "sum[" << i << "] " << sum << std::endl;
T sec2 = boost::multiprecision::log2(sum);
diff = boost::multiprecision::abs(sec - sec2);
// std::cout << diff << std::endl;
sec = sec2;
i++;
}
return std::max<double>(0, (double)-sec);
#else
throw std::runtime_error("getBinOverflowProb requires ENABLE_BOOST. " LOCATION);
#endif
}
namespace
{
// log2(bin size) of mapping n balls to m bins, for 40 bit sec.
// row i has n=2^i bins, column j has m=2^j balls.
std::vector<std::vector<double>> logbinSizes_40bit{{
// log #bins , log #balls
// 0, 1, 2, 3, 4, 5, 6,...
/*0*/ {{0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30}},
/*1*/ {{0, 1, 2, 3, 4, 5, 5.857980995, 6.686500527, 7.523561956, 8.392317423, 9.290018847, 10.21067134, 11.15228484, 12.10950422, 13.07831762, 14.05579081, 15.03969019, 16.02818667, 17.01999243, 18.01416217, 19.01002812, 20.00709846, 21.00502277, 22.00355291, 23.00251306, 24.00177721, 25.00125665, 26.00088843, 27.00062802, 28.00044386, 29.00031363}},
/*2*/ {{0, 1, 2, 3, 4, 4.754887502, 5.459431619, 6.129283017, 6.87036472, 7.665335917, 8.491853096, 9.361943774, 10.2632692, 11.18982456, 12.13602985, 13.09737377, 14.06936585, 15.04929552, 16.03499235, 17.02481502, 18.01757508, 19.01244722, 20.00880883, 21.00623293, 22.00440908, 23.00311846, 24.00220528, 25.00155925, 26.00110233, 27.00077917, 28.00055063}},
/*3*/ {{0, 1, 2, 3, 3.906890596, 4.459431619, 5, 5.614709844, 6.247927513, 6.965784285, 7.727920455, 8.539158811, 9.394462695, 10.28771238, 11.20762447, 12.14879432, 13.10639936, 14.07581338, 15.05392588, 16.03827601, 17.02713927, 18.01923236, 19.0136171, 20.00963729, 21.00681914, 22.00482395, 23.00341171, 24.00241262, 25.00170588, 26.00120598, 27.00085241}},
/*4*/ {{0, 1, 2, 3, 3.700439718, 4.087462841, 4.584962501, 5.129283017, 5.672425342, 6.321928095, 7.011227255, 7.761551232, 8.566054038, 9.413627929, 10.30149619, 11.21735191, 12.15608308, 13.11146174, 14.07948478, 15.05651071, 16.04011845, 17.0284457, 18.02015526, 19.01427116, 20.0101019, 21.00714706, 22.00505602, 23.0035759, 24.00252877, 25.00178798, 26.00126401}},
/*5*/ {{0, 1, 2, 3, 3.459431619, 3.807354922, 4.247927513, 4.700439718, 5.169925001, 5.727920455, 6.357552005, 7.033423002, 7.781359714, 8.581200582, 9.426264755, 10.30947635, 11.22339841, 12.16050175, 13.11471839, 14.08173308, 15.06149777, 16.04127413, 17.02926566, 18.02074126, 19.01468524, 20.01039425, 21.00735446, 22.00520271, 23.00367969, 24.00260216, 25.0018399}},
/*6*/ {{0, 1, 2, 2.807354922, 3.169925001, 3.584962501, 3.906890596, 4.321928095, 4.700439718, 5.209453366, 5.754887502, 6.375039431, 7.055282436, 7.794415866, 8.592457037, 9.434628228, 10.31514956, 11.22821744, 12.16364968, 13.11699368, 14.08339622, 15.05930221, 16.04210821, 17.02985876, 18.0211535, 19.01497939, 20.01060323, 21.00750229, 22.00530724, 23.00375379, 24.00265452}},
/*7*/ {{0, 1, 2, 2.807354922, 3, 3.321928095, 3.584962501, 4, 4.321928095, 4.754887502, 5.247927513, 5.781359714, 6.392317423, 7.06608919, 7.807354922, 8.599912842, 9.440869168, 10.32080055, 11.23122118, 12.16616308, 13.11877889, 14.08472536, 15.06023151, 16.04277086, 17.03032228, 18.02148428, 19.0152163, 20.01076984, 21.00762, 22.00539086, 23.0038128}},
/*8*/ {{0, 1, 2, 2.584962501, 2.807354922, 3.169925001, 3.321928095, 3.700439718, 4, 4.392317423, 4.807354922, 5.247927513, 5.807354922, 6.409390936, 7.076815597, 7.813781191, 8.607330314, 9.445014846, 10.32418055, 11.23421868, 12.16835873, 13.1203999, 14.08580438, 15.0610336, 16.04332639, 17.03073179, 18.02177162, 19.01541777, 20.01091459, 21.00772264, 22.00546316}},
/*9*/ {{0, 1, 2, 2.321928095, 2.584962501, 3, 3.169925001, 3.459431619, 3.700439718, 4, 4.392317423, 4.807354922, 5.285402219, 5.807354922, 6.426264755, 7.087462841, 7.826548487, 8.614709844, 9.451211112, 10.32755264, 11.23720996, 12.17023805, 13.12185725, 14.08679969, 15.06175089, 16.04386035, 17.03109809, 18.02203723, 19.01560561, 20.01104704, 21.00781707}},
/*10*/ {{0, 1, 2, 2.321928095, 2.584962501, 2.807354922, 3, 3.169925001, 3.459431619, 3.700439718, 4.087462841, 4.392317423, 4.807354922, 5.285402219, 5.832890014, 6.426264755, 7.098032083, 7.832890014, 8.618385502, 9.45532722, 10.33203655, 11.23959853, 12.17211493, 13.12315143, 14.0877943, 15.06246782, 16.04435143, 17.03145353, 18.02229195, 19.01578526, 20.01117265}},
/*11*/ {{0, 1, 2, 2.321928095, 2.321928095, 2.584962501, 2.807354922, 3, 3.169925001, 3.459431619, 3.700439718, 4.087462841, 4.459431619, 4.857980995, 5.321928095, 5.832890014, 6.442943496, 7.108524457, 7.839203788, 8.625708843, 9.459431619, 10.33539035, 11.24198315, 12.17398937, 13.12444446, 14.08878824, 15.06314225, 16.04484233, 17.03179811, 18.02253579, 19.01595672}},
/*12*/ {{0, 1, 2, 2, 2.321928095, 2.321928095, 2.584962501, 2.807354922, 3, 3.169925001, 3.459431619, 3.807354922, 4.087462841, 4.459431619, 4.857980995, 5.321928095, 5.857980995, 6.459431619, 7.118941073, 7.845490051, 8.62935662, 9.463524373, 10.33873638, 11.24436384, 12.17586138, 13.12573633, 14.08969874, 15.06381637, 16.04531174, 17.03213185, 18.02277416}},
/*13*/ {{0, 1, 2, 2, 2.321928095, 2.321928095, 2.584962501, 2.584962501, 2.807354922, 3, 3.321928095, 3.459431619, 3.807354922, 4.087462841, 4.459431619, 4.857980995, 5.357552005, 5.882643049, 6.459431619, 7.129283017, 7.851749041, 8.636624621, 9.46760555, 10.34207467, 11.2467406, 12.17741954, 13.12702704, 14.09060867, 15.06444807, 16.04575966, 17.0324655}},
/*14*/ {{0, 1, 1.584962501, 2, 2, 2.321928095, 2.321928095, 2.584962501, 2.584962501, 2.807354922, 3, 3.321928095, 3.584962501, 3.807354922, 4.169925001, 4.459431619, 4.906890596, 5.357552005, 5.882643049, 6.475733431, 7.139551352, 7.857980995, 8.64385619, 9.47370575, 10.34429591, 11.24911345, 12.1792871, 13.1283166, 14.09151803, 15.06507949, 16.04622877}},
/*15*/ {{0, 1, 1.584962501, 2, 2, 2, 2.321928095, 2.321928095, 2.584962501, 2.807354922, 2.807354922, 3.169925001, 3.321928095, 3.584962501, 3.807354922, 4.169925001, 4.523561956, 4.906890596, 5.357552005, 5.906890596, 6.491853096, 7.14974712, 7.87036472, 8.647458426, 9.477758266, 10.34762137, 11.25148241, 12.18084157, 13.12944402, 14.09234422, 15.06571064}},
/*16*/ {{0, 1, 1.584962501, 1.584962501, 2, 2, 2, 2.321928095, 2.321928095, 2.584962501, 2.807354922, 3, 3.169925001, 3.321928095, 3.584962501, 3.906890596, 4.169925001, 4.523561956, 4.906890596, 5.392317423, 5.906890596, 6.491853096, 7.159871337, 7.876516947, 8.654636029, 9.481799432, 10.35093918, 11.25384748, 12.18270471, 13.13073143, 14.09325249}},
/*17*/ {{0, 1, 1.584962501, 1.584962501, 1.584962501, 2, 2, 2, 2.321928095, 2.321928095, 2.584962501, 2.807354922, 3, 3.169925001, 3.321928095, 3.584962501, 3.906890596, 4.169925001, 4.523561956, 4.95419631, 5.392317423, 5.930737338, 6.50779464, 7.159871337, 7.882643049, 8.658211483, 9.485829309, 10.35424938, 11.25620869, 12.1842555, 13.13185696}},
/*18*/ {{0, 1, 1.584962501, 1.584962501, 1.584962501, 2, 2, 2, 2.321928095, 2.321928095, 2.584962501, 2.584962501, 2.807354922, 3, 3.169925001, 3.321928095, 3.584962501, 3.906890596, 4.169925001, 4.584962501, 4.95419631, 5.426264755, 5.930737338, 6.523561956, 7.169925001, 7.888743249, 8.665335917, 9.48984796, 10.357552, 11.25856603, 12.18580462}},
/*19*/ {{0, 1, 1.584962501, 1.584962501, 1.584962501, 1.584962501, 2, 2, 2, 2.321928095, 2.321928095, 2.584962501, 2.584962501, 2.807354922, 3, 3.169925001, 3.459431619, 3.700439718, 3.906890596, 4.247927513, 4.584962501, 4.95419631, 5.426264755, 5.95419631, 6.523561956, 7.17990909, 7.894817763, 8.668884984, 9.493855449, 10.35974956, 11.26091953}},
/*20*/ {{0, 1, 1.584962501, 1.584962501, 1.584962501, 1.584962501, 1.584962501, 2, 2, 2, 2.321928095, 2.321928095, 2.584962501, 2.584962501, 2.807354922, 3, 3.169925001, 3.459431619, 3.700439718, 3.906890596, 4.247927513, 4.584962501, 5, 5.426264755, 5.95419631, 6.539158811, 7.189824559, 7.900866808, 8.675957033, 9.497851837, 10.36303963}},
/*21*/ {{0, 1, 1, 1.584962501, 1.584962501, 1.584962501, 1.584962501, 2, 2, 2, 2, 2.321928095, 2.321928095, 2.584962501, 2.584962501, 2.807354922, 3, 3.169925001, 3.459431619, 3.700439718, 4, 4.247927513, 4.584962501, 5, 5.459431619, 5.977279923, 6.554588852, 7.199672345, 7.906890596, 8.6794801, 9.501837185}},
/*22*/ {{0, 1, 1, 1.584962501, 1.584962501, 1.584962501, 1.584962501, 1.584962501, 2, 2, 2, 2.321928095, 2.321928095, 2.321928095, 2.584962501, 2.807354922, 2.807354922, 3, 3.321928095, 3.459431619, 3.700439718, 4, 4.247927513, 4.64385619, 5, 5.459431619, 5.977279923, 6.554588852, 7.209453366, 7.912889336, 8.682994584}},
/*23*/ {{0, 1, 1, 1, 1.584962501, 1.584962501, 1.584962501, 1.584962501, 1.584962501, 2, 2, 2, 2.321928095, 2.321928095, 2.321928095, 2.584962501, 2.807354922, 2.807354922, 3, 3.321928095, 3.459431619, 3.700439718, 4, 4.321928095, 4.64385619, 5.044394119, 5.491853096, 6, 6.569855608, 7.209453366, 7.918863237}},
/*24*/ {{0, 1, 1, 1, 1.584962501, 1.584962501, 1.584962501, 1.584962501, 1.584962501, 1.584962501, 2, 2, 2, 2.321928095, 2.321928095, 2.584962501, 2.584962501, 2.807354922, 3, 3.169925001, 3.321928095, 3.459431619, 3.700439718, 4, 4.321928095, 4.64385619, 5.044394119, 5.491853096, 6, 6.584962501, 7.21916852}},
/*25*/ {{0, 1, 1, 1, 1, 1.584962501, 1.584962501, 1.584962501, 1.584962501, 1.584962501, 2, 2, 2, 2, 2.321928095, 2.321928095, 2.584962501, 2.584962501, 2.807354922, 3, 3.169925001, 3.321928095, 3.459431619, 3.807354922, 4, 4.321928095, 4.64385619, 5.044394119, 5.491853096, 6.022367813, 6.584962501}},
/*26*/ {{0, 1, 1, 1, 1, 1.584962501, 1.584962501, 1.584962501, 1.584962501, 1.584962501, 1.584962501, 2, 2, 2, 2, 2.321928095, 2.321928095, 2.584962501, 2.584962501, 2.807354922, 3, 3.169925001, 3.321928095, 3.584962501, 3.807354922, 4, 4.321928095, 4.700439718, 5.087462841, 5.523561956, 6.022367813}},
/*27*/ {{0, 1, 1, 1, 1, 1, 1.584962501, 1.584962501, 1.584962501, 1.584962501, 1.584962501, 1.584962501, 2, 2, 2, 2.321928095, 2.321928095, 2.321928095, 2.584962501, 2.584962501, 2.807354922, 3, 3.169925001, 3.321928095, 3.584962501, 3.807354922, 4.087462841, 4.392317423, 4.700439718, 5.087462841, 5.523561956}},
/*28*/ {{0, 1, 1, 1, 1, 1, 1, 1.584962501, 1.584962501, 1.584962501, 1.584962501, 1.584962501, 1.584962501, 2, 2, 2, 2.321928095, 2.321928095, 2.321928095, 2.584962501, 2.584962501, 2.807354922, 3, 3.169925001, 3.321928095, 3.584962501, 3.807354922, 4.087462841, 4.392317423, 4.700439718, 5.087462841}},
/*29*/ {{0, 1, 1, 1, 1, 1, 1, 1.584962501, 1.584962501, 1.584962501, 1.584962501, 1.584962501, 1.584962501, 2, 2, 2, 2, 2.321928095, 2.321928095, 2.321928095, 2.584962501, 2.807354922, 2.807354922, 3, 3.169925001, 3.321928095, 3.584962501, 3.807354922, 4.087462841, 4.392317423, 4.754887502}},
/*30*/ {{0, 1, 1, 1, 1, 1, 1, 1, 1.584962501, 1.584962501, 1.584962501, 1.584962501, 1.584962501, 1.584962501, 2, 2, 2, 2, 2.321928095, 2.321928095, 2.584962501, 2.584962501, 2.807354922, 2.807354922, 3, 3.169925001, 3.459431619, 3.584962501, 3.807354922, 4.087462841, 4.392317423}},
/*31*/ {{0, 1, 1, 1, 1, 1, 1, 1, 1, 1.584962501, 1.584962501, 1.584962501, 1.584962501, 1.584962501, 1.584962501, 2, 2, 2, 2, 2.321928095, 2.321928095, 2.584962501, 2.584962501, 2.807354922, 2.807354922, 3, 3.169925001, 3.459431619, 3.584962501, 3.906890596, 4.087462841}},
/*32*/ {{0, 1, 1, 1, 1, 1, 1, 1, 1, 1.584962501, 1.584962501, 1.584962501, 1.584962501, 1.584962501, 1.584962501, 1.584962501, 2, 2, 2, 2.321928095, 2.321928095, 2.321928095, 2.584962501, 2.584962501, 2.807354922, 3, 3, 3.321928095, 3.459431619, 3.700439718, 3.906890596}},
}};
std::vector<std::vector<double>> logbinSizes_50bit{{/*0 */ {{0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30}},
/*1 */ {{0, 1, 2, 3, 4, 5, 5.977279923, 6.794415866, 7.622051819, 8.471675214, 9.350939182, 10.25738784, 11.18673329, 12.13442632, 13.09638573, 14.06886223, 15.04904021, 16.03484194, 17.02472847, 18.01752615, 19.01241449, 20.00878969, 21.00622128, 22.00440154, 23.00311348, 24.0022021, 25.00155732, 26.00110119, 27.00077858, 28.00055042, 29.00038906}},
/*2 */ {{0, 1, 2, 3, 4, 4.95419631, 5.64385619, 6.321928095, 7.033423002, 7.787902559, 8.588714636, 9.436711542, 10.31967212, 11.23122118, 12.16647695, 13.11926538, 14.08514046, 15.0606115, 16.04307002, 17.03055938, 18.02165778, 19.01534154, 20.01085997, 21.00768569, 22.00543781, 23.00384642, 24.00272043, 25.0019238, 26.0013603, 27.00096173, 28.00067986}},
/*3 */ {{0, 1, 2, 3, 4, 4.700439718, 5.247927513, 5.832890014, 6.459431619, 7.129283017, 7.857980995, 8.64385619, 9.475733431, 10.34762137, 11.25207404, 12.18146288, 13.12992693, 14.09275714, 15.06604713, 16.04691083, 17.03328318, 18.02359194, 19.01671037, 20.01183055, 21.00837254, 22.00592363, 23.00419011, 24.00296348, 25.00209568, 26.00148182, 27.00104763}},
/*4 */ {{0, 1, 2, 3, 3.906890596, 4.459431619, 4.906890596, 5.392317423, 5.930737338, 6.523561956, 7.17990909, 7.894817763, 8.672425342, 9.495855027, 10.36303963, 11.26268214, 12.18920683, 13.13554898, 14.0967975, 15.06890421, 16.04895509, 17.03474524, 18.02462568, 19.01744187, 20.01234901, 21.00873909, 22.00618292, 23.00437376, 24.00309332, 25.00218746, 26.00154671}},
/*5 */ {{0, 1, 2, 3, 3.807354922, 4.169925001, 4.584962501, 5, 5.459431619, 5.977279923, 6.554588852, 7.209453366, 7.918863237, 8.686500527, 9.50779464, 10.37177664, 11.26912668, 12.19383333, 13.13891172, 14.09918341, 15.06149777, 16.05018877, 17.03560458, 18.02523691, 19.01787679, 20.01265727, 21.0089572, 22.00633738, 23.00448281, 24.00317045, 25.00224203}},
/*6 */ {{0, 1, 2, 3, 3.584962501, 3.906890596, 4.247927513, 4.64385619, 5.044394119, 5.491853096, 6, 6.584962501, 7.22881869, 7.930737338, 8.696967526, 9.515699838, 10.37721053, 11.2737956, 12.19690944, 13.1411492, 14.10082657, 15.07175563, 16.05099646, 17.03618435, 18.02564786, 19.01816757, 20.01286183, 21.00910213, 22.00644011, 23.0045555, 24.00322193}},
/*7 */ {{0, 1, 2, 3, 3.459431619, 3.700439718, 4, 4.321928095, 4.700439718, 5.087462841, 5.523561956, 6.022367813, 6.599912842, 7.238404739, 7.942514505, 8.707359132, 9.52160044, 10.38154295, 11.27670602, 12.19936562, 13.14290479, 14.10197567, 15.07263508, 16.05159132, 17.03661365, 18.025956, 19.01838494, 20.01301592, 21.0092115, 22.0065175, 23.00461019}},
/*8 */ {{0, 1, 2, 3, 3.321928095, 3.459431619, 3.807354922, 4.087462841, 4.392317423, 4.700439718, 5.087462841, 5.523561956, 6.044394119, 6.614709844, 7.247927513, 7.948367232, 8.710806434, 9.527477006, 10.3858624, 11.27961058, 12.20120501, 13.14418024, 14.10295989, 15.07330478, 16.052101, 17.03697846, 18.02621002, 19.01856696, 20.01314408, 21.00930241, 22.00658153}},
/*9 */ {{0, 1, 2, 2.807354922, 3.169925001, 3.321928095, 3.584962501, 3.807354922, 4.087462841, 4.392317423, 4.700439718, 5.129283017, 5.554588852, 6.044394119, 6.62935662, 7.257387843, 7.960001932, 8.717676423, 9.531381461, 10.38801729, 11.28193003, 12.20304206, 13.14545456, 14.10386149, 15.07397416, 16.05254682, 17.03728955, 18.02643699, 19.01872722, 20.0132586, 21.00938375}},
/*10*/ {{0, 1, 2, 2.807354922, 3, 3.169925001, 3.321928095, 3.584962501, 3.807354922, 4.087462841, 4.392317423, 4.754887502, 5.129283017, 5.554588852, 6.06608919, 6.62935662, 7.266786541, 7.965784285, 8.724513853, 9.535275377, 10.39124359, 11.28366717, 12.20457114, 13.14656868, 14.10468065, 15.07455962, 16.05297129, 17.03760057, 18.02665311, 19.01887933, 20.0133663}},
/*11*/ {{0, 1, 2, 2.584962501, 2.807354922, 3, 3.169925001, 3.459431619, 3.584962501, 3.906890596, 4.087462841, 4.392317423, 4.754887502, 5.129283017, 5.584962501, 6.087462841, 6.64385619, 7.276124405, 7.971543554, 8.727920455, 9.539158811, 10.39446269, 11.28598011, 12.20609861, 13.14768193, 14.10549934, 15.07510305, 16.05339563, 17.03789009, 18.0268584, 19.01902598}},
/*12*/ {{0, 1, 2, 2.584962501, 2.807354922, 2.807354922, 3, 3.169925001, 3.459431619, 3.700439718, 3.906890596, 4.169925001, 4.459431619, 4.754887502, 5.169925001, 5.584962501, 6.087462841, 6.64385619, 7.276124405, 7.977279923, 8.731319031, 9.54303182, 10.39660478, 11.28771238, 12.20762447, 13.14879432, 14.10623576, 15.07568805, 16.05377743, 17.03816882, 18.02705826}},
/*13*/ {{0, 1, 2, 2.321928095, 2.584962501, 2.807354922, 3, 3.169925001, 3.321928095, 3.459431619, 3.700439718, 3.906890596, 4.169925001, 4.459431619, 4.807354922, 5.169925001, 5.614709844, 6.087462841, 6.658211483, 7.285402219, 7.982993575, 8.73809226, 9.544964433, 10.39981196, 11.29001885, 12.20884399, 13.14990586, 14.10705357, 15.07623105, 16.05418033, 17.0384475}},
/*14*/ {{0, 1, 2, 2.321928095, 2.584962501, 2.584962501, 2.807354922, 3, 3.169925001, 3.321928095, 3.459431619, 3.700439718, 3.906890596, 4.169925001, 4.459431619, 4.807354922, 5.169925001, 5.614709844, 6.108524457, 6.672425342, 7.294620749, 7.988684687, 8.741466986, 9.548821908, 10.40194612, 11.29174628, 12.21036695, 13.15085792, 14.1077892, 15.07677385, 16.05456193}},
/*15*/ {{0, 1, 2, 2.321928095, 2.321928095, 2.584962501, 2.584962501, 2.807354922, 3, 3.169925001, 3.321928095, 3.459431619, 3.700439718, 3.906890596, 4.169925001, 4.459431619, 4.807354922, 5.209453366, 5.614709844, 6.108524457, 6.672425342, 7.303780748, 7.994353437, 8.744833837, 9.552669098, 10.40514146, 11.29404631, 12.21188829, 13.15196787, 14.10852446, 15.07731645}},
/*16*/ {{0, 1, 2, 2.321928095, 2.321928095, 2.321928095, 2.584962501, 2.807354922, 2.807354922, 3, 3.169925001, 3.321928095, 3.459431619, 3.700439718, 3.906890596, 4.169925001, 4.523561956, 4.807354922, 5.209453366, 5.64385619, 6.129283017, 6.686500527, 7.312882955, 8, 8.751544059, 9.556506055, 10.40726776, 11.29576893, 12.21340804, 13.15291858, 14.10925934}},
/*17*/ {{0, 1, 2, 2, 2.321928095, 2.321928095, 2.584962501, 2.584962501, 2.807354922, 2.807354922, 3, 3.169925001, 3.321928095, 3.584962501, 3.700439718, 4, 4.247927513, 4.523561956, 4.857980995, 5.209453366, 5.64385619, 6.129283017, 6.686500527, 7.312882955, 8.005624549, 8.754887502, 9.560332834, 10.41045135, 11.2974895, 12.21462269, 13.15402694}},
/*18*/ {{0, 1, 2, 2, 2.321928095, 2.321928095, 2.321928095, 2.584962501, 2.584962501, 2.807354922, 2.807354922, 3, 3.169925001, 3.321928095, 3.584962501, 3.700439718, 4, 4.247927513, 4.523561956, 4.857980995, 5.209453366, 5.64385619, 6.14974712, 6.700439718, 7.321928095, 8.011227255, 8.758223215, 9.562242424, 10.41256985, 11.2997804, 12.21613956}},
/*19*/ {{0, 1, 2, 2, 2, 2.321928095, 2.321928095, 2.321928095, 2.584962501, 2.584962501, 2.807354922, 2.807354922, 3, 3.169925001, 3.321928095, 3.584962501, 3.807354922, 4, 4.247927513, 4.523561956, 4.857980995, 5.247927513, 5.672425342, 6.14974712, 6.714245518, 7.330916878, 8.016808288, 8.764871591, 9.566054038, 10.41468524, 11.30149619}},
/*20*/ {{0, 1, 1.584962501, 2, 2, 2, 2.321928095, 2.321928095, 2.321928095, 2.584962501, 2.584962501, 2.807354922, 3, 3, 3.169925001, 3.321928095, 3.584962501, 3.807354922, 4, 4.247927513, 4.523561956, 4.857980995, 5.247927513, 5.672425342, 6.169925001, 6.714245518, 7.339850003, 8.022367813, 8.768184325, 9.569855608, 10.41785251}},
/*21*/ {{0, 1, 1.584962501, 2, 2, 2, 2, 2.321928095, 2.321928095, 2.321928095, 2.584962501, 2.584962501, 2.807354922, 3, 3, 3.169925001, 3.459431619, 3.584962501, 3.807354922, 4, 4.247927513, 4.584962501, 4.906890596, 5.247927513, 5.700439718, 6.169925001, 6.727920455, 7.339850003, 8.027905997, 8.77148947, 9.573647187}},
/*22*/ {{0, 1, 1.584962501, 2, 2, 2, 2, 2, 2.321928095, 2.321928095, 2.584962501, 2.584962501, 2.584962501, 2.807354922, 3, 3.169925001, 3.321928095, 3.459431619, 3.584962501, 3.807354922, 4, 4.321928095, 4.584962501, 4.906890596, 5.285402219, 5.700439718, 6.189824559, 6.727920455, 7.348728154, 8.033423002, 8.77478706}},
/*23*/ {{0, 1, 1.584962501, 1.584962501, 2, 2, 2, 2, 2.321928095, 2.321928095, 2.321928095, 2.584962501, 2.584962501, 2.807354922, 2.807354922, 3, 3.169925001, 3.321928095, 3.459431619, 3.584962501, 3.807354922, 4.087462841, 4.321928095, 4.584962501, 4.906890596, 5.285402219, 5.700439718, 6.189824559, 6.741466986, 7.357552005, 8.038918989}},
/*24*/ {{0, 1, 1.584962501, 1.584962501, 1.584962501, 2, 2, 2, 2, 2.321928095, 2.321928095, 2.321928095, 2.584962501, 2.584962501, 2.807354922, 2.807354922, 3, 3.169925001, 3.321928095, 3.459431619, 3.584962501, 3.807354922, 4.087462841, 4.321928095, 4.584962501, 4.906890596, 5.285402219, 5.727920455, 6.209453366, 6.741466986, 7.357552005}},
/*25*/ {{0, 1, 1.584962501, 1.584962501, 1.584962501, 2, 2, 2, 2, 2, 2.321928095, 2.321928095, 2.321928095, 2.584962501, 2.584962501, 2.807354922, 2.807354922, 3, 3.169925001, 3.321928095, 3.459431619, 3.700439718, 3.807354922, 4.087462841, 4.321928095, 4.584962501, 4.95419631, 5.321928095, 5.727920455, 6.209453366, 6.754887502}},
/*26*/ {{0, 1, 1.584962501, 1.584962501, 1.584962501, 1.584962501, 2, 2, 2, 2, 2, 2.321928095, 2.321928095, 2.321928095, 2.584962501, 2.584962501, 2.807354922, 2.807354922, 3, 3.169925001, 3.321928095, 3.459431619, 3.700439718, 3.906890596, 4.087462841, 4.321928095, 4.64385619, 4.95419631, 5.321928095, 5.727920455, 6.209453366}},
/*27*/ {{0, 1, 1.584962501, 1.584962501, 1.584962501, 1.584962501, 1.584962501, 2, 2, 2, 2, 2.321928095, 2.321928095, 2.321928095, 2.321928095, 2.584962501, 2.584962501, 2.807354922, 2.807354922, 3, 3.169925001, 3.321928095, 3.459431619, 3.700439718, 3.906890596, 4.087462841, 4.321928095, 4.64385619, 4.95419631, 5.321928095, 5.754887502}},
/*28*/ {{0, 1, 1.584962501, 1.584962501, 1.584962501, 1.584962501, 1.584962501, 1.584962501, 2, 2, 2, 2, 2.321928095, 2.321928095, 2.321928095, 2.584962501, 2.584962501, 2.584962501, 2.807354922, 3, 3, 3.169925001, 3.321928095, 3.459431619, 3.700439718, 3.906890596, 4.087462841, 4.392317423, 4.64385619, 4.95419631, 5.321928095}},
/*29*/ {{0, 1, 1.584962501, 1.584962501, 1.584962501, 1.584962501, 1.584962501, 1.584962501, 2, 2, 2, 2, 2, 2.321928095, 2.321928095, 2.321928095, 2.584962501, 2.584962501, 2.584962501, 2.807354922, 3, 3, 3.169925001, 3.321928095, 3.584962501, 3.700439718, 3.906890596, 4.169925001, 4.392317423, 4.64385619, 5}},
/*30*/ {{0, 1, 1.584962501, 1.584962501, 1.584962501, 1.584962501, 1.584962501, 1.584962501, 1.584962501, 2, 2, 2, 2, 2, 2.321928095, 2.321928095, 2.321928095, 2.584962501, 2.584962501, 2.807354922, 2.807354922, 3, 3, 3.169925001, 3.321928095, 3.584962501, 3.700439718, 3.906890596, 4.169925001, 4.392317423, 4.700439718}},
/*31*/ {{0, 1, 1, 1.584962501, 1.584962501, 1.584962501, 1.584962501, 1.584962501, 1.584962501, 1.584962501, 2, 2, 2, 2, 2, 2.321928095, 2.321928095, 2.321928095, 2.584962501, 2.584962501, 2.807354922, 2.807354922, 3, 3.169925001, 3.169925001, 3.321928095, 3.584962501, 3.700439718, 3.906890596, 4.169925001, 4.392317423}},
/*32*/ {{0, 1, 1, 1.584962501, 1.584962501, 1.584962501, 1.584962501, 1.584962501, 1.584962501, 1.584962501, 1.584962501, 2, 2, 2, 2, 2.321928095, 2.321928095, 2.321928095, 2.321928095, 2.584962501, 2.584962501, 2.807354922, 2.807354922, 3, 3.169925001, 3.321928095, 3.459431619, 3.584962501, 3.700439718, 3.906890596, 4.169925001}}}};
std::vector<std::vector<double>> logbinSizes_60bit{{/*0*/ {{0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32}},
/*1*/ {{0, 1, 2, 3, 4, 5, 5.97728, 6.79442, 7.62205, 8.47168, 9.35094, 10.2574, 11.1867, 12.1344, 13.0964, 14.0689, 15.049, 16.0348, 17.0247, 18.0175, 19.0124, 20.0088, 21.0062, 22.0044, 23.0031, 24.0022, 25.0016, 26.0011, 27.0008, 28.0006, 29.0004}},
/*2*/ {{0, 1, 2, 3, 4, 4.9542, 5.64386, 6.32193, 7.03342, 7.7879, 8.58871, 9.43671, 10.3197, 11.2312, 12.1665, 13.1193, 14.0851, 15.0606, 16.0431, 17.0306, 18.0217, 19.0153, 20.0109, 21.0077, 22.0054, 23.0038, 24.0027, 25.0019, 26.0014, 27.001, 28.0007}},
/*3*/ {{0, 1, 2, 3, 4, 4.70044, 5.24793, 5.83289, 6.45943, 7.12928, 7.85798, 8.64386, 9.47573, 10.3476, 11.2521, 12.1815, 13.1299, 14.0928, 15.066, 16.0469, 17.0333, 18.0236, 19.0167, 20.0118, 21.0084, 22.0059, 23.0042, 24.003, 25.0021, 26.0015, 27.001}},
/*4*/ {{0, 1, 2, 3, 3.90689, 4.45943, 4.90689, 5.39232, 5.93074, 6.52356, 7.17991, 7.89482, 8.67243, 9.49586, 10.363, 11.2627, 12.1892, 13.1355, 14.0968, 15.0689, 16.049, 17.0347, 18.0246, 19.0174, 20.0123, 21.0087, 22.0062, 23.0044, 24.0031, 25.0022, 26.0015}},
/*5*/ {{0, 1, 2, 3, 3.80735, 4.16993, 4.58496, 5, 5.45943, 5.97728, 6.55459, 7.20945, 7.91886, 8.6865, 9.50779, 10.3718, 11.2691, 12.1938, 13.1389, 14.0992, 15.0615, 16.0502, 17.0356, 18.0252, 19.0179, 20.0127, 21.009, 22.0063, 23.0045, 24.0032, 25.0022}},
/*6*/ {{0, 1, 2, 3, 3.58496, 3.90689, 4.24793, 4.64386, 5.04439, 5.49185, 6, 6.58496, 7.22882, 7.93074, 8.69697, 9.5157, 10.3772, 11.2738, 12.1969, 13.1411, 14.1008, 15.0718, 16.051, 17.0362, 18.0256, 19.0182, 20.0129, 21.0091, 22.0064, 23.0046, 24.0032}},
/*7*/ {{0, 1, 2, 3, 3.45943, 3.70044, 4, 4.32193, 4.70044, 5.08746, 5.52356, 6.02237, 6.59991, 7.2384, 7.94251, 8.70736, 9.5216, 10.3815, 11.2767, 12.1994, 13.1429, 14.102, 15.0726, 16.0516, 17.0366, 18.026, 19.0184, 20.013, 21.0092, 22.0065, 23.0046}},
/*8*/ {{0, 1, 2, 3, 3.32193, 3.45943, 3.80735, 4.08746, 4.39232, 4.70044, 5.08746, 5.52356, 6.04439, 6.61471, 7.24793, 7.94837, 8.71081, 9.52748, 10.3859, 11.2796, 12.2012, 13.1442, 14.103, 15.0733, 16.0521, 17.037, 18.0262, 19.0186, 20.0131, 21.0093, 22.0066}},
/*9*/ {{0, 1, 2, 2.80735, 3.16993, 3.32193, 3.58496, 3.80735, 4.08746, 4.39232, 4.70044, 5.12928, 5.55459, 6.04439, 6.62936, 7.25739, 7.96, 8.71768, 9.53138, 10.388, 11.2819, 12.203, 13.1455, 14.1039, 15.074, 16.0525, 17.0373, 18.0264, 19.0187, 20.0133, 21.0094}},
/*10*/ {{0, 1, 2, 2.80735, 3, 3.16993, 3.32193, 3.58496, 3.80735, 4.08746, 4.39232, 4.75489, 5.12928, 5.55459, 6.06609, 6.62936, 7.26679, 7.96578, 8.72451, 9.53528, 10.3912, 11.2837, 12.2046, 13.1466, 14.1047, 15.0746, 16.053, 17.0376, 18.0267, 19.0189, 20.0134}},
/*11*/ {{0, 1, 2, 2.58496, 2.80735, 3, 3.16993, 3.45943, 3.58496, 3.90689, 4.08746, 4.39232, 4.75489, 5.12928, 5.58496, 6.08746, 6.64386, 7.27612, 7.97154, 8.72792, 9.53916, 10.3945, 11.286, 12.2061, 13.1477, 14.1055, 15.0751, 16.0534, 17.0379, 18.0269, 19.019}},
/*12*/ {{0, 1, 2, 2.58496, 2.80735, 2.80735, 3, 3.16993, 3.45943, 3.70044, 3.90689, 4.16993, 4.45943, 4.75489, 5.16993, 5.58496, 6.08746, 6.64386, 7.27612, 7.97728, 8.73132, 9.54303, 10.3966, 11.2877, 12.2076, 13.1488, 14.1062, 15.0757, 16.0538, 17.0382, 18.0271}},
/*13*/ {{0, 1, 2, 2.32193, 2.58496, 2.80735, 3, 3.16993, 3.32193, 3.45943, 3.70044, 3.90689, 4.16993, 4.45943, 4.80735, 5.16993, 5.61471, 6.08746, 6.65821, 7.2854, 7.98299, 8.73809, 9.54496, 10.3998, 11.29, 12.2088, 13.1499, 14.1071, 15.0762, 16.0542, 17.0384}},
/*14*/ {{0, 1, 2, 2.32193, 2.58496, 2.58496, 2.80735, 3, 3.16993, 3.32193, 3.45943, 3.70044, 3.90689, 4.16993, 4.45943, 4.80735, 5.16993, 5.61471, 6.10852, 6.67243, 7.29462, 7.98868, 8.74147, 9.54882, 10.4019, 11.2917, 12.2104, 13.1509, 14.1078, 15.0768, 16.0546}},
/*15*/ {{0, 1, 2, 2.32193, 2.32193, 2.58496, 2.58496, 2.80735, 3, 3.16993, 3.32193, 3.45943, 3.70044, 3.90689, 4.16993, 4.45943, 4.80735, 5.20945, 5.61471, 6.10852, 6.67243, 7.30378, 7.99435, 8.74483, 9.55267, 10.4051, 11.294, 12.2119, 13.152, 14.1085, 15.0773}},
/*16*/ {{0, 1, 2, 2.32193, 2.32193, 2.32193, 2.58496, 2.80735, 2.80735, 3, 3.16993, 3.32193, 3.45943, 3.70044, 3.90689, 4.16993, 4.52356, 4.80735, 5.20945, 5.64386, 6.12928, 6.6865, 7.31288, 8, 8.75154, 9.55651, 10.4073, 11.2958, 12.2134, 13.1529, 14.1093}},
/*17*/ {{0, 1, 2, 2, 2.32193, 2.32193, 2.58496, 2.58496, 2.80735, 2.80735, 3, 3.16993, 3.32193, 3.58496, 3.70044, 4, 4.24793, 4.52356, 4.85798, 5.20945, 5.64386, 6.12928, 6.6865, 7.31288, 8.00562, 8.75489, 9.56033, 10.4105, 11.2975, 12.2146, 13.154}},
/*18*/ {{0, 1, 2, 2, 2.32193, 2.32193, 2.32193, 2.58496, 2.58496, 2.80735, 2.80735, 3, 3.16993, 3.32193, 3.58496, 3.70044, 4, 4.24793, 4.52356, 4.85798, 5.20945, 5.64386, 6.14975, 6.70044, 7.32193, 8.01123, 8.75822, 9.56224, 10.4126, 11.2998, 12.2161}},
/*19*/ {{0, 1, 2, 2, 2, 2.32193, 2.32193, 2.32193, 2.58496, 2.58496, 2.80735, 2.80735, 3, 3.16993, 3.32193, 3.58496, 3.80735, 4, 4.24793, 4.52356, 4.85798, 5.24793, 5.67243, 6.14975, 6.71425, 7.33092, 8.01681, 8.76487, 9.56605, 10.4147, 11.3015}},
/*20*/ {{0, 1, 1.58496, 2, 2, 2, 2.32193, 2.32193, 2.32193, 2.58496, 2.58496, 2.80735, 3, 3, 3.16993, 3.32193, 3.58496, 3.80735, 4, 4.24793, 4.52356, 4.85798, 5.24793, 5.67243, 6.16993, 6.71425, 7.33985, 8.02237, 8.76818, 9.56986, 10.4179}},
/*21*/ {{0, 1, 1.58496, 2, 2, 2, 2, 2.32193, 2.32193, 2.32193, 2.58496, 2.58496, 2.80735, 3, 3, 3.16993, 3.45943, 3.58496, 3.80735, 4, 4.24793, 4.58496, 4.90689, 5.24793, 5.70044, 6.16993, 6.72792, 7.33985, 8.02791, 8.77149, 9.57365}},
/*22*/ {{0, 1, 1.58496, 2, 2, 2, 2, 2, 2.32193, 2.32193, 2.58496, 2.58496, 2.58496, 2.80735, 3, 3.16993, 3.32193, 3.45943, 3.58496, 3.80735, 4, 4.32193, 4.58496, 4.90689, 5.2854, 5.70044, 6.18982, 6.72792, 7.34873, 8.03342, 8.77479}},
/*23*/ {{0, 1, 1.58496, 1.58496, 2, 2, 2, 2, 2.32193, 2.32193, 2.32193, 2.58496, 2.58496, 2.80735, 2.80735, 3, 3.16993, 3.32193, 3.45943, 3.58496, 3.80735, 4.08746, 4.32193, 4.58496, 4.90689, 5.2854, 5.70044, 6.18982, 6.74147, 7.35755, 8.03892}},
/*24*/ {{0, 1, 1.58496, 1.58496, 1.58496, 2, 2, 2, 2, 2.32193, 2.32193, 2.32193, 2.58496, 2.58496, 2.80735, 2.80735, 3, 3.16993, 3.32193, 3.45943, 3.58496, 3.80735, 4.08746, 4.32193, 4.58496, 4.90689, 5.2854, 5.72792, 6.20945, 6.74147, 7.35755}},
/*25*/ {{0, 1, 1.58496, 1.58496, 1.58496, 2, 2, 2, 2, 2, 2.32193, 2.32193, 2.32193, 2.58496, 2.58496, 2.80735, 2.80735, 3, 3.16993, 3.32193, 3.45943, 3.70044, 3.80735, 4.08746, 4.32193, 4.58496, 4.9542, 5.32193, 5.72792, 6.20945, 6.75489}},
/*26*/ {{0, 1, 1.58496, 1.58496, 1.58496, 1.58496, 2, 2, 2, 2, 2, 2.32193, 2.32193, 2.32193, 2.58496, 2.58496, 2.80735, 2.80735, 3, 3.16993, 3.32193, 3.45943, 3.70044, 3.90689, 4.08746, 4.32193, 4.64386, 4.9542, 5.32193, 5.72792, 6.20945}},
/*27*/ {{0, 1, 1.58496, 1.58496, 1.58496, 1.58496, 1.58496, 2, 2, 2, 2, 2.32193, 2.32193, 2.32193, 2.32193, 2.58496, 2.58496, 2.80735, 2.80735, 3, 3.16993, 3.32193, 3.45943, 3.70044, 3.90689, 4.08746, 4.32193, 4.64386, 4.9542, 5.32193, 5.75489}},
/*28*/ {{0, 1, 1.58496, 1.58496, 1.58496, 1.58496, 1.58496, 1.58496, 2, 2, 2, 2, 2.32193, 2.32193, 2.32193, 2.58496, 2.58496, 2.58496, 2.80735, 3, 3, 3.16993, 3.32193, 3.45943, 3.70044, 3.90689, 4.08746, 4.39232, 4.64386, 4.9542, 5.32193}},
/*29*/ {{0, 1, 1.58496, 1.58496, 1.58496, 1.58496, 1.58496, 1.58496, 2, 2, 2, 2, 2, 2.32193, 2.32193, 2.32193, 2.58496, 2.58496, 2.58496, 2.80735, 3, 3, 3.16993, 3.32193, 3.58496, 3.70044, 3.90689, 4.16993, 4.39232, 4.64386, 5}},
/*30*/ {{0, 1, 1.58496, 1.58496, 1.58496, 1.58496, 1.58496, 1.58496, 1.58496, 2, 2, 2, 2, 2, 2.32193, 2.32193, 2.32193, 2.58496, 2.58496, 2.80735, 2.80735, 3, 3, 3.16993, 3.32193, 3.58496, 3.70044, 3.90689, 4.16993, 4.39232, 4.70044}},
/*31*/ {{0, 1, 1, 1.58496, 1.58496, 1.58496, 1.58496, 1.58496, 1.58496, 1.58496, 2, 2, 2, 2, 2, 2.32193, 2.32193, 2.32193, 2.58496, 2.58496, 2.80735, 2.80735, 3, 3.16993, 3.16993, 3.32193, 3.58496, 3.70044, 3.90689, 4.16993, 4.39232}},
/*32*/ {{0, 1, 1, 1.58496, 1.58496, 1.58496, 1.58496, 1.58496, 1.58496, 1.58496, 1.58496, 2, 2, 2, 2, 2.32193, 2.32193, 2.32193, 2.32193, 2.58496, 2.58496, 2.80735, 2.80735, 3, 3.16993, 3.32193, 3.45943, 3.58496, 3.70044, 3.90689, 4.16993}}}};
std::vector<std::vector<double>> logbinSizes_80bit{{/*0*/ {{0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32}},
/*1*/ {{0, 1, 2, 3, 4, 5, 6, 6.88264, 7.69349, 8.53138, 9.39874, 10.2946, 11.2143, 12.1551, 13.1115, 14.0797, 15.0568, 16.0404, 17.0287, 18.0203, 19.0144, 20.0102, 21.0072, 22.0051, 23.0036, 24.0026, 25.0018, 26.0013, 27.0009, 28.0006, 29.0005}},
/*2*/ {{0, 1, 2, 3, 4, 5, 5.78136, 6.45943, 7.14975, 7.88264, 8.66888, 9.49785, 10.3652, 11.2656, 12.1917, 13.1376, 14.0984, 15.0701, 16.0498, 17.0354, 18.0251, 19.0178, 20.0126, 21.0089, 22.0063, 23.0045, 24.0032, 25.0022, 26.0016, 27.0011, 28.0008}},
/*3*/ {{0, 1, 2, 3, 4, 4.90689, 5.45943, 6.02237, 6.61471, 7.25739, 7.96578, 8.72792, 9.5411, 10.3977, 11.2889, 12.2085, 13.1496, 14.107, 15.0762, 16.0542, 17.0385, 18.0273, 19.0193, 20.0137, 21.0097, 22.0069, 23.0048, 24.0034, 25.0024, 26.0017, 27.0012}},
/*4*/ {{0, 1, 2, 3, 4, 4.64386, 5.12928, 5.58496, 6.10852, 6.6865, 7.31288, 8.00562, 8.75822, 9.56415, 10.4136, 11.3009, 12.217, 13.1558, 14.1114, 15.0794, 16.0564, 17.0401, 18.0284, 19.0201, 20.0143, 21.0101, 22.0071, 23.005, 24.0036, 25.0025, 26.0018}},
/*5*/ {{0, 1, 2, 3, 4, 4.45943, 4.80735, 5.20945, 5.67243, 6.16993, 6.72792, 7.34873, 8.02791, 8.77479, 9.57554, 10.4231, 11.3078, 12.2219, 13.1594, 14.1139, 15.0615, 16.0577, 17.041, 18.0291, 19.0206, 20.0146, 21.0103, 22.0073, 23.0052, 24.0037, 25.0026}},
/*6*/ {{0, 1, 2, 3, 3.80735, 4.24793, 4.52356, 4.90689, 5.2854, 5.70044, 6.18982, 6.74147, 7.36632, 8.04439, 8.7879, 9.58496, 10.4284, 11.3117, 12.2252, 13.1616, 14.1155, 15.0823, 16.0585, 17.0416, 18.0295, 19.0209, 20.0148, 21.0105, 22.0074, 23.0052, 24.0037}},
/*7*/ {{0, 1, 2, 3, 3.70044, 4, 4.32193, 4.58496, 4.9542, 5.32193, 5.72792, 6.20945, 6.76818, 7.37504, 8.05528, 8.79442, 9.59059, 10.4325, 11.3151, 12.2273, 13.1632, 14.1167, 15.0831, 16.0591, 17.042, 18.0298, 19.0211, 20.0149, 21.0106, 22.0075, 23.0053}},
/*8*/ {{0, 1, 2, 3, 3.58496, 3.80735, 4.08746, 4.32193, 4.64386, 4.9542, 5.32193, 5.75489, 6.22882, 6.76818, 7.3837, 8.0607, 8.8009, 9.59432, 10.4357, 11.3174, 12.2291, 13.1644, 14.1176, 15.0838, 16.0596, 17.0423, 18.03, 19.0213, 20.0151, 21.0107, 22.0075}},
/*9*/ {{0, 1, 2, 3, 3.45943, 3.70044, 3.90689, 4.08746, 4.39232, 4.64386, 4.9542, 5.35755, 5.75489, 6.24793, 6.78136, 7.39232, 8.06609, 8.80413, 9.59805, 10.4388, 11.3191, 12.2306, 13.1655, 14.1184, 15.0844, 16.06, 17.0426, 18.0302, 19.0214, 20.0152, 21.0107}},
/*10*/ {{0, 1, 2, 3, 3.32193, 3.45943, 3.70044, 3.90689, 4.16993, 4.39232, 4.64386, 5, 5.35755, 5.78136, 6.24793, 6.79442, 7.40088, 8.07146, 8.80735, 9.60177, 10.4419, 11.3214, 12.2321, 13.1666, 14.1191, 15.0849, 16.0604, 17.0429, 18.0304, 19.0215, 20.0153}},
/*11*/ {{0, 1, 2, 3, 3.16993, 3.32193, 3.58496, 3.70044, 3.90689, 4.16993, 4.39232, 4.70044, 5, 5.35755, 5.78136, 6.26679, 6.79442, 7.40088, 8.07682, 8.81378, 9.60363, 10.444, 11.3231, 12.2333, 13.1676, 14.1198, 15.0854, 16.0607, 17.0431, 18.0306, 19.0217}},
/*12*/ {{0, 1, 2, 2.80735, 3, 3.16993, 3.32193, 3.58496, 3.70044, 3.90689, 4.16993, 4.39232, 4.70044, 5, 5.39232, 5.78136, 6.26679, 6.80735, 7.40939, 8.08215, 8.81698, 9.60733, 10.446, 11.3247, 12.2345, 13.1685, 14.1205, 15.0859, 16.0611, 17.0434, 18.0308}},
/*13*/ {{0, 1, 2, 2.80735, 3, 3.16993, 3.32193, 3.45943, 3.58496, 3.80735, 4, 4.16993, 4.45943, 4.70044, 5.04439, 5.39232, 5.80735, 6.2854, 6.80735, 7.41785, 8.08746, 8.82018, 9.61102, 10.4481, 11.3264, 12.236, 13.1695, 14.1211, 15.0864, 16.0614, 17.0436}},
/*14*/ {{0, 1, 2, 2.58496, 2.80735, 3, 3.16993, 3.32193, 3.45943, 3.58496, 3.80735, 4, 4.16993, 4.45943, 4.70044, 5.04439, 5.39232, 5.80735, 6.2854, 6.82018, 7.42626, 8.09276, 8.82337, 9.61287, 10.4512, 11.3281, 12.2372, 13.1704, 14.1219, 15.0868, 16.0618}},
/*15*/ {{0, 1, 2, 2.58496, 2.80735, 2.80735, 3, 3.16993, 3.32193, 3.45943, 3.58496, 3.80735, 4, 4.16993, 4.45943, 4.75489, 5.04439, 5.42626, 5.83289, 6.2854, 6.83289, 7.42626, 8.09803, 8.82972, 9.61655, 10.4533, 11.3298, 12.2384, 13.1712, 14.1225, 15.0873}},
/*16*/ {{0, 1, 2, 2.58496, 2.58496, 2.80735, 3, 3, 3.16993, 3.32193, 3.45943, 3.58496, 3.80735, 4, 4.24793, 4.45943, 4.75489, 5.04439, 5.42626, 5.83289, 6.30378, 6.83289, 7.43463, 8.10329, 8.83289, 9.61839, 10.4553, 11.3315, 12.2396, 13.1721, 14.1232}},
/*17*/ {{0, 1, 2, 2.32193, 2.58496, 2.58496, 2.80735, 3, 3, 3.16993, 3.32193, 3.45943, 3.58496, 3.80735, 4, 4.24793, 4.45943, 4.75489, 5.08746, 5.42626, 5.83289, 6.30378, 6.84549, 7.44294, 8.10852, 8.83605, 9.62205, 10.4574, 11.3332, 12.2408, 13.1731}},
/*18*/ {{0, 1, 2, 2.32193, 2.58496, 2.58496, 2.80735, 2.80735, 3, 3, 3.16993, 3.32193, 3.45943, 3.70044, 3.80735, 4, 4.24793, 4.45943, 4.75489, 5.08746, 5.42626, 5.85798, 6.32193, 6.84549, 7.44294, 8.10852, 8.8392, 9.62571, 10.4594, 11.3348, 12.242}},
/*19*/ {{0, 1, 2, 2.32193, 2.32193, 2.58496, 2.58496, 2.80735, 2.80735, 3, 3, 3.16993, 3.32193, 3.45943, 3.70044, 3.80735, 4, 4.24793, 4.52356, 4.75489, 5.08746, 5.45943, 5.85798, 6.32193, 6.85798, 7.45121, 8.11374, 8.84235, 9.62753, 10.4625, 11.3365}},
/*20*/ {{0, 1, 2, 2.32193, 2.32193, 2.32193, 2.58496, 2.58496, 2.80735, 2.80735, 3, 3.16993, 3.16993, 3.32193, 3.45943, 3.70044, 3.80735, 4.08746, 4.24793, 4.52356, 4.80735, 5.08746, 5.45943, 5.85798, 6.33985, 6.85798, 7.45943, 8.11894, 8.84549, 9.63118, 10.4645}},
/*21*/ {{0, 1, 2, 2.32193, 2.32193, 2.32193, 2.58496, 2.58496, 2.58496, 2.80735, 2.80735, 3, 3.16993, 3.16993, 3.32193, 3.58496, 3.70044, 3.90689, 4.08746, 4.24793, 4.52356, 4.80735, 5.12928, 5.45943, 5.88264, 6.33985, 6.87036, 7.45943, 8.12412, 8.85175, 9.633}},
/*22*/ {{0, 1, 2, 2, 2.32193, 2.32193, 2.32193, 2.58496, 2.58496, 2.58496, 2.80735, 2.80735, 3, 3.16993, 3.32193, 3.32193, 3.58496, 3.70044, 3.90689, 4.08746, 4.32193, 4.52356, 4.80735, 5.12928, 5.49185, 5.88264, 6.33985, 6.87036, 7.46761, 8.12928, 8.85487}},
/*23*/ {{0, 1, 2, 2, 2.32193, 2.32193, 2.32193, 2.32193, 2.58496, 2.58496, 2.58496, 2.80735, 2.80735, 3, 3.16993, 3.32193, 3.45943, 3.58496, 3.70044, 3.90689, 4.08746, 4.32193, 4.52356, 4.80735, 5.12928, 5.49185, 5.88264, 6.35755, 6.88264, 7.47573, 8.13443}},
/*24*/ {{0, 1, 2, 2, 2, 2.32193, 2.32193, 2.32193, 2.32193, 2.58496, 2.58496, 2.80735, 2.80735, 3, 3, 3.16993, 3.32193, 3.45943, 3.58496, 3.70044, 3.90689, 4.08746, 4.32193, 4.58496, 4.80735, 5.12928, 5.49185, 5.90689, 6.35755, 6.88264, 7.47573}},
/*25*/ {{0, 1, 2, 2, 2, 2, 2.32193, 2.32193, 2.32193, 2.32193, 2.58496, 2.58496, 2.80735, 2.80735, 3, 3, 3.16993, 3.32193, 3.45943, 3.58496, 3.70044, 3.90689, 4.08746, 4.32193, 4.58496, 4.85798, 5.16993, 5.49185, 5.90689, 6.37504, 6.89482}},
/*26*/ {{0, 1, 2, 2, 2, 2, 2, 2.32193, 2.32193, 2.32193, 2.58496, 2.58496, 2.58496, 2.80735, 2.80735, 3, 3, 3.16993, 3.32193, 3.45943, 3.58496, 3.70044, 3.90689, 4.08746, 4.32193, 4.58496, 4.85798, 5.16993, 5.52356, 5.90689, 6.37504}},
/*27*/ {{0, 1, 1.58496, 2, 2, 2, 2, 2, 2.32193, 2.32193, 2.32193, 2.58496, 2.58496, 2.58496, 2.80735, 2.80735, 3, 3, 3.16993, 3.32193, 3.45943, 3.58496, 3.80735, 3.90689, 4.16993, 4.32193, 4.58496, 4.85798, 5.16993, 5.52356, 5.93074}},
/*28*/ {{0, 1, 1.58496, 2, 2, 2, 2, 2, 2.32193, 2.32193, 2.32193, 2.32193, 2.58496, 2.58496, 2.58496, 2.80735, 2.80735, 3, 3, 3.16993, 3.32193, 3.45943, 3.58496, 3.80735, 3.90689, 4.16993, 4.39232, 4.58496, 4.85798, 5.16993, 5.52356}},
/*29*/ {{0, 1, 1.58496, 1.58496, 2, 2, 2, 2, 2, 2.32193, 2.32193, 2.32193, 2.32193, 2.58496, 2.58496, 2.58496, 2.80735, 2.80735, 3, 3.16993, 3.16993, 3.32193, 3.45943, 3.58496, 3.80735, 4, 4.16993, 4.39232, 4.58496, 4.85798, 5.16993}},
/*30*/ {{0, 1, 1.58496, 1.58496, 2, 2, 2, 2, 2, 2, 2.32193, 2.32193, 2.32193, 2.32193, 2.58496, 2.58496, 2.58496, 2.80735, 2.80735, 3, 3.16993, 3.16993, 3.32193, 3.45943, 3.58496, 3.80735, 4, 4.16993, 4.39232, 4.64386, 4.90689}},
/*31*/ {{0, 1, 1.58496, 1.58496, 1.58496, 2, 2, 2, 2, 2, 2, 2.32193, 2.32193, 2.32193, 2.32193, 2.58496, 2.58496, 2.80735, 2.80735, 2.80735, 3, 3.16993, 3.16993, 3.32193, 3.45943, 3.70044, 3.80735, 4, 4.16993, 4.39232, 4.64386}},
/*32*/ {{0, 1, 1.58496, 1.58496, 1.58496, 1.58496, 2, 2, 2, 2, 2, 2.32193, 2.32193, 2.32193, 2.32193, 2.58496, 2.58496, 2.58496, 2.80735, 2.80735, 3, 3, 3.16993, 3.32193, 3.32193, 3.45943, 3.70044, 3.80735, 4, 4.16993, 4.39232}}}};
struct XY
{
double x, y;
};
// double eval(XY p0, XY p1, double x)
//{
// if (p0.x == p1.x)
// return p0.y;
// double slope = (p0.y - p1.y) / (p0.x - p1.x);
// auto yInter = p0.y - slope * p0.x;
// return x * slope + yInter;
// }
}
u64 SimpleIndex::get_bin_size(u64 numBins, u64 numBalls, u64 statSecParam, bool approx)
{
if (numBins < 2)
return numBalls;
if (approx)
{
auto &sizes = [&]() -> std::vector<std::vector<double>> &
{
if (statSecParam <= 40)
return logbinSizes_40bit;
if (statSecParam <= 50)
return logbinSizes_50bit;
if (statSecParam <= 60)
return logbinSizes_60bit;
return logbinSizes_80bit;
}();
auto numBinsLow = oc::log2floor(numBins);
auto numBinsHgh = oc::log2ceil(numBins);
auto numBallsLow = oc::log2floor(numBalls);
auto numBallsHgh = oc::log2ceil(numBalls);
auto diffBin = std::log2(numBins) - numBinsLow;
auto diffBall = std::log2(numBalls) - numBallsLow;
// interpolate a linear 2d spline between the serounding points (a surface).
// Then evalate the surface at out bin,ball coordinate.
if (numBinsHgh < sizes.size() && numBallsHgh < sizes[numBinsHgh].size())
{
auto a0 = (diffBin)*sizes[numBinsLow][numBallsLow] + (1 - diffBin) * sizes[numBinsLow][numBallsHgh];
auto a1 = (diffBin)*sizes[numBinsHgh][numBallsLow] + (1 - diffBin) * sizes[numBinsHgh][numBallsHgh];
auto b0 = (diffBall)*a0 + (1 - diffBall) * a1;
auto B = std::ceil(std::pow(2, b0));
#if !defined(NDEBUG) && defined(ENABLE_BOOST)
auto B2 = get_bin_size(numBins, numBalls, statSecParam, false);
assert(B2 <= B);
#endif
return B;
}
}
auto B = std::max<u64>(1, numBalls / numBins);
double currentProb = getBinOverflowProb(numBins, numBalls, B);
u64 step = 1;
bool doubling = true;
while (currentProb < statSecParam || step > 1)
{
if (!step)
throw std::runtime_error(LOCATION);
if (statSecParam > currentProb)
{
if (doubling)
step = std::max<u64>(1, step * 2);
else
step = std::max<u64>(1, step / 2);
B += step;
}
else
{
doubling = false;
step = std::max<u64>(1, step / 2);
B -= step;
}
currentProb = getBinOverflowProb(numBins, numBalls, B);
}
// std::cout << "binsize " << numBins << " " << numBalls << " " << statSecParam << " -> " << B << std::endl;
// std::cout << numBins << " " << numBalls << " " << B << std::endl;
return B;
}
void SimpleIndex::init(u64 numBins, u64 numBalls, u64 statSecParam, u64 numHashFunction)
{
mNumHashFunctions = numHashFunction;
mMaxBinSize = get_bin_size(numBins, numBalls * numHashFunction, statSecParam);
mBins.resize(numBins, mMaxBinSize);
mBinSizes.resize(numBins, 0);
mItemToBinMap.resize(numBalls, numHashFunction);
mNumBins = numBins;
}
void SimpleIndex::insertItems(span<block> items, block hashingSeed)
{
oc::CuckooIndex<> cuckoo;
{
//cuckoo.mLocations.resize(items.size(), mNumHashFunctions, oc::AllocType::Uninitialized);
u64 binCount = mNumBins;
// mBins.resize(binCount, mMaxBinSize);
// mStash.resize(mParams.mStashSize);
// mNumBins = binCount;
// mNumBinMask = mParams.binMask();
cuckoo.mMods.resize(mNumHashFunctions);
for (u64 i = 0; i < cuckoo.mMods.size(); ++i)
{
cuckoo.mMods[i] = oc::Mod(binCount - i);
}
}
// cuckoo.computeLocations()
oc::Matrix<u32> locations(32, mNumHashFunctions);
std::array<block, 32> hashs;
oc::AES hasher(hashingSeed);
for (u64 i = 0; i < items.size(); i += hashs.size())
{
auto min = std::min<u64>(items.size() - i, hashs.size());
hasher.hashBlocks(items.data() + i, min, hashs.data());
cuckoo.computeLocations(hashs, locations);
for (u64 j = 0; j < mNumHashFunctions; ++j)
{
for(u64 k = 0; k < min; ++k)
{
auto loc = locations(k,j);
mBins(loc, mBinSizes[loc]++).set(i+k, j);
}
}
}
}
}