The foreword 0.

Given a function that generates random integers 1-7, call it generator get7. Use it to generate random integers 1-11, not random, with equal probability.

Getx is a function that generates random numbers from 1 to x

Get7 (Random is disabled for all of you)

function  get7() {
	return~ ~ (Math.random()*7) +1 // Rule: the only place random can be used in the whole article
}
Copy the code

1. Expand + Partition

Since it is an extension, I will extend the small range random number generator several times, and then intercept the target random number range. How to use get7 to implement a qualified GET14? It look like?

function get14(){
	return get7() +get7() 
}
Copy the code

Let’s test it out:

    	var obj = Object.create(null)
    	for(var i = 0; i<1000000; i++){var n = get14();
    		if(! obj[n]){ obj[n] =1
    		}else{
    			obj[n] ++
    		}
    	}
    	console.log(obj)
Copy the code

Leaving the minima problem aside, first of all, it’s not an equal-probability sequence so let’s ask another question, can get14 be represented by get7 plus, minus, multiply and divide?

Hey, are you sure you’re okay with get7 of alpha times 11/7?

1.1 extensions

Since it is a random expansion from a small range to a large range, it must be inseparable from the multiple calls of the small range random number generator get7. Of course, our final goal is very clear, the target is get11 random number generator, every random number of which will be equally probability mapped to the extended sequence of get7:

Then we can quickly come up with a formula:

a*(getx - 1) + getx
Copy the code

A is an integer, and the whole formula says, you expand getx to a times, and you implement an equal probability distribution. For example, if x is 3 and we want to expand it by 2, a=2 is 2* get3-1 + get3, the range is 1-7, but let’s look at the probabilities:

X \y 1 2 3 0 1 2 3 2 3 4 5 4 5 6 7 = "the probability of 1-7 is 1:1:2:1:2:1Copy the code

Obviously this formula has a premise

1.2 Value range of A

Let’s look at a = 1:

X \y 1 2 3 0 1 2 3 1 2 3 4 2 3 4 5 = "the probability of 1-5 is 1:2:3:2:1Copy the code

It’s like every row of the matrix has an intersection

// If a is 3, ran3-1 produces 0-6, and ran3 produces 1-3 x\y 1 2 3 0 1 2 3 3 4 5 6 6 7 8 9 = "1-9 equal probability // If a is 4, Ran3-1 produces 0-8, Ran3 produces 1-3 x\y 1 2 3 0 1 2 3 4 5 6 7 8 9 10 11 =Copy the code

Therefore, as long as all numbers are equally likely to appear, first satisfy that the maximum value of the mapping table is greater than or equal to its own square (3*3 = 9, that is, a is at least 3). Why? Because of lack of itself, there is bound to be overlap, as each line 1 and 2 above two matrix has intersection, as long as the size of the greater than itself, there would be no intersection, each line matrix no intersection, then they can equal probability So, to 7 would like to extend a sequence, such as probability get14 (get less than 49 are useless, not equal probability) is clearly it’s no use. At least get49, after which all sequences are 49 in length. So a get14 has to be gotten by get49, and we can go from get49 to get11

1.3 From get49 to get11

function get49() {var n = 7 * (get7 () - 1) + get7 () / / a * (getx - 1) + getx, a 7, does not believe that he look at the printingreturn  n
}
var obj = Object.create(null)
for(var i = 0; i<1000000; i++){ var n = get49();if(! obj[n]){ obj[n] = 1 }else{
		obj[n] ++
	}
}
console.log(obj)
Copy the code

Now that we see that all the elements are equally likely, we just have to get rid of the superfluous ones, that is, the ones that are not in the range that we want, and regenerate.

function get11() {var n = 7 * (get7 () - 1) + get7 () / / a * (getx - 1) + getx, a 7, does not believe that he look at the printingreturnn > 11? get11():n }Copy the code

Change get49 to get49, it seems that too many extended arrays are useless, we should improve the utilization of extended arrays, and reduce recursion

function get11(){
	var n = 7*(get7()-1) + get7() 
	returnn>44? get11():~~((n-1) / 4)+1 }Copy the code

2. Binary method

To binary classification of small random number function, half said 1 0, then expressed in binary random number, and then remove excess get7 get11, 8 11 < < 16, we take 4 bit binary, namely take 4 times get7 because 7 is odd, let’s get rid of a, then we take out 1, when faced with 1 to regenerate once, Divide the rest in half

// Get the binary sequencefunction getBinary(){
	var n = get7()
	if(n>4){
		return1}else if(n>1){
		return0}else{
		returnGetBinary ()}} // Convert the binary sequence backfunction get11_by_binary(){
	var res = ' '
	for(var i = 0; i<4; i++){ res += getBinary() } res = parseInt(res,2)returnres>11? get11_by_binary():res }Copy the code

Of course, the performance is much worse because there are too many iterations. A generic version is not difficult, you can encapsulate one yourself.

3. Summary

The first method is actually called sampling rejection. We know that equal probability generates a certain range of random numbers. If we want to use this function to generate a smaller range of random numbers, we should look like this: beyond the expected range, re-sampling, so it is called rejection sampling. Basic operations:

// We still use get7 to get random numbers from 1 to less than 7functionGetn (n){var num = get7()returnnum > n? getn(n):num } //whileIn the form offunction getn(n){
	var t
	do{
		t = get7()
	}while(t>n)
	return t
}
Copy the code

Get14 = 7*2 = 14

function get14(){
	var t
	do{
		t = get7()
	}while(t>2)// Let's call it get2returnGet7 () + 7 *(t -1) // A *(getx -1) + getx is a variant of the above formula.Copy the code

If get11 is greater than 11, the sample will be rejected. I want get49 first, okay? This is a gradual process, so that you can understand how the process works. Does it feel flexible to reject sampling?

Generality of formula: given that generator getn can generate 1-n random numbers, then the new generator geta and getb obtained by getn rejection sampling (a, b are not greater than n) can generate GET (a*b) :

Get (a*b) = geta + a* getb-1 Get14 () = get7() + 7 *(get2() -1) = get2() + 2*(get7() -1 (get2() -1) = get2() + 2*(get5() -1)Copy the code

Get7 can get get2, get14 can get get5, get10 can do the same thing. Just right is perfect, and if the target generator is prime, keep rejection samples as small as possible, that is, as close to the target as possible. This kind of random number expansion, the pattern is over the reject sampling, insufficient use of addition and multiplication to make just to the target range or over the target