Dr John Stockton said:
In at least one browser, |0 is a little faster than Math.floor.
But it only works for numbers less than 2^32. For most practical
purposes that is not a problem, but it needs to be said, so doesn't
qualify as canonical
I was told that, in some Opera, Math.random can give 1, which
Math.random()%1 will fix.
Correct. I have forgotten the version, but I think it was O5.
That is an error in Opera, though, and shouldn't be used to
complicate the general solution.
To find a random number in the range 0..n-1, this is the most direct
version and, barring implementation errors of the primitives, it
works correctly for all numbers that can be represented:
Math.floor(Math.random()*n);
(Interesting observation: In Opera 7,
Math.random()*Math.pow(2,32)
is always an integer. That means that the random floating point number
is simply a 32-bit random integer divided by 2^32. Multiplying
by only Math.pow(2,31) gave numbers ending in ".5" half the time.
I.e, at most 32 bits worth of randomness in each random number.
In IE and MozFireFox, there are decimals on the result
If javascript were better designed, Math.random(N) would give a random
integer in 0..(N-1) - Random in Pascal gives 0 <= X < 1 but Random(N)
gives 0 <= n < N.
I agree. It is the most common use of random number generation, and
should be supported directly.
ISTM that the probability on the second choice of getting the next
higher number will be doubled, unless the first selected was the
highest.
No, all elements that were not the previous choice have an equal
chance. It has no memeory about choices before that, all it prevents
is that the same element is chosen twice in a row.
If the first choice picks number 5 out of 0..7, the second choice
picks a random number between 0 and 6. If it is 5 or above, it adds
one, so the possible outcomes become 0, 1, 2, 3, 4, 6 and 7.
n = -1 // untested
for (j=0; j<2
{ t = Random(N) ; if (t != n) A[j++] = n = t }
This rerolls until it gets a new result. It has expected execution
time O(2 * N/(N-1)), but in the hypothetical worst case, it never
terminates because it keeps rolling the same number.
It won't diverge when using a pseudo-random number generator, because
it won't generate the same number every time and will eventually
(depending on its period) hit the entire phase space. It still makes
analysis a little harder
A = [] // untested
for (j=0 ; j<K
{ t = Random(N) ; if (!A[t]) { A[t]=t ; j++ }
change to "true", or 0 can never be marked ^
Picks K out of N random numbers, no element twice. Execution time
can be bad. If K>N, it always diverges, but that would be stupid
You should store the result somewhere (e.g., B[j++]=t) or use it.
If N=K, it finds a permutation. The expected time for that is
O[n*ln(N)] (not as bad as I feared, although it can be done
in linear time)
But the easy general solution is to do a partial shuffle.
Yes. Finding a random permutation and keep cycling that is often
better than completely random switching (with no immediate repeates).
This problem seems to often come up for people permuting advertisment
banners
/L