# Is it possible to construct a PRNG where the output numbers have a certain distribution of hamming weights?

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.

• 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. – Thomas May 20 '20 at 17:17

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).

• 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! – Ollie May 20 '20 at 18:56
• @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 – poncho May 20 '20 at 19:04
• 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? – Ollie Jun 28 at 20:50
• @Ollie: I don't know of a reference to this approach in the published literature – poncho Jun 28 at 21:01
• Worth a shot, thanks anyways! – Ollie Jun 28 at 22:21