Randomness
Take a look at the following puzzle:
“Given a function which produces a random integer from 1 to 5, write one that produces a random integer from 1 to 7″
I immediately thought of this:
... function naiveRand(){ return (given() + given()) % 7 + 1; } ...
It is obviously not random enough, you can guess that there are more chances of getting 7 than the other numbers, the number of combinations is 25, each one of these resulting in an integer between 1 and 7, but there are more ways of getting 7 than any other number, see:
1 : 4 chances: 5+2, 2+5, 3+4, 4+3 2 : 3 chances: 3+5, 5+3, 4+4 3 : 3 chances: 4+5, 5+4, 1+1 4 : 3 chances: 1+2, 2+1, 5+5 5 : 3 chances: 3+1, 1+3, 2+2 6 : 4 chances: 1+4, 4+1, 2+3, 3+2 7 : 5 chances: 5+1, 1+5, 4+2, 2+4, 3+3
More graphically:
That is clearly not the picture of a uniform distribution, so what if we add few more invocations to given()? Something like this would do the trick:
function newRand(){ return ( given() + given() + given() + given() + given() + given() ) % 7 + 1; }
The number of combinations is 5^6 (15625) and as you can see in the graphic above, it seems pretty random, but if you count the number of opportunities to get each integer from 1 to 7 you’ll find this:
1 : 2229 2 : 2224 3 : 2224 4 : 2229 5 : 2238 6 : 2243 7 : 2238
Number 6 is slightly more likely to come out. So how can this task be achieved? I spent around an hour trying to think of a better solution, but I couldn’t.
So I googled the question and I found a couple of posts with similar answers, none of them was a better approach, until I found Simon’s, which I think is more elegant and totally random, or at least as random as the given function should be:
function simonsRand(){ var randtab = [ [1,1,1,2,2], [2,3,3,3,4], [4,4,5,5,5], [6,6,6,7,7], [7,0,0,0,0] ]; var r = 0; while(r == 0) r = randtab[ givenRand() 1][ givenRand() 1]; return r; }
He makes a 5×5 table and uses just two executions of given() to produce a [i,j] position. Then repeats each integer from 0 to 7 exactly 3 times which is the best way to fill the table with minimum wasted spaces, if we hit 0, just repeat. We end up with 1/25 possibilities of hitting each position.
As you can see, both newRand() and simonsRand() produce similar results on a large scale, but Simon’s approach uses a lot less given() executions.

phil F