Solution: Rejection Sampling
function rand5() {
// Returns random integer 0-4 uniformly
return Math.floor(Math.random() * 5);
}
function rand7() {
// Generate number 0-24 using two calls to rand5()
let num;
do {
num = rand5() * 5 + rand5(); // 0-24
} while (num >= 21); // Reject 21-24
// Map 0-20 to 0-6
return num % 7;
}
// Test distribution
function testDistribution() {
const counts = Array(7).fill(0);
const trials = 70000;
for (let i = 0; i < trials; i++) {
counts[rand7()]++;
}
console.log("Distribution test (should be ~10000 each):");
counts.forEach((count, i) => {
console.log(` ${i}: ${count} (${(count/trials*100).toFixed(1)}%)`);
});
}
testDistribution();
General Solution: randN from randM
function makeRandN(randM, M, N) {
return function randN() {
// Find how many calls we need
let k = 1;
let range = M;
while (range < N) {
k++;
range *= M;
}
// Find largest multiple of N that fits in range
const maxValid = Math.floor(range / N) * N;
let num;
do {
num = 0;
for (let i = 0; i < k; i++) {
num = num * M + randM();
}
} while (num >= maxValid);
return num % N;
};
}
// Create rand7 from rand5
const rand7FromMake = makeRandN(rand5, 5, 7);
console.log(rand7FromMake()); // Random 0-6
Reverse: rand5 from rand7
function rand7() {
return Math.floor(Math.random() * 7);
}
function rand5FromRand7() {
let num;
do {
num = rand7();
} while (num >= 5); // Reject 5, 6
return num;
}
// Expected calls: 7/5 = 1.4
More Efficient: Reuse Rejected Values
function rand7Efficient() {
// Use remainder from rejection
let num = rand5() * 5 + rand5(); // 0-24
if (num < 21) {
return num % 7;
}
// num is 21-24 (4 values)
// Use as start for next attempt
num = (num - 21) * 5 + rand5(); // 0-19
if (num < 14) {
return num % 7;
}
// num is 14-19 (6 values)
num = (num - 14) * 5 + rand5(); // 0-29
if (num < 28) {
return num % 7;
}
// Very rare, just retry
return rand7Efficient();
}
// Expected calls: slightly better than 2.38
Step-by-Step Example
Call 1: rand5() = 3
Call 2: rand5() = 4
num = 3 * 5 + 4 = 19
Is 19 < 21? Yes
Return 19 % 7 = 5 ✓
Another example:
Call 1: rand5() = 4
Call 2: rand5() = 2
num = 4 * 5 + 2 = 22
Is 22 < 21? No, retry
Call 3: rand5() = 1
Call 4: rand5() = 0
num = 1 * 5 + 0 = 5
Is 5 < 21? Yes
Return 5 % 7 = 5 ✓
Why Uniform?
Each of 0-20 appears exactly 3 times in 0-24:
0: appears at 0
1: appears at 1
...
6: appears at 6
0: appears at 7
...
6: appears at 13
0: appears at 14
...
6: appears at 20
Values 0-6 each appear 3 times in 0-20.
After modulo 7, each 0-6 equally likely.
Complexity Analysis
Average calls to rand5(): 2 / (21/25) ≈ 2.38
Worst case: Unbounded (theoretically infinite, practically rare)
Space: O(1)
Common Mistakes
- rand5() + rand5(): Not uniform (more likely to get middle values)
- rand5() % 7: Not uniform (0-4 more likely than 5-6)
- Not rejecting: Must reject to ensure uniformity
- Wrong rejection range: Must use largest multiple that fits
Probability Distribution Comparison
// WRONG: rand5() + rand5()
// 0 appears only when both return 0 (1/25 chance)
// 4 appears 5 ways: (0,4), (1,3), (2,2), (3,1), (4,0) (5/25 chance)
// NOT UNIFORM!
// CORRECT: rejection sampling
// Each of 0-6 has exactly 3/21 chance
// UNIFORM!
Follow-Up Questions
Q: Generate random float [0, 1) from rand5()?
A: Use multiple calls: rand5()/5 + rand5()/25 + rand5()/125...
Q: Generate rand49() from rand7()?
A: rand7() * 7 + rand7() gives 0-48, no rejection needed!
Q: What if rand5() is expensive?
A: Use efficient version that reuses rejected values
Related Problems
