Rand7 generates Rand10
"TLDR: This article explains how to use mathematical principles and C++ code to generate equiprobable random numbers. First, random numbers in the range of $[1, X * Y]$ with equal probability can be generated through the mathematical formula $(randX() - 1) * Y + randY()$. The proof process is based on $randX()$ and $randY()$ generating equal-probability random numbers between $[1, X]$ and $[1, Y]$ respectively. The joint probability table shows how to sample uniformly distributed random numbers between $[1, XY]$ from these random numbers. Next, the article provides a code example written in C++ that demonstrates how to generate uniform random numbers within a specified range by constructing a specific expression. However, this method is less efficient because it will only stop when the sample is between $[1, 10]$, and the numbers between $[11, 49]$ will be discarded. In order to improve efficiency, the article proposes an optimization method that reduces the range to $[1, 10]$ through modular division operations, and further optimizes it to only sample numbers between $[41, 49]$, thereby improving efficiency. Finally, the article also discusses ways to solve the problem from a base point of view, pointing out that if a given $rand1()$ can only generate uniform random numbers between $[0, 1]$, then binary encoding can be used to generate uniform random numbers between $[a, b]$."
Mathematical Principles
Mathematical law: can generate random numbers in the range of with equal probability
Proof: Since can generate equal-probability random numbers between , can generate equal-probability random numbers between
Then can be randomly sampled in ,
Therefore, the joint probability table formed by is:
Therefore, as can be seen from the table, random numbers between can be uniformly sampled
code
According to the above formula, if you want to generate through , you can first construct , thus achieving uniform random sampling between
The code is as follows:
#include<iostream>
using namespace std;
int main() {
while(1) {
int rand_value = (rand7() - 1) * 7 + rand7();
if(rand_value >= 1 && rand_value <= 10){
cout << rand_value<< endl;
break;
}
}
return 0;
}
However, the efficiency of this method is low, because the sampling only ends when it reaches , and the numbers between will be discarded.
With further optimization, uniform random sampling can be performed between , and can be scaled to using modular division.
#include<iostream>
using namespace std;
int main() {
while(1) {
int rand_value = (rand7() - 1) * 7 + rand7();
if(rand_value >= 1 && rand_value <= 40){
cout << rand_value % 10 << endl;
break;
}
}
}
In this way, only the numbers between will be discarded, and the efficiency will be higher.
Base solution
The above solution lies in the proof and practicality of mathematical formulas. Another solution is to think from the perspective of base system.
First of all, if is given, only uniform random numbers between can be generated. How to construct uniform random numbers of ? In this case, the above formula cannot be applied directly.
If you look at it from a binary point of view, it is easy to generate a uniform random number between , because you can use the random function for each bit of the binary. Then you can easily generate uniform random numbers between
Now change the question to given , and hope to generate a uniform random number of , then this is to use the 7-base system to randomly generate a number between