Math.random()

D

Dr John Stockton

JRS: In article <[email protected]>, seen in
news:comp.lang.javascript said:
JRS: In article <[email protected]>, seen in
news:comp.lang.javascript said:
By reading the FAQ and following its "shuffling" reference, you could
have found

function Shuffle(Q) { var R, T, J
for (J=Q.length-1 ; J>0 ; J--)
{ R=Random(J+1) ; T=Q[J] ; Q[J]=Q[R] ; Q[R]=T }
return Q }

which is AFAICS the best possible Shuffle.
I, like many others here, am a dial-up off-line user; so, where known,
"Please Give URL". The algorithm in the sci.crypto FAQ seems to be
equivalent to the above, encoded in C.
I certainly don't believe that.

"Thus, for example, if m = 2**32, certain permutations of 13 elements
will never occur, since 13! is approximately 1.45x2**32"
Knuth TAoCP, p. 146, vol. 2 third edition.

I was explicitly referring to the Shuffle algorithm; immediately above
what you quoted I had written "(assuming, that is, a perfect Random
function)." which you evidently failed to appreciate; ISTM evident that
it must apply to the paragraph below.

Which stand for?

The words "Please Give URL" appeared earlier in my previous article ...
 
J

John M. Gamble

To add a left turn into the conversation, a human, using a typical
shuffle, splitting a deck in two, and joining them, cannot create all
52! outcomes either. It is really just a combination of the two piles,
based on a given deck state. You can shuffle more than once, and have
more combos, but still, not all combos are equally likely.

To add yet another left turn to this, the act of human-shuffling is
not the only randomizer. Tossing in the cards after play, and
scooping them up will have an effect too. Heck, the type of game
will make a difference, since cards will be collected by players
in a different order depending upon whether they are playing
bridge or blackjack.
With that, if you want to simulate a (typical) human shuffle, you really
only need to have random numbers between 1 and 10, where 1,2,3 are more
likely than 10 (if you are en experienced shuffler). Then, you take a
given deck, split it in half (with a random deviance), and take random
ammounts from each side, one side, and then annother.

Then, do it one or two more times. This, to me seems more likely to be
a good shuffle algorithm for a card game. Oh yeah... dont forget to
split the deck :)

Heh. Of course there's always the "smear them around on the table"
method - a friend of mine would do that. She swore up and down that
she just couldn't do the classical shuffle.

And then there's the other type of shuffle (or is it properly called
a shuffle?), wherein one holds part of the deck in one hand, while
sort-of tossing the remaining cards back in with the other. I know
it has a name, but i can't remember it.
I did something like this, in a blackjack simulator... I wanted to test
betting techniques over a long period of time. I actually shuffled a
deck of cards about 20 times, and tallied up the probabilty of the
different card chunks that added together to a single deck. I found
that numbers such as 2 and 3 were much more common than 1 and 4, where 5
and 6 were practically unheard of. I used these stats to generate my
shuffle.

Ultimately, I scrapped the program, because it didn't deal with the many
factors that cannot be programmed, such as human emotion around the
table, and bad playing decisions on other player's parts. This threw a
mix into the final hand that made the my subtle shuffling algorithm
practically useless :)

Anyways, that is just a sidenote.

Interesting though. Thanks.
 
J

John M. Gamble

Yes, there is a big difference between a statistically good PRNG, and
a cryptographically strong one (or so I have been told :).

Yes, although in this case i believe it doesn't make a difference.

Hmm. I may be making an unwarranted assumption. I wrote my
previous message under the belief that javascript's Random is just
as statistically lousy as every other language's Random/rand/rnd
built-in or library-supplied function[1]. (Outside the function's
natural period, of course). Is that true? Has Random been tested
with the diehard suite?

[1] Excepting specially written packages which are not normally
included by default. Perl has Math::TrulyRandom; Java has
something like that too but i can't remember the name.
 
D

Dr John Stockton

JRS: In article <[email protected]>, seen in
If the period of the pseudo-random number generator is 2^32, then indeed,
it can at most generate 2^32 different shuffles, which is less than the
13! needed. I never thought of that restriction. :)

In fact, that restriction holds for any shuffling algorithm using a
PRNG with a period of 2^32.

Agreed.

The situation may be worse than you think, although (since,
unfortunately, the seed is not visible in javascript and its method of
generation is not evident) it's not necessarily easy to be sure.

Consider a Web page that generates a pack cards in logical order and
then, exactly once, applies a perfect shuffle method algorithm which,
however, calls the built-in Math.random.

It is already established that a system you use has a 32-bit seed (AIUI,
probable as that seems, it is not established that it uses R[n+1] =
(A*R[n]+B) mod 2^32) ; and that mine apparently uses a larger seed, 53
bits or more.

ASIDE A good Shuffle of N cards calls Random N times, or N-1 times; if
that number has a factor M in common with the cycle length C of
the PRNG (with N=52 or 53, M=4 is likely), then the cycle length
of the random sequences used will be C/M. However, C/M shuffles
probably leave the deck in a new order. Better to shuffle than
to deal a new deck every time.
/ASIDE

Given the shuffle method and the PRNG method, the result of the single
shuffle is determined by the initial value of the seed.

Ideally, this will itself be random.

But there is, in most systems, no intrinsic source of genuine random.

I believe some form of the time is usually used, perhaps permuted.

The Pascal that I use takes this time from the DOS clock at $40:6C,
which ticks (@55ms) $1800B0 times per day and then repeats. Only
$1800B0 of the $100000000 initial seeds can be given, 1/2730 of the
ideal. My Delphi, D3, is equivalent. Delphi 7, at least, does better.
( <URL:http://www.merlyn.demon.co.uk/pas-rand.htm> )

Javascript clearly has access to time with a resolution of 55ms or 10ms
(in Windows; what might it have on non-PC systems?); at 55ms, 2730 days
will be needed to get all 32-bit seeds.

One cannot be sure, without evidence, when the seed is initialised -
when the browser is loaded, when the window is opened, when the page is
loaded, when Math.random is first called, ...
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

Forum statistics

Threads
473,744
Messages
2,569,482
Members
44,901
Latest member
Noble71S45

Latest Threads

Top