5
$\begingroup$

I am in need of a non-uniform random number generator where each n-bit output has a hamming weight with a certain binomial distribution.

For example, I would like a non-uniform PRNG which generates 32-bit outputs with a hamming weight whose binomial distribution is n=32, p=0.1. For instance, 0xFF should be output with significantly less probability than 0x200, which in turn should have the same probability as 0x1.

Perhaps I can modify the output of a PRNG like xorshift or a LFSR to accomodate for this? I thought about rejection sampling the output, but the distribution of hamming weights for a uniform PRNG does not necessarily envelope a given binominal distribution with a variable parameter p, especially when p << 0.5.

I am not concerned about the cryptographic quality of the output. However, I am working on a 8 bit microcontroller with 2 KB SRAM, so memory and speed are both my primary concern. In the most naive case, I would just generate an array of random numbers and convert each element to 0 and 1 given a threshold probability, and finally convert this resulting array of 0's and 1's to an integer. But I would really, really like to avoid this memory overhead of an n-element array.

$\endgroup$
1
  • $\begingroup$ You don't need to store an N-element array, you can update your integer bit by bit on the fly. Since order doesn't matter you can just do this: output = (output << 1) | (1 or 0), 32 times or as many times as needed, shifting the bits in as you go. $\endgroup$ – Thomas May 20 '20 at 17:17
10
$\begingroup$

The obvious way to do this is to generate N words, and use logical operations to combine them in a single word such that each bit of the output word is a 1 with probability approximately 0.1 (and the individual bits are uncorrelated).

In the simplest case, you could generate 3 words, and just AND them together into a single one. In C, this would be:

     r1 = rand();
     r2 = rand();
     r3 = rand();
     return r1 & r2 & r3;

This gives each bit set with probability 0.125, which is close to 0.1

If that's not quite close enough, you can get a closer approximation by using more bits; for example, r1 & r2 & r3 & ~(r4 & r5) results with bits set with probability $3/32 = 0.09375$

With this technique, you use $n$ random words to generate bits set with probability $k 2^{-n}$ for some integer $k$; this can be made arbitrarily close to 0.1.

This obviously uses minimal memory; the computation time isn't too bad (assuming your rand implementation is cheap), unless you insist on a quite good approximation to your target probability.

And, while I said 'words', your implementation would use whatever size it finds most convenient; for an 8 bit CPU, each word might be 8 bits (and you just do it 4 times to generate the required 32 bits).

$\endgroup$
5
  • $\begingroup$ An approximate probability for each Bernoulli trial is perfectly fine for my application. Interesting technique that can scale in accuracy with the number of words - Thanks! $\endgroup$ – Ollie May 20 '20 at 18:56
  • $\begingroup$ @Ollie: you just need to make sure that adjacent calls to the underlying rng don't have strong bit correlations; an LFSR-based rng might, a linear congruential (state = a*state + b mod m for m odd) one would be less likely to cause problems $\endgroup$ – poncho May 20 '20 at 19:04
  • $\begingroup$ Sorry for raising this thread from the dead. Quick question: Is there a name in the academic literature for this technique of using combinations of bitwise-and and bitwise-or to approximate bit probabilities? I can see that for probability $k \cdot 2^{-n}$ that the binary representation of any general k forms a radix tree (bitwise trie). And that this radix tree can be used to find the correct sequence of and/or instructions for an arbitrarily large n. This allows unlimited precision in approximating the probability, given enough RAM. I'm wondering if this idea is well known? $\endgroup$ – Ollie Jun 28 at 20:50
  • $\begingroup$ @Ollie: I don't know of a reference to this approach in the published literature $\endgroup$ – poncho Jun 28 at 21:01
  • $\begingroup$ Worth a shot, thanks anyways! $\endgroup$ – Ollie Jun 28 at 22:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.