hyperloglog_rs/
precisions.rs

1//! In this document, we define the precisions as a trait and we implement it for structs
2//! ranging from Precision4 to Precision16. This is necessary so that the compiler can
3//! know the size necessary to store the number of zeros, and allows us the save when using
4//! a number of registers equal of inferior to 256 a Byte, compared to what is possible when
5//! using a number of registers equal or inferior to 65536, which would make us waste another byte.
6//!
7
8use core::ops::{Index, IndexMut};
9use core::{fmt::Debug, ops::SubAssign};
10
11use serde::{Deserialize, Serialize};
12
13use crate::{
14    array_default::ArrayDefault,
15    array_default::ArrayIterArgmin,
16    array_default::PrimitiveArray,
17    array_default::{ArrayIter, ArrayIterArgmax},
18    prelude::{precompute_linear_counting, One},
19    primitive::Primitive,
20    zeros::Zero,
21};
22
23pub trait WordType<const BITS: usize>: Precision {
24    /// The type to use for the associated vector of words.
25    /// The type of Words is always an array of u32, as this is the smallest
26    /// type that can be used to store the number of registers.
27    ///
28    /// The length of the array is: ceil(P::NUMBER_OF_REGISTERS, 32 / BITS)
29    ///
30    /// We cannot use the above expression directly, as it would force the library
31    /// user to propagate some very ugly constraints around.
32    ///
33    type Words: Copy
34        + Debug
35        + IndexMut<usize, Output = u32>
36        + Index<usize, Output = u32>
37        + Send
38        + Sync
39        + Eq
40        + PartialEq
41        + ArrayIter<u32>
42        + ArrayDefault<u32>; // = [u32; ceil(P::NUMBER_OF_REGISTERS, 32 / BITS)]
43    /// The register multiplicities is an array with the length of the largest possible
44    /// value that can appear in a register. The value at index i is the number of registers
45    /// that have a value equal to i, meaning the largest value that any register can have
46    /// is the number of registers, i.e. 2^EXPONENT. This is the m parameter in the HyperLogLog.
47    /// The lenth of the multiplicities array varies depending on the exponent and the number of bits,
48    /// as the length of the array is equal to the maximal value that can be stored in a register.
49    /// The value being stored in the register is the number of leading zeros in the hash of the
50    /// value that is being inserted.
51    /// When the register is of 1 bit, the maximal value is 1, and the length of the array is 2.
52    /// When the register is of 2 bits, the maximal value is 3, and the length of the array is 4.
53    /// When the register is of 3 bits, the maximal value is 7, and the length of the array is 8.
54    /// When the register is of 4 bits, the maximal value is 15, and the length of the array is 16.
55    /// When the register is of 5 bits, the maximal value is 31, and the length of the array is 32.
56    /// Things start to get interesting for the cases of register at least 6 bits, as the maximal
57    /// value representable in 6 bits is 63, but here we have to take into account the fact that
58    /// the precision will be the limiting factor. In fact, the higher the precision, the larger
59    /// the number of registers, and therefore more bits of the hash will be used to sample the
60    /// register associated to a given value. For this reason, in those cases, the maximal value
61    /// that we may encounter stored in the register is not 63, but 64 - (PRECISION - 1) + 1.
62    /// So, when the register is of 6 bits, we need to consider the precision as follows:
63    /// When the precision is 4, the maximal value is 61, and the length of the array is 62.
64    /// When the precision is 5, the length of the array is 61.
65    /// When the precision is 6, the length of the array is 60.
66    /// The decrease in length continues linearly until the maximal precision for which we
67    /// have experimental parameters, which is 18, where the length of the array is 48.
68    type RegisterMultiplicities: Index<usize, Output = Self::NumberOfZeros>
69        + IndexMut<usize, Output = Self::NumberOfZeros>
70        + Copy
71        + Debug
72        + Eq
73        + ArrayIterArgmin<Self::NumberOfZeros>
74        + ArrayIterArgmax<Self::NumberOfZeros>
75        + ArrayDefault<Self::NumberOfZeros>
76        + PrimitiveArray<f32, Array = Self::FloatMultiplicities>
77        + ArrayIter<Self::NumberOfZeros>;
78
79    type FloatMultiplicities: Index<usize, Output = f32>;
80}
81
82pub trait Precision: Default + Copy + Eq + Serialize + Debug + Send + Sync {
83    /// The data type to use for the number of zeros registers counter.
84    /// This should be the smallest possinle data type that allows us to count
85    /// all the registers without overflowing. We can tollerate a one-off error
86    /// when counting the number of zeros, as it will be corrected when computing
87    /// the cardinality as it is known before hand whether this can happen at all.
88    type NumberOfZeros: Copy
89        + Debug
90        + Eq
91        + PartialEq
92        + Primitive<usize>
93        + Primitive<f32>
94        + Send
95        + Copy
96        + Sync
97        + Zero
98        + One
99        + Ord
100        + PartialOrd
101        + SubAssign;
102    /// The exponent of the number of registers, meaning the number of registers
103    /// that will be used is 2^EXPONENT. This is the p parameter in the HyperLogLog.
104    const EXPONENT: usize;
105    /// The number of registers that will be used.
106    const NUMBER_OF_REGISTERS: usize = 1 << Self::EXPONENT;
107    /// Type for small corrections:
108    type SmallCorrections: Index<usize, Output = f32> + Copy;
109    type Registers: Index<usize, Output = u32> + Copy + ArrayDefault<u32> + ArrayIter<u32>;
110    /// The precomputed small corrections used in the HyperLogLog algorithm for better performance.
111    const SMALL_CORRECTIONS: Self::SmallCorrections;
112}
113
114#[derive(Default, Debug, Clone, Copy, PartialEq, Eq, Hash, Serialize, Deserialize)]
115pub struct Precision4;
116
117impl Precision for Precision4 {
118    type NumberOfZeros = u8;
119    const EXPONENT: usize = 4;
120    type SmallCorrections = [f32; 16];
121    type Registers = [u32; 16];
122    const SMALL_CORRECTIONS: Self::SmallCorrections =
123        precompute_linear_counting::<{ Self::NUMBER_OF_REGISTERS }>();
124}
125
126impl WordType<1> for Precision4 {
127    type Words = [u32; 1];
128    type RegisterMultiplicities = [Self::NumberOfZeros; 2];
129    type FloatMultiplicities = [f32; 2];
130}
131
132impl WordType<2> for Precision4 {
133    type Words = [u32; 1];
134    type RegisterMultiplicities = [Self::NumberOfZeros; 4];
135    type FloatMultiplicities = [f32; 4];
136}
137
138impl WordType<3> for Precision4 {
139    type Words = [u32; 2];
140    type RegisterMultiplicities = [Self::NumberOfZeros; 8];
141    type FloatMultiplicities = [f32; 8];
142}
143
144impl WordType<4> for Precision4 {
145    type Words = [u32; 2];
146    type RegisterMultiplicities = [Self::NumberOfZeros; 16];
147    type FloatMultiplicities = [f32; 16];
148}
149
150impl WordType<5> for Precision4 {
151    type Words = [u32; 3];
152    type RegisterMultiplicities = [Self::NumberOfZeros; 32];
153    type FloatMultiplicities = [f32; 32];
154}
155
156impl WordType<6> for Precision4 {
157    type Words = [u32; 4];
158    type RegisterMultiplicities = [Self::NumberOfZeros; 62];
159    type FloatMultiplicities = [f32; 62];
160}
161
162#[derive(Default, Debug, Clone, Copy, PartialEq, Eq, Hash, Serialize, Deserialize)]
163pub struct Precision5;
164
165impl Precision for Precision5 {
166    type NumberOfZeros = u8;
167    const EXPONENT: usize = 5;
168    type SmallCorrections = [f32; 32];
169    type Registers = [u32; 32];
170    const SMALL_CORRECTIONS: Self::SmallCorrections =
171        precompute_linear_counting::<{ Self::NUMBER_OF_REGISTERS }>();
172}
173
174impl WordType<1> for Precision5 {
175    type Words = [u32; 1];
176    type RegisterMultiplicities = [Self::NumberOfZeros; 2];
177    type FloatMultiplicities = [f32; 2];
178}
179
180impl WordType<2> for Precision5 {
181    type Words = [u32; 2];
182    type RegisterMultiplicities = [Self::NumberOfZeros; 4];
183    type FloatMultiplicities = [f32; 4];
184}
185
186impl WordType<3> for Precision5 {
187    type Words = [u32; 4];
188    type RegisterMultiplicities = [Self::NumberOfZeros; 8];
189    type FloatMultiplicities = [f32; 8];
190}
191
192impl WordType<4> for Precision5 {
193    type Words = [u32; 4];
194    type RegisterMultiplicities = [Self::NumberOfZeros; 16];
195    type FloatMultiplicities = [f32; 16];
196}
197
198impl WordType<5> for Precision5 {
199    type Words = [u32; 6];
200    type RegisterMultiplicities = [Self::NumberOfZeros; 32];
201    type FloatMultiplicities = [f32; 32];
202}
203
204impl WordType<6> for Precision5 {
205    type Words = [u32; 7];
206    type RegisterMultiplicities = [Self::NumberOfZeros; 61];
207    type FloatMultiplicities = [f32; 61];
208}
209
210#[derive(Default, Debug, Clone, Copy, PartialEq, Eq, Hash, Serialize, Deserialize)]
211pub struct Precision6;
212
213impl Precision for Precision6 {
214    type NumberOfZeros = u8;
215    const EXPONENT: usize = 6;
216    type SmallCorrections = [f32; 64];
217    type Registers = [u32; 64];
218    const SMALL_CORRECTIONS: Self::SmallCorrections =
219        precompute_linear_counting::<{ Self::NUMBER_OF_REGISTERS }>();
220}
221
222impl WordType<1> for Precision6 {
223    type Words = [u32; 2];
224    type RegisterMultiplicities = [Self::NumberOfZeros; 2];
225    type FloatMultiplicities = [f32; 2];
226}
227
228impl WordType<2> for Precision6 {
229    type Words = [u32; 4];
230    type RegisterMultiplicities = [Self::NumberOfZeros; 4];
231    type FloatMultiplicities = [f32; 4];
232}
233
234impl WordType<3> for Precision6 {
235    type Words = [u32; 7];
236    type RegisterMultiplicities = [Self::NumberOfZeros; 8];
237    type FloatMultiplicities = [f32; 8];
238}
239
240impl WordType<4> for Precision6 {
241    type Words = [u32; 8];
242    type RegisterMultiplicities = [Self::NumberOfZeros; 16];
243    type FloatMultiplicities = [f32; 16];
244}
245
246impl WordType<5> for Precision6 {
247    type Words = [u32; 11];
248    type RegisterMultiplicities = [Self::NumberOfZeros; 32];
249    type FloatMultiplicities = [f32; 32];
250}
251
252impl WordType<6> for Precision6 {
253    type Words = [u32; 13];
254    type RegisterMultiplicities = [Self::NumberOfZeros; 60];
255    type FloatMultiplicities = [f32; 60];
256}
257
258impl WordType<7> for Precision6 {
259    type Words = [u32; 16];
260    type RegisterMultiplicities = [Self::NumberOfZeros; 128];
261    type FloatMultiplicities = [f32; 128];
262}
263
264impl WordType<8> for Precision6 {
265    type Words = [u32; 16];
266    type RegisterMultiplicities = [Self::NumberOfZeros; 256];
267    type FloatMultiplicities = [f32; 256];
268}
269
270#[derive(Default, Debug, Clone, Copy, PartialEq, Eq, Hash, Serialize, Deserialize)]
271pub struct Precision7;
272
273impl Precision for Precision7 {
274    type NumberOfZeros = u8;
275    const EXPONENT: usize = 7;
276    type SmallCorrections = [f32; 128];
277    type Registers = [u32; 128];
278    const SMALL_CORRECTIONS: Self::SmallCorrections =
279        precompute_linear_counting::<{ Self::NUMBER_OF_REGISTERS }>();
280}
281
282impl WordType<1> for Precision7 {
283    type Words = [u32; 4];
284    type RegisterMultiplicities = [Self::NumberOfZeros; 2];
285    type FloatMultiplicities = [f32; 2];
286}
287
288impl WordType<2> for Precision7 {
289    type Words = [u32; 8];
290    type RegisterMultiplicities = [Self::NumberOfZeros; 4];
291    type FloatMultiplicities = [f32; 4];
292}
293
294impl WordType<3> for Precision7 {
295    type Words = [u32; 13];
296    type RegisterMultiplicities = [Self::NumberOfZeros; 8];
297    type FloatMultiplicities = [f32; 8];
298}
299
300impl WordType<4> for Precision7 {
301    type Words = [u32; 16];
302    type RegisterMultiplicities = [Self::NumberOfZeros; 16];
303    type FloatMultiplicities = [f32; 16];
304}
305
306impl WordType<5> for Precision7 {
307    type Words = [u32; 22];
308    type RegisterMultiplicities = [Self::NumberOfZeros; 32];
309    type FloatMultiplicities = [f32; 32];
310}
311
312impl WordType<6> for Precision7 {
313    type Words = [u32; 26];
314    type RegisterMultiplicities = [Self::NumberOfZeros; 59];
315    type FloatMultiplicities = [f32; 59];
316}
317
318#[derive(Default, Debug, Clone, Copy, PartialEq, Eq, Hash, Serialize, Deserialize)]
319pub struct Precision8;
320
321impl Precision for Precision8 {
322    type NumberOfZeros = u16;
323    const EXPONENT: usize = 8;
324    type SmallCorrections = [f32; 256];
325    type Registers = [u32; 256];
326    const SMALL_CORRECTIONS: Self::SmallCorrections =
327        precompute_linear_counting::<{ Self::NUMBER_OF_REGISTERS }>();
328}
329impl WordType<1> for Precision8 {
330    type Words = [u32; 8];
331    type RegisterMultiplicities = [Self::NumberOfZeros; 2];
332    type FloatMultiplicities = [f32; 2];
333}
334
335impl WordType<2> for Precision8 {
336    type Words = [u32; 16];
337    type RegisterMultiplicities = [Self::NumberOfZeros; 4];
338    type FloatMultiplicities = [f32; 4];
339}
340
341impl WordType<3> for Precision8 {
342    type Words = [u32; 26];
343    type RegisterMultiplicities = [Self::NumberOfZeros; 8];
344    type FloatMultiplicities = [f32; 8];
345}
346
347impl WordType<4> for Precision8 {
348    type Words = [u32; 32];
349    type RegisterMultiplicities = [Self::NumberOfZeros; 16];
350    type FloatMultiplicities = [f32; 16];
351}
352
353impl WordType<5> for Precision8 {
354    type Words = [u32; 43];
355    type RegisterMultiplicities = [Self::NumberOfZeros; 32];
356    type FloatMultiplicities = [f32; 32];
357}
358
359impl WordType<6> for Precision8 {
360    type Words = [u32; 52];
361    type RegisterMultiplicities = [Self::NumberOfZeros; 58];
362    type FloatMultiplicities = [f32; 58];
363}
364
365#[derive(Default, Debug, Clone, Copy, PartialEq, Eq, Hash, Serialize, Deserialize)]
366pub struct Precision9;
367
368impl Precision for Precision9 {
369    type NumberOfZeros = u16;
370    const EXPONENT: usize = 9;
371    type SmallCorrections = [f32; 512];
372    type Registers = [u32; 512];
373    const SMALL_CORRECTIONS: Self::SmallCorrections =
374        precompute_linear_counting::<{ Self::NUMBER_OF_REGISTERS }>();
375}
376impl WordType<1> for Precision9 {
377    type Words = [u32; 16];
378    type RegisterMultiplicities = [Self::NumberOfZeros; 2];
379    type FloatMultiplicities = [f32; 2];
380}
381
382impl WordType<2> for Precision9 {
383    type Words = [u32; 32];
384    type RegisterMultiplicities = [Self::NumberOfZeros; 4];
385    type FloatMultiplicities = [f32; 4];
386}
387
388impl WordType<3> for Precision9 {
389    type Words = [u32; 52];
390    type RegisterMultiplicities = [Self::NumberOfZeros; 8];
391    type FloatMultiplicities = [f32; 8];
392}
393
394impl WordType<4> for Precision9 {
395    type Words = [u32; 64];
396    type RegisterMultiplicities = [Self::NumberOfZeros; 16];
397    type FloatMultiplicities = [f32; 16];
398}
399
400impl WordType<5> for Precision9 {
401    type Words = [u32; 86];
402    type RegisterMultiplicities = [Self::NumberOfZeros; 32];
403    type FloatMultiplicities = [f32; 32];
404}
405
406impl WordType<6> for Precision9 {
407    type Words = [u32; 103];
408    type RegisterMultiplicities = [Self::NumberOfZeros; 57];
409    type FloatMultiplicities = [f32; 57];
410}
411
412#[derive(Default, Debug, Clone, Copy, PartialEq, Eq, Hash, Serialize, Deserialize)]
413pub struct Precision10;
414
415impl Precision for Precision10 {
416    type NumberOfZeros = u16;
417    const EXPONENT: usize = 10;
418    type SmallCorrections = [f32; 1024];
419    type Registers = [u32; 1024];
420    const SMALL_CORRECTIONS: Self::SmallCorrections =
421        precompute_linear_counting::<{ Self::NUMBER_OF_REGISTERS }>();
422}
423impl WordType<1> for Precision10 {
424    type Words = [u32; 32];
425    type RegisterMultiplicities = [Self::NumberOfZeros; 2];
426    type FloatMultiplicities = [f32; 2];
427}
428
429impl WordType<2> for Precision10 {
430    type Words = [u32; 64];
431    type RegisterMultiplicities = [Self::NumberOfZeros; 4];
432    type FloatMultiplicities = [f32; 4];
433}
434
435impl WordType<3> for Precision10 {
436    type Words = [u32; 103];
437    type RegisterMultiplicities = [Self::NumberOfZeros; 8];
438    type FloatMultiplicities = [f32; 8];
439}
440
441impl WordType<4> for Precision10 {
442    type Words = [u32; 128];
443    type RegisterMultiplicities = [Self::NumberOfZeros; 16];
444    type FloatMultiplicities = [f32; 16];
445}
446
447impl WordType<5> for Precision10 {
448    type Words = [u32; 171];
449    type RegisterMultiplicities = [Self::NumberOfZeros; 32];
450    type FloatMultiplicities = [f32; 32];
451}
452
453impl WordType<6> for Precision10 {
454    type Words = [u32; 205];
455    type RegisterMultiplicities = [Self::NumberOfZeros; 56];
456    type FloatMultiplicities = [f32; 56];
457}
458
459#[derive(Default, Debug, Clone, Copy, PartialEq, Eq, Hash, Serialize, Deserialize)]
460pub struct Precision11;
461
462impl Precision for Precision11 {
463    type NumberOfZeros = u16;
464    const EXPONENT: usize = 11;
465    type SmallCorrections = [f32; 2048];
466    type Registers = [u32; 2048];
467    const SMALL_CORRECTIONS: Self::SmallCorrections =
468        precompute_linear_counting::<{ Self::NUMBER_OF_REGISTERS }>();
469}
470impl WordType<1> for Precision11 {
471    type Words = [u32; 64];
472    type RegisterMultiplicities = [Self::NumberOfZeros; 2];
473    type FloatMultiplicities = [f32; 2];
474}
475
476impl WordType<2> for Precision11 {
477    type Words = [u32; 128];
478    type RegisterMultiplicities = [Self::NumberOfZeros; 4];
479    type FloatMultiplicities = [f32; 4];
480}
481
482impl WordType<3> for Precision11 {
483    type Words = [u32; 205];
484    type RegisterMultiplicities = [Self::NumberOfZeros; 8];
485    type FloatMultiplicities = [f32; 8];
486}
487
488impl WordType<4> for Precision11 {
489    type Words = [u32; 256];
490    type RegisterMultiplicities = [Self::NumberOfZeros; 16];
491    type FloatMultiplicities = [f32; 16];
492}
493
494impl WordType<5> for Precision11 {
495    type Words = [u32; 342];
496    type RegisterMultiplicities = [Self::NumberOfZeros; 32];
497    type FloatMultiplicities = [f32; 32];
498}
499
500impl WordType<6> for Precision11 {
501    type Words = [u32; 410];
502    type RegisterMultiplicities = [Self::NumberOfZeros; 55];
503    type FloatMultiplicities = [f32; 55];
504}
505
506#[derive(Default, Debug, Clone, Copy, PartialEq, Eq, Hash, Serialize, Deserialize)]
507pub struct Precision12;
508
509impl Precision for Precision12 {
510    type NumberOfZeros = u16;
511    const EXPONENT: usize = 12;
512    type SmallCorrections = [f32; 4096];
513    type Registers = [u32; 4096];
514    const SMALL_CORRECTIONS: Self::SmallCorrections =
515        precompute_linear_counting::<{ Self::NUMBER_OF_REGISTERS }>();
516}
517impl WordType<1> for Precision12 {
518    type Words = [u32; 128];
519    type RegisterMultiplicities = [Self::NumberOfZeros; 2];
520    type FloatMultiplicities = [f32; 2];
521}
522
523impl WordType<2> for Precision12 {
524    type Words = [u32; 256];
525    type RegisterMultiplicities = [Self::NumberOfZeros; 4];
526    type FloatMultiplicities = [f32; 4];
527}
528
529impl WordType<3> for Precision12 {
530    type Words = [u32; 410];
531    type RegisterMultiplicities = [Self::NumberOfZeros; 8];
532    type FloatMultiplicities = [f32; 8];
533}
534
535impl WordType<4> for Precision12 {
536    type Words = [u32; 512];
537    type RegisterMultiplicities = [Self::NumberOfZeros; 16];
538    type FloatMultiplicities = [f32; 16];
539}
540
541impl WordType<5> for Precision12 {
542    type Words = [u32; 683];
543    type RegisterMultiplicities = [Self::NumberOfZeros; 32];
544    type FloatMultiplicities = [f32; 32];
545}
546
547impl WordType<6> for Precision12 {
548    type Words = [u32; 820];
549    type RegisterMultiplicities = [Self::NumberOfZeros; 54];
550    type FloatMultiplicities = [f32; 54];
551}
552
553#[derive(Default, Debug, Clone, Copy, PartialEq, Eq, Hash, Serialize, Deserialize)]
554pub struct Precision13;
555
556impl Precision for Precision13 {
557    type NumberOfZeros = u16;
558    const EXPONENT: usize = 13;
559    type SmallCorrections = [f32; 8192];
560    type Registers = [u32; 8192];
561    const SMALL_CORRECTIONS: Self::SmallCorrections =
562        precompute_linear_counting::<{ Self::NUMBER_OF_REGISTERS }>();
563}
564impl WordType<1> for Precision13 {
565    type Words = [u32; 256];
566    type RegisterMultiplicities = [Self::NumberOfZeros; 2];
567    type FloatMultiplicities = [f32; 2];
568}
569
570impl WordType<2> for Precision13 {
571    type Words = [u32; 512];
572    type RegisterMultiplicities = [Self::NumberOfZeros; 4];
573    type FloatMultiplicities = [f32; 4];
574}
575
576impl WordType<3> for Precision13 {
577    type Words = [u32; 820];
578    type RegisterMultiplicities = [Self::NumberOfZeros; 8];
579    type FloatMultiplicities = [f32; 8];
580}
581
582impl WordType<4> for Precision13 {
583    type Words = [u32; 1024];
584    type RegisterMultiplicities = [Self::NumberOfZeros; 16];
585    type FloatMultiplicities = [f32; 16];
586}
587
588impl WordType<5> for Precision13 {
589    type Words = [u32; 1366];
590    type RegisterMultiplicities = [Self::NumberOfZeros; 32];
591    type FloatMultiplicities = [f32; 32];
592}
593
594impl WordType<6> for Precision13 {
595    type Words = [u32; 1639];
596    type RegisterMultiplicities = [Self::NumberOfZeros; 53];
597    type FloatMultiplicities = [f32; 53];
598}
599
600#[derive(Default, Debug, Clone, Copy, PartialEq, Eq, Hash, Serialize, Deserialize)]
601pub struct Precision14;
602
603impl Precision for Precision14 {
604    type NumberOfZeros = u16;
605    const EXPONENT: usize = 14;
606    type SmallCorrections = [f32; 16384];
607    type Registers = [u32; 16384];
608    const SMALL_CORRECTIONS: Self::SmallCorrections =
609        precompute_linear_counting::<{ Self::NUMBER_OF_REGISTERS }>();
610}
611impl WordType<1> for Precision14 {
612    type Words = [u32; 512];
613    type RegisterMultiplicities = [Self::NumberOfZeros; 2];
614    type FloatMultiplicities = [f32; 2];
615}
616
617impl WordType<2> for Precision14 {
618    type Words = [u32; 1024];
619    type RegisterMultiplicities = [Self::NumberOfZeros; 4];
620    type FloatMultiplicities = [f32; 4];
621}
622
623impl WordType<3> for Precision14 {
624    type Words = [u32; 1639];
625    type RegisterMultiplicities = [Self::NumberOfZeros; 8];
626    type FloatMultiplicities = [f32; 8];
627}
628
629impl WordType<4> for Precision14 {
630    type Words = [u32; 2048];
631    type RegisterMultiplicities = [Self::NumberOfZeros; 16];
632    type FloatMultiplicities = [f32; 16];
633}
634
635impl WordType<5> for Precision14 {
636    type Words = [u32; 2731];
637    type RegisterMultiplicities = [Self::NumberOfZeros; 32];
638    type FloatMultiplicities = [f32; 32];
639}
640
641impl WordType<6> for Precision14 {
642    type Words = [u32; 3277];
643    type RegisterMultiplicities = [Self::NumberOfZeros; 52];
644    type FloatMultiplicities = [f32; 52];
645}
646
647#[derive(Default, Debug, Clone, Copy, PartialEq, Eq, Hash, Serialize, Deserialize)]
648pub struct Precision15;
649
650impl Precision for Precision15 {
651    type NumberOfZeros = u16;
652    const EXPONENT: usize = 15;
653    type SmallCorrections = [f32; 32768];
654    type Registers = [u32; 32768];
655    const SMALL_CORRECTIONS: Self::SmallCorrections =
656        precompute_linear_counting::<{ Self::NUMBER_OF_REGISTERS }>();
657}
658impl WordType<1> for Precision15 {
659    type Words = [u32; 1024];
660    type RegisterMultiplicities = [Self::NumberOfZeros; 2];
661    type FloatMultiplicities = [f32; 2];
662}
663
664impl WordType<2> for Precision15 {
665    type Words = [u32; 2048];
666    type RegisterMultiplicities = [Self::NumberOfZeros; 4];
667    type FloatMultiplicities = [f32; 4];
668}
669
670impl WordType<3> for Precision15 {
671    type Words = [u32; 3277];
672    type RegisterMultiplicities = [Self::NumberOfZeros; 8];
673    type FloatMultiplicities = [f32; 8];
674}
675
676impl WordType<4> for Precision15 {
677    type Words = [u32; 4096];
678    type RegisterMultiplicities = [Self::NumberOfZeros; 16];
679    type FloatMultiplicities = [f32; 16];
680}
681
682impl WordType<5> for Precision15 {
683    type Words = [u32; 5462];
684    type RegisterMultiplicities = [Self::NumberOfZeros; 32];
685    type FloatMultiplicities = [f32; 32];
686}
687
688impl WordType<6> for Precision15 {
689    type Words = [u32; 6554];
690    type RegisterMultiplicities = [Self::NumberOfZeros; 51];
691    type FloatMultiplicities = [f32; 51];
692}
693
694#[derive(Default, Debug, Clone, Copy, PartialEq, Eq, Hash, Serialize, Deserialize)]
695pub struct Precision16;
696
697impl Precision for Precision16 {
698    // For Precision 16, we are still able to use a u16, but we
699    // will loose the ability to count one of the registers.
700    type NumberOfZeros = u32;
701    const EXPONENT: usize = 16;
702    type SmallCorrections = [f32; 65536];
703    type Registers = [u32; 65536];
704    const SMALL_CORRECTIONS: Self::SmallCorrections =
705        precompute_linear_counting::<{ Self::NUMBER_OF_REGISTERS }>();
706}
707impl WordType<1> for Precision16 {
708    type Words = [u32; 2048];
709    type RegisterMultiplicities = [Self::NumberOfZeros; 2];
710    type FloatMultiplicities = [f32; 2];
711}
712
713impl WordType<2> for Precision16 {
714    type Words = [u32; 4096];
715    type RegisterMultiplicities = [Self::NumberOfZeros; 4];
716    type FloatMultiplicities = [f32; 4];
717}
718
719impl WordType<3> for Precision16 {
720    type Words = [u32; 6554];
721    type RegisterMultiplicities = [Self::NumberOfZeros; 8];
722    type FloatMultiplicities = [f32; 8];
723}
724
725impl WordType<4> for Precision16 {
726    type Words = [u32; 8192];
727    type RegisterMultiplicities = [Self::NumberOfZeros; 16];
728    type FloatMultiplicities = [f32; 16];
729}
730
731impl WordType<5> for Precision16 {
732    type Words = [u32; 10923];
733    type RegisterMultiplicities = [Self::NumberOfZeros; 32];
734    type FloatMultiplicities = [f32; 32];
735}
736
737impl WordType<6> for Precision16 {
738    type Words = [u32; 13108];
739    type RegisterMultiplicities = [Self::NumberOfZeros; 50];
740    type FloatMultiplicities = [f32; 50];
741}
742
743#[derive(Default, Debug, Clone, Copy, PartialEq, Eq, Hash, Serialize, Deserialize)]
744pub struct Precision17;
745
746impl Precision for Precision17 {
747    type NumberOfZeros = u32;
748    const EXPONENT: usize = 17;
749    type SmallCorrections = [f32; 131072];
750    type Registers = [u32; 131072];
751    const SMALL_CORRECTIONS: Self::SmallCorrections =
752        precompute_linear_counting::<{ Self::NUMBER_OF_REGISTERS }>();
753}
754impl WordType<1> for Precision17 {
755    type Words = [u32; 4096];
756    type RegisterMultiplicities = [Self::NumberOfZeros; 2];
757    type FloatMultiplicities = [f32; 2];
758}
759
760impl WordType<2> for Precision17 {
761    type Words = [u32; 8192];
762    type RegisterMultiplicities = [Self::NumberOfZeros; 4];
763    type FloatMultiplicities = [f32; 4];
764}
765
766impl WordType<3> for Precision17 {
767    type Words = [u32; 13108];
768    type RegisterMultiplicities = [Self::NumberOfZeros; 8];
769    type FloatMultiplicities = [f32; 8];
770}
771
772impl WordType<4> for Precision17 {
773    type Words = [u32; 16384];
774    type RegisterMultiplicities = [Self::NumberOfZeros; 16];
775    type FloatMultiplicities = [f32; 16];
776}
777
778impl WordType<5> for Precision17 {
779    type Words = [u32; 21846];
780    type RegisterMultiplicities = [Self::NumberOfZeros; 32];
781    type FloatMultiplicities = [f32; 32];
782}
783
784impl WordType<6> for Precision17 {
785    type Words = [u32; 26215];
786    type RegisterMultiplicities = [Self::NumberOfZeros; 49];
787    type FloatMultiplicities = [f32; 49];
788}
789
790#[derive(Default, Debug, Clone, Copy, PartialEq, Eq, Hash, Serialize, Deserialize)]
791pub struct Precision18;
792
793impl Precision for Precision18 {
794    type NumberOfZeros = u32;
795    const EXPONENT: usize = 18;
796    type SmallCorrections = [f32; 262144];
797    type Registers = [u32; 262144];
798    const SMALL_CORRECTIONS: Self::SmallCorrections =
799        precompute_linear_counting::<{ Self::NUMBER_OF_REGISTERS }>();
800}
801impl WordType<1> for Precision18 {
802    type Words = [u32; 8192];
803    type RegisterMultiplicities = [Self::NumberOfZeros; 2];
804    type FloatMultiplicities = [f32; 2];
805}
806
807impl WordType<2> for Precision18 {
808    type Words = [u32; 16384];
809    type RegisterMultiplicities = [Self::NumberOfZeros; 4];
810    type FloatMultiplicities = [f32; 4];
811}
812
813impl WordType<3> for Precision18 {
814    type Words = [u32; 26215];
815    type RegisterMultiplicities = [Self::NumberOfZeros; 8];
816    type FloatMultiplicities = [f32; 8];
817}
818
819impl WordType<4> for Precision18 {
820    type Words = [u32; 32768];
821    type RegisterMultiplicities = [Self::NumberOfZeros; 16];
822    type FloatMultiplicities = [f32; 16];
823}
824
825impl WordType<5> for Precision18 {
826    type Words = [u32; 43691];
827    type RegisterMultiplicities = [Self::NumberOfZeros; 32];
828    type FloatMultiplicities = [f32; 32];
829}
830
831impl WordType<6> for Precision18 {
832    type Words = [u32; 52429];
833    type RegisterMultiplicities = [Self::NumberOfZeros; 48];
834    type FloatMultiplicities = [f32; 48];
835}
hyperloglog_rs/precisions.rs

hyperloglog_rs/
precisions.rs
