2

Say I need N cryptographically-secure pseudorandom integers within the range [0, K). The most obvious way of achieving this would be N calls to arc4random_uniform(3), and this is exactly what I’m doing.

However, the profiler tells me that numerous calls to arc4random_uniform(3) are taking 2/3 of the whole execution time, and I really need to make my code faster. This is why I‘m planning to generate some random bytes in advance (probably with arc4random_buf(3)) and subsequently extract from it bit by bit.

For K = 2, I can simply mask the desired bit out, but when K is not a power of 2, things are getting hairy. Surely I can use a bunch of %= and /=, but then I would have modulo bias. Another problem is when N grows too large, I can no longer interpret the whole buffer as an integer and perform arithmetic operations on it.

In case it’s relevant, K would be less than 20, whereas N can be really large, like millions.

nalzok
  • 14,965
  • 21
  • 72
  • 139
  • Does this answer your question? [How to generate a random integer in the range \[0,n\] from a stream of random bits without wasting bits?](https://stackoverflow.com/questions/6046918/how-to-generate-a-random-integer-in-the-range-0-n-from-a-stream-of-random-bits) – Peter O. Jul 17 '20 at 05:11

1 Answers1

3

You can use the modulus operator and division, you just need to do a bit of extra preprocessing. Generate your array of values as normal. Take P to be the largest power of K less than or equal to 2^32 (where ^ denotes exponentiation), and iterate over your array making sure all random values are strictly less then P. Any which aren't, replace with a new random number which is less than P. This will remove the bias.

Now to handle large N, you'll need to two loops. The first loop iterates over the elements in the array, the second extracts multiple random numbers from each element. If P = k ^ e, then you can extract e random numbers from [0, k) from each element in the array. Each time you extract a random number from an element, do a floored division by k on that element.

Of course, this doesn't necessarily need to be actual loops. You can store two variables (array index, sub-element index) and extract from the array_index element as a function gets called. If sub_element_index == e, then reset it to zero and increase the array_index. Extract a random number from this array element and return it instead.

Dillon Davis
  • 6,679
  • 2
  • 15
  • 37