Mfcttrf

Would there be an efficient way to implement a function with the following signature:

unsigned long long int random_word(size_t n, size_t m)

that would generate a random machine word (64 bits here) such that exactly m bits over the n least significant ones at set to 1. For example: random_word(10, 3) would generate a 64-bit random number such that 3 bits over the 10 LSBs are set to 1. For a given n and m every possible output should have equal probability (uniform distribution of possible permutations).

If assembly bit twiddling hacks to do that are known, great, if not, I am looking for references and research directions.

I'd guess that you can simply split this into two problems:

1. create 64 - n random bits, call this R


2. shuffle n bits where m bits (at any location) are set to 1, call this P

Finally you can simply perform R | P (presuming big endian notation).

Shuffling lists of elements is an operation present in almost any language. If there is any inefficiency it would be in the shuffling algorithm (although Fisher-Yates is optimal, so you'd expect some form of that algorithm, possibly the inefficiency is getting values in a range...).

The problem for choosing $k$ bits from $64$ ultimately comes down to computing a uniformly random integer $r$ with $0 leq r < frac64!k!(64-k)!$ then decoding it to determine which bits. The $k!$ in the denominator is annoying, but we can ignore it, because we can just allow our algorithm to have $k!$ random numbers that map to the same output (setting bit 0 then bit 4 is the same as setting bit 4 then bit 0). Now we just have multiplying a decreasing sequence starting from $64$: with $k=4$ this equals $64 * 63 * 62 * 61$.

So for efficiency, you select a random number in $0 le r_0 < 64$, then another $0 le r_1 < 63$ ... through $0 le r_k-1 < 64-(k-1)$ each time using $r_n$ to select among the remaining unset bits.

I threw the following Python code together showing the idea, though it's not fast or anything:

# b = size of integer type
# n = number of set bits
# random_limited(x) is some function returning [0, x) sufficiently uniformly
def random_n_set_bits(b, n):
 assert b > 0
 assert n >= 0 and n <= b
 result = 0
 available = list(range(b))
 for i in range(n):
 index = random_limited(len(available))
 bit = available[index]
 available = available[:index] + available[index + 1:]
 result |= (1 << bit)
 return result