Dr John Stockton <(E-Mail Removed)> writes:

>>which is much better, going on canonical.

>

> 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.

>>First choice (num choices):

>> var selected = Math.floor(Math.random()*num);

>>

>>Later choice (num-1 choices to avoid repeat):

>> var tmp = Math.floor(Math.random()*(num-1));

>> selected = (tmp >= selected ? tmp+1 : tmp);

>

> 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

--

Lasse Reichstein Nielsen -

(E-Mail Removed)
DHTML Death Colors: <URL:http://www.infimum.dk/HTML/rasterTriangleDOM.html>

'Faith without judgement merely degrades the spirit divine.'