A fast alternative to the modulo reduction (2016)
lemire.me
lemire.me
Another approach, if you really want to use modulo, is to execute the division as a multiplication by the reciprocal followed by a shift. This makes sense when the divisor is odd and used multiple times. See e.g. [0] about how compilers generate code to divide by a constant.
[0] https://en.wikipedia.org/wiki/Division_algorithm#Division_by...
Attackers knew some site used some DB that used a specific hash and items that hash to the same value end up in a linked list. So, the submitted a ton of user data that all hashed to the same value then DOS’d with requests that ran through the whole linked list every time.
The random seed can by extracted, exposed or calculated, and then siphash doesn't help you at all, it just makes everything 2x slower.
This is what all (non-vulnerable) programming languages do btw.
PS: saw your other post, interesting take.
https://news.ycombinator.com/item?id=12401920
I’ll venture a guess: a lot of practical attacks in the lab becomes completely impractical on a network.
If you’ve been watching, there have been a series of articles over the last five or so years as each language upgrades their hash table implementation to thwart this class of attack.
(1) Map key to an integer (2) Map key to a uniformly distributed integer
In case of (1) the hash map implementation needs to do the mixing step, (2) is much better for benchmarking as in the article.
It reminds me of the sort of tricks I used as a teenager back in the 90s to speed up my MS-DOS graphics code.
Another trick: You can perform rounding by adding fixed-point 1/2 before the bit shift.
That's exactly how I described this trick in code-comments.
The "Faster Threshold-Based Discarding" section of that article is the technique that Lemire actually suggests, to avoid the %, and the benchmarks indicate Lemire's method is equal or faster in all but the "Large Shuffle" case (and the "Optimizing Modulo" section reduces that difference significantly).
Write those four split positions in base 8:
1/5 = 0.1463(1463)
2/5 = 0.3146(3146)
3/5 = 0.4631(4631)
4/5 = 0.6314(6314)
Use the d8 to generate an octal fraction in [0, 1]. Find which of the 5 intervals it falls in, and output that interval's number.
For example, if the d8 comes up 0, 2, 5, or 7, you would output 0, 1, 3, or 4, respectively. If you get anything else, you will need at least one more roll. For example, suppose the first roll was 1. Then you know that the output is going to be 0 or 1. Roll again. On 0, 1, 2, or 3, output 0. On 5, 6, or 7, output a 1. On 4, you need to roll a third time. On the third roll, 1-5 => 0, 7 => 1, and 6 means you'll need a 4th roll. The 4th roll goes 0-2 => 0, 4-7 => 1, and 3 means roll again. The pattern then repeats for potential rolls 5, 6, 7, and 8, and so on.
Another way to work out the same thing, without explicit fractions, is to work out a state diagram, naming each state with a string that lists each reachable output, with some outputs repeated so that they appear in the name in proportion to their probability from that state. That's probably confusion, so here is an example, where we will use a d2 (i.e., a random bit stream) to generate integers in [0, 2]. In other words, we are using a d2 to simulate a d3.
The first state should be able to lead to 0, 1, or 2, an they should be equally probable, so we name the first state 012. There should be two next states from that, one for rolling 0 and one for rolling 1.
The way we get the names for those states is by splitting 012 in two. But we need a name with an even number of characters for that, so lets double all the characters: 001122. Now we can split it in two to get the two next states: 001 and 122.
Same thing to get the next states for 001 (make it even--000011--and then split it: 000 and 011) and 122 (=> 112222 => 112 and 222). So far we have this (draw root down):
000 011 112 222
\ / \ /
001 122
\ /
012
A 111 111 B
\ / \ /
000 011 112 222
\ / \ /
A:001 B:122
\ /
012
This all easily generalizes to using a dN to simulate a dM.
The base-M fraction approach can be done without actually building up the table of partition points, and the digits of the one partition point you need for each simulated dM roll can be worked out on demand as you need them, using just integers.
For example, if you need a/b in base M, set r = a. To get successive digits, iterate this:
r = r * M
d = floor(r/b)
r = r % b
However, I think that approach is conceptually very similar to "FP Multiply" (using floating-point arithmetic) or "Integer Multiplication" (using fixed-point arithmetic) in the GP's linked blog post. Those approaches package the whole "generate digits" idea into a single step, by handling the "split positions" directly as native fractions, rather than having to think of them as sequences in a particular base. These are likely to be significantly more efficient too, since they do not have to do (multiple) division/modulos, which are expensive as the main article points out (let alone computing/storing the fraction representation).
Your approach has the benefit that it is not biased (if the entropy in `r` is tracked appropriately, so that it can be resampled), but Lemire's "Debiased Integer Multiplication" version (as well as the optimised versions) are likely a faster way to remove the bias.
Furthermore, suppose the distribution has to be even. Then, you do not want the modulo N in any shape or form, unless the modulus is a factor of the range of the random number source.
What you do is find the smallest power of P, such that N < P. Then you reduce the input numbers using mod P; which is a fast bitwise AND operation against (P - 1).
Then, you reject values which are >= N; you get another random number R and try again, until R & (P - 1) lands in the [0, N) range.
> Suppose you have a hash table with a capacity N. Again, you need to transform your hash values (typically 32-bit or 64-bit integers) down to an index no larger than N.
I wouldn't have such a thing where N isn't a power of two.
Non-power-of-two moduli in hash tables are only useful in the open addressing technique, where all entries are stored in the table itself, rather than in chains emanating from the table. Open addressing resolves collisions by probing for alternate locations in the hash table. If the modulus is a prime number under open addressing, then if quadratic probing is used:
https://en.wikipedia.org/wiki/Quadratic_probing
it will have the property of visiting all the table locations. That is to say, the quadratic probes modulo a prime N generate a sequence of unique table entries before repeating. This guarantees that a place will be found for any new key even if the table has just one slot left.
> You can also generate random numbers in a range faster, which matters if you have a very fast random number generator.
That seems too biased for many RNG uses.
threshold = -bound % bound
So it's doing (2^n - bound) % bound = 2^n % bound.
Is that accurate? Is there any concern there for never getting the smallest possible values? Or is that acceptable because you can't generate values very close to 1?
There is some concern with the bias due to missing small values (and missing low bits, even for moderate values), but this is often ignored, and is usually good-enough.
From "Writing a Damn Fast Hash Table With Tiny Memory Footprints": http://www.idryman.org/blog/2017/05/03/writing-a-damn-fast-h... , previous discussion https://news.ycombinator.com/item?id=14290055
I wonder if the introduction of calculators into school curriculum has made people less prone to carry around rational values as intermediates. Division is a pain in the butt in mental arithmetic and it remains slow on computers (except when compilers are able to strength-reduce it away). There are a lot of nice optimizations in numerical algorithms that come from keeping denominators seperate (implicitly or explicitly).