Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Random numbers between 1 and 15

I generate many many random numbers that need to be between 1 and 15 (included) in C++. Of course, I can generate zillons of std::uniform_int_distribution<std::mt19937::result_type> random(1, 15); but this is a waste since this mersenn twister generates 32 bits (or even 64 using mt19937_64) of random values, and I would only keep 4 bits and throw away all the rest, and in my case, performance is an issue and random number generation is a significant contributor.

My idea was thus to generate for example a single 64-bit random value between 0 and 2^64-1, and select 4 bits among them. The issue is that I can't find a way to have the generated values between 1 and 15. Example:

unsigned long long int r = uniform(generator); // between 0 and 2^64-1
unsigned int r1 = (r+1)&15;     // first desired random value
unsigned int r2 = ((r>>4)+1)&15; //second desired random value 
unsigned int r3 = ((r>>8)+1)&15; //third desired random value 
...

Here, this version of course doesn't work : despite the +1, the generated values are still between 0 and 15 (since if r&15 happens to be 0xb1111 then adding 1 produces the result 0xb0000).

Also, I would like the distribution to remain uniform (for instance, I wouldn't want to bias the least significant bit to occur more often, which could be the case with something like (r&15+1)|((r&15 +1) >> 4) since the value 0xb0001 would occur twice often).

like image 352
nbonneel Avatar asked Jul 10 '19 23:07

nbonneel


People also ask

What is the most common random number between 1 and 10?

Exploited in carnivals, the fact that given a choice of any number between 1 and 10, people will most often choose 3 or 7. Humans are lousy random-number generators and an unusually large number of them will pick 37 while a smaller, but still lopsided number of people will pick 73.

Why is 17 the most popular random number?

Seventeen is: Described at MIT as 'the least random number', according to the Jargon File. This is supposedly because in a study where respondents were asked to choose a random number from 1 to 20, 17 was the most common choice. This study has been repeated a number of times.

How many random 5 digit numbers are there?

Therefore, there are 90,000 unique 5-digit numbers possible.

What is the most popular random number?

The most random two-digit number is 37, When groups of people are polled to pick a “random number between 1 and 100”, the most commonly chosen number is 37.


1 Answers

Instead of

std::mt19937 gen(seed);
std::uniform_int_distribution<> dis(1, 15);

auto r1 = dis(gen);
auto r2 = dis(gen);
auto r3 = dis(gen);
auto r4 = dis(gen);

You might do:

std::mt19937 gen(seed);
std::uniform_int_distribution<> dis(0, 15 * 15 * 15 * 15 - 1); // Assuming int at least 16 bits

auto r = dis(gen);

auto r1 = r % 15 + 1; r /= 15;
auto r2 = r % 15 + 1; r /= 15;
auto r3 = r % 15 + 1; r /= 15;
auto r4 = r + 1;

Quick benchmark (second version 2.5 times faster than first one)

like image 129
Jarod42 Avatar answered Sep 24 '22 17:09

Jarod42