pwuille

4 ms·

1.
by pwuille 5y ago
Yes, that's called rejection sampling, and it's the only way to produce truly uniform output if the range doesn't evenly divide the input range. However in a setting of say finding buckets in a hashtable which isn't a po
2.
by pwuille 5y ago
The conversion is free, at least on x86-like platforms, because there are no separate 32-bit and 64-bit registers. Instead, there is a fixed shared set of registers, and the instructions signal whether they operate on the 32-bit or 64-bit v
3.
by pwuille 5y ago
No, it's not. The method described by ARM is functionally identical, so it is equally biased as the method described in the blog post here.
4.
by pwuille 5y ago
Exactly, both the modulo and the multiplicative method are equally close to uniform. In fact, under the constraint of starting from a uniform input with 2^n possibilities, both produce an output that is as close to uniform as possible. A ne
5.
by pwuille 5y ago
I recently discovered a generalization of this approach, which allows mapping a single hash to multiple independent numbers, each in their own range, while maintaining various uniformity properties. A write-up is here, in case anyone is int
6.
by pwuille 6y ago
I think the most mind-blowing aspect about it is that (PinSketch) sketches are identical in size to the bandwidth that would be required to just send the difference if you did know it ahead of time. Perhaps this intuition helps: imagine w
7.
by pwuille 6y ago
Yeah, IBLT has a size overhead which mostly matters for small differences/capacities. It's also probabilistic, so the higher your probability for recovery has to be, the larger it gets. Assuming you don't actually know an str
8.
by pwuille 6y ago
It depends on the protocol requirements. If you have 256-bit data elements to reconcile, and want 100% guarantee that reconciliation will succeed with 1 round-trip, then you'll indeed need to use sketches with 256-bit elements. However
9.
by pwuille 6y ago
Hi, other author here. 0. Indeed. Though if your set consists of 100 million elements, you'll indirectly need to have at least 27 bit elements just to be able to identify them. So for practical problems you can probably say that the sk