6 ms·

An optimal algorithm for bounded random integers

• whiterock 5y ago
  wow
• Straw 5y ago
  This is essentially arithmetic encoding to do base conversion from binary to n-ary. Once you have enough bits, you're almost certainly not on the boundary of a bucket. Funny how the same thing seems to have been reinvented...
  • Someone 5y ago
    I don’t think that’s fair. The article clearly knows about prior art, and ‘only’ claims: “This PR introduces a novel algorithm that: - never divides - avoids rejection sampling entirely - achieves a theoretically optimal bound on the amount of randomness consumed to generate a sample - delivers actual performance improvements for most real cases”
    • Straw 5y ago
      I don't mean it as a negative! Except perhaps I could have understand what they did faster if they described it as arithmetic encoding.
  • stephencanon 5y ago
    That's exactly right (in fact, thinking about AC is what prompted me to implement it).
• gumby 5y ago
  This PR should be submitted, as is, to a peer reviewed journal and published again as is. It would be great if the DOI resolved to the PR itself! I don't mean this as a joke, I mean this as a way to contribute (slightly humorously, or perhaps even not) to upending an outdated, yet valuable, way of disseminating scientific research.
  • petschge 5y ago
    Papers are hardly outdated. But sure, having a reference implementation to go with it is good.
  • nyanpasu64 5y ago
    My concern is that pull requests are mutable, and the thread and code can be edited, deleted by the author or repo owner, or even disappeared entirely if the author gets banned by GitHub (like github.com/volth, whose account got shadowbanned since it changed from a real person to a bot account used by archive.is to scrape GitHub).
  • toxik 5y ago
    The author himself has stated upthread that this is not novel.
  • ithinkso 5y ago
    What scientific research values the most is references and being able to read them. What tech values the least is the ability to access two years old blogposts
• foota 5y ago
  Lemire (cited in the article) is also the author of some work in fast integer division by a constant.
  • H8crilA 5y ago
    You mean the Division by Invariant Multiplication? It feels very related.
    • saagarjha 5y ago
      The insight here is more the application of fast integer division by a constant (to generating random numbers) than work "in" it.
  • IncRnd 5y ago
    Lemire is not only cited in the article. He responded to it on the gh page.
• codetrotter 5y ago
  I thought because of the branch name they used for their PR that it was going to be a joke PR, but the mathematics of it is outside of what I understand well enough to judge if it’s legit. But from the way it reads it sounds honest. So assuming that it is legit, it sounds really intriguing especially because of the claim they make that it “breaks the loop-carried dependency for fast generators, unlocking vectorization and parallelization where it was previously impossible”.
  • theresistor 5y ago
    The author is a vector & numerics expert at Apple.
  • saagarjha 5y ago
    It's legit.
  • burnished 5y ago
    If I understand correctly the reason for that claim is they know in advance how many bits they will need to essentially guarantee a good sample, so instead of needing to perform the operation first to find out where the next operation can start they can just chunk it out and do it in parallel.
• stephencanon 5y ago
  Hi, author here. Note this is not really a "new idea"; in a very reasonable sense it's simply the most obvious thing possible. I do think that it's likely the first mainstream "productized" implementation, however (though I would be interested to hear of other places that it's been tried).
  • nullc 5y ago
    You may be interested in this work going in the opposite direction, holding the bias constant and extracting the most ranges from a constant amount of randomness: https://github.com/sipa/writeups/tree/main/uniform-range-extraction https://github.com/sipa/writeups/tree/main/uniform-range-ext... This work is interesting because generating random bits via strong generators is typically much more expensive than extraction-- so it can be very useful in cases where a number of small random values are needed in a tight loop such as for some kinds of hash table and generating permutations.
• quickthrower2 5y ago
  It’s spreading https://github.com/rust-random/rand/issues/1172 https://github.com/rust-random/rand/issues/1172
• TimonKnigge 5y ago
  I'm a bit confused about this method. So the standard argument against such a procedure is that if you generate N random bits, each of {0,1}^N bitstrings is equiprobable and therefore no mapping of {0,1}^N to {0..U-1} can map an equal number of bitstrings to each output. A priori the method seems to work around this by conditionally sampling more bits, so that your domain is not one of fixed-length bitstrings. But then there is this paragraph: > More intriguing still, this algorithm can be made unconditional by removing the early out, so that every value computed requires word size + 64 bits from the stream, which breaks the loop-carried dependency for fast generators, unlocking vectorization and parallelization where it was previously impossible. This is an especially powerful advantage when paired with bitstream generators that allow skip-ahead such as counter-based generators or PCG. But now we are mapping {0, 1}^N into {0..U-1} right? So this mapping ought not be uniform? In fact I'm not sure why the early-termination method even works, because for a fixed U we know the maximum depth of the generated-bitstring-tree, so we can just pad it with imaginary random bits to arrive at the contradiction that U does not divide 2^N. I imagine I missed something, what is it? EDIT: thinking about it more, if you sample finitely many bits then each possible output has a probability that is a dyadic rational (fractions of the form a/2^k) which does not include all integer reciprocals.
  • stephencanon 5y ago
    That's exactly right. It's not uniform, but the deviation from uniform is so small that there's no measurement you can perform that can observe the difference. If you need an formally uniform distribution for an information-theoretic proof or something similar, you wouldn't use this termination condition.
    • TimonKnigge 5y ago
      I see -- thank you for clarifying. So for a formally uniform distribution, is rejection sampling your only option ?
      • stephencanon 5y ago
        Not at all! You can simply compute additional product bits (you don’t need to go bit-by-bit) until the “can this possibly carry out” test (which is just a comparison) says “no”. The probability that you need more bits falls off exponentially, so this happens very quickly. What you lose by doing this is each value no longer consumes a bounded number of bits from the source, which is how it’s able to be “truly” uniform.
• kwillets 5y ago
  I did the work that Lemire links there. It started with realizing that Lemire's rejection method becomes more likely to need a division/modulo as the range maxes out (the gate on division is fraction < range, so as range -> maxint the division case approaches 100%, if the fraction and range have the same precision). If the range is 32 bit but the fraction is 64, the division case is 2^32 times less likely, so I worked out Lemire's method for 32.64 fixed point. That turned out to be similar to the infinite-precision case described here, as we only need 32 bits of fraction if it's far enough from the edges, ie nothing can carry into the integer part if we extend to 64. Once I worked out when to extend to 64 bits in the rejection method, I realized that the infinite-precision case is similar, using a loop instead of a conditional. It's simpler since there's no rejection, just a decision to continue as long as it's possible to carry.
• nneonneo 5y ago
  Note that this is equivalent to computing `upperbound * randbits(nbits + 64) >> (nbits + 64)` combined with an early-exit optimization, albeit one that becomes less effective as `upperbound` increases: if `upperbound = 2^nbits - 1`, the probability of using the early exit is basically zero. (As the author points out, Lemire's optimization may be used to improve this exit test). The early exit optimization, however, may leak information about the random output, since it tells someone with access to timing information whether one or two outputs was used. With standard rejection sampling, the entire sample is discarded if a bias would be produced, so the output is independent of the number of samples. However, here, certain outputs cannot be produced by the early exit (for sufficiently large upper bounds), meaning that an attacker could narrow down the random number if the algorithm exited early. I think that, to avoid this timing attack vector, the early exit would need to be eliminated - in which case the algorithm would perform no better (and usually worse) than Lemire's approach in terms of expected calls to the random number generator.
  • stephencanon 5y ago
    Right, this is a generator that's used in contexts where a timing side-channel is not a concern, but it's still a great distinction to point out. More broadly, the Swift language--like almost every other language--doesn't have any notion of constant-time operation, so it's not clear what you would do with an RNG free of timing side channels if you had one; use it in a computation that can't make any guarantees about side channels?* You're correct that the number of expected calls collapses to 2 (matching the worst case for Lemire) even in that case, but (for our purposes) it's a "better" 2 (at least with most random sources) since (a) it still never divides (b) it is branch-free, so it never mispredicts and (c) it's always 2 instead of 1 with probability 1/2, 2 with probability 1/4, 3 with probability 1/8 and so on. * I am generally very (probably too) negative on “best effort” constant time operations in high-level languages, but having seen innumerable schemes undone by compiler optimizations, I’m jaded. If you need to eliminate side channels, use hardware designed to do so. [All that said, I added a note to the PR to make this clear.]
    • nneonneo 5y ago
      Cryptographic operations come to mind. I could see someone reaching for this function to get a uniform value below some prime, for example, which might be reasonable if it were backed by a good CSPRNG for the underlying bits - and a good CSPRNG might well be slow enough to make this timing channel easily observable. Some of the good modern crypto libraries make fairly strong guarantees about constant-time or at least data-independent operations. Granted, these may not be 100% side-effect-free thanks to processor bugs, but at least those are fairly time-intensive to attack. In any case, the concern isn’t the variable number of calls, but the fact that the number of calls could leak information about the results. EDIT: Well, two of the places your PR has been linked to are RustCrypto (https://github.com/RustCrypto/utils/issues/453 https://github.com/RustCrypto/utils/issues/453) and OpenSSL (https://github.com/openssl/openssl/issues/16500 https://github.com/openssl/openssl/issues/16500), two places where I definitely would not want to see a significant timing vulnerability. I wish that the folks posting these to crypto libraries would be more aware that this timing issue exists! To concretely demonstrate the problem: suppose that the 64-bit upper bound is `2^64 * 3/4 = 13835058055282163712`. In this case, if the early exit is triggered, the result modulo 3 must be 0 or 2 (with 50% probability for each): numbers congruent to 1 mod 3 cannot come out of the early exit. By contrast, Lemire's method always outputs a uniform distribution of outputs at each iteration. Lemire's method has a smaller timing leak in that the division doesn't always happen - and since divisions are expensive, this could be significant, but it won't outweigh the cost of an unbuffered read of urandom, for example.
• krick 5y ago
  Are there any benchmarks (performance)?