Math.random()

[Thomas Mlynarczyk]

I remember there is a programming language where you can initialize the
random number generator, so that it can - if you want - give you the exactly
same sequence of random numbers every time you initialize it with the same
parameter. Can this be done with JavaScript? I couldn't find anything in the
documentation. Basically, what I want to achieve is to obtain always the
same sequence of random numbers for the same given initialization value (but
of course different sequences for different init values).

Can this be done in JavaScript?

Greetings,
Thomas

 

[lallous]

Hello

AFAIK, This cannot be done w/ JavaScript, but allowed with languages such as
C, Pascal, ...

To solve your problem, write your own random and randomize functions as:

var randSeed = 1234; // initial seed
function randomize()
{
// use math.random() to generate a random number and assign to initial
seed
}

function random()
{
randSeed = (randSeed * 1232) + (randSeed % 212) - randSeed & 0xFA11;
// put any forumla you want....i am not an export at writing pseudo number
generators functions
}

To generate same sequence:
randSeed = 232; // your initial seed
for (i=0;i<10;i++)
document.write(random() + "<br>"); // this will generate same sequence!

To generate a new sequence everytime, call randomize() or simply init
randSeed variable to a value of your choice.

HTH,
Elias

 

[Dr John Stockton]

JRS: In article <[email protected]>, seen in
lallous <[email protected]> posted at Mon, 16
Feb 2004 14:26:56 :-

Responses should go after trimmed quotes, as per FAQ; corrected.

AFAIK, This cannot be done w/ JavaScript, but allowed with languages such as
C, Pascal, ...

It is not necessarily a matter of the language, but may be just of the
implementation of the language library. If anyone here is writing a new
ECMA-262, then the random seed needs to be made a read/write variable.
In test, it is useful for randoms to be reproducible.

To solve your problem, write your own random and randomize functions as:

var randSeed = 1234; // initial seed
function randomize()
{
// use math.random() to generate a random number and assign to initial
seed
}

function random()
{
randSeed = (randSeed * 1232) + (randSeed % 212) - randSeed & 0xFA11;
// put any forumla you want....i am not an export at writing pseudo number
generators functions
}

Nor an expert at spelling; but, from TZ +0200, that is not important.

Donald E Knuth wrote :- "Random numbers should not be generated with a
method chosen at random". Choice of a good algorithm is non-trivial,
except for those willing to look up available resources rather than
reinvent the wheel themselves.

See
<URL:http://www.merlyn.demon.co.uk/pas-rand.htm>
<URL:http://www.merlyn.demon.co.uk/js-randm.htm>
and Knuth's volumes.

The following are reported good (X[n] are successive RandSeed) :-

X[n+1] = 134775813*X[n] + 1 (mod 2^32)
X[n+1] = 1664525*X[n] + 1013904223 (mod 2^32)

Divide by 2^32, of course.

The expression of lallous is, in fact, remarkably bad; initialised with
1234, it immediately enters a cycle of length 4. With 1, it soon
reaches a cycle of length 2.

0xFA11 = 1111 1010 0001 0001, with 8 bits set; we have, in effect, an
8-bit seed and a maximum cycle length of 256.

 

[Thomas Mlynarczyk]

Also sprach lallous:

AFAIK, This cannot be done w/ JavaScript
:-(((

randSeed = (randSeed * 1232) + (randSeed % 212) - randSeed & 0xFA11;
// put any forumla you want....i am not an export at writing pseudo
number generators functions

Well, I don't need anything statistically sophisticated. The background is,
I'm programming a game and need to lay out some cards in a random order to
start playing. Now I want to be able to get back to the same layout later by
simply selecting "game number 12345", where 12345 will be the seed that
should always generate the same deck of cards. Currently I shuffle the cards
by selecting two at random and swapping their places. This I do a number of
times, so more or less all the cards should be randomly displaced.

 

[lallous]

JRS: In article <[email protected]>, seen in
lallous <[email protected]> posted at Mon, 16
Feb 2004 14:26:56 :-

Responses should go after trimmed quotes, as per FAQ; corrected.



It is not necessarily a matter of the language, but may be just of the
implementation of the language library. If anyone here is writing a new
ECMA-262, then the random seed needs to be made a read/write variable.
In test, it is useful for randoms to be reproducible.





Nor an expert at spelling; but, from TZ +0200, that is not important.

I learned my english through programming...so no wonder if tech words
come to mind and fingers first!

Donald E Knuth wrote :- "Random numbers should not be generated with a
method chosen at random". Choice of a good algorithm is non-trivial,
except for those willing to look up available resources rather than
reinvent the wheel themselves.

See
<URL:http://www.merlyn.demon.co.uk/pas-rand.htm>
<URL:http://www.merlyn.demon.co.uk/js-randm.htm>
and Knuth's volumes.

The following are reported good (X[n] are successive RandSeed) :-

X[n+1] = 134775813*X[n] + 1 (mod 2^32)
X[n+1] = 1664525*X[n] + 1013904223 (mod 2^32)

Divide by 2^32, of course.

The expression of lallous is, in fact, remarkably bad; initialised with
1234, it immediately enters a cycle of length 4. With 1, it soon
reaches a cycle of length 2.

Yes, I am aware of that, I was just trying to indicate how to create
own random function with a seed variable.

 

[Dr John Stockton]

JRS: In article <[email protected]>, seen in
Thomas Mlynarczyk

Also sprach lallous:

Well, I don't need anything statistically sophisticated. The background is,
I'm programming a game and need to lay out some cards in a random order to
start playing. Now I want to be able to get back to the same layout later by
simply selecting "game number 12345", where 12345 will be the seed that
should always generate the same deck of cards. Currently I shuffle the cards
by selecting two at random and swapping their places. This I do a number of
times, so more or less all the cards should be randomly displaced.

Your shuffling is, therefore, very probably not enough to achieve full
randomness, or more than is necessary to achieve full randomness, or
does not give equal probability to all possible results (assuming, that
is, a perfect Random function).

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.

However, for your stated purpose, you do not need a Shuffle, but can do
a Deal which generates 0..N-1 in random order

function Deal(N) { var J, K, Q = new Array(N)
for (J=0; J<N; J++) { K = Random(J+1) ; Q[J] = Q[K] ; Q[K] = J }
return Q }

The best choice depends on how you represent the cards by variables.

 

[Thomas Mlynarczyk]

Strange... I had posted this before, but it doesn't seem to show up...? So,
I'll have another try:

Also sprach lallous:

AFAIK, This cannot be done w/ JavaScript
randSeed = (randSeed * 1232) + (randSeed % 212) - randSeed & 0xFA11;
// put any forumla you want....i am not an export at writing pseudo
number generators functions

Well, I don't need anything statistically sophisticated. The background is,
I'm programming a game and need to lay out some cards in a random order to
start playing. Now I want to be able to get back to the same layout later by
simply selecting "game number 12345", where 12345 will be the seed that
should always generate the same deck of cards. Currently I shuffle the cards
by selecting two at random and swapping their places. This I do a number of
times, so more or less all the cards should be randomly displaced.

 

[John M. Gamble]

JRS: In article <[email protected]>, seen in
Thomas Mlynarczyk

Also sprach lallous:

Well, I don't need anything statistically sophisticated. The background is,
I'm programming a game and need to lay out some cards in a random order to
start playing. Now I want to be able to get back to the same layout later by
simply selecting "game number 12345", where 12345 will be the seed that
should always generate the same deck of cards. Currently I shuffle the cards
by selecting two at random and swapping their places. This I do a number of
times, so more or less all the cards should be randomly displaced.

Your shuffling is, therefore, very probably not enough to achieve full
randomness, or more than is necessary to achieve full randomness, or
does not give equal probability to all possible results (assuming, that
is, a perfect Random function).

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.

This is actually well-known to be a bad shuffle algorithm. The
question comes up occasionally in sci.crypt, and also was discussed
in detail in the comp.lang.perl.moderated newsgroup. I think that
the perl FAQ was corrected with a much better shuffle as a result
(look for the key word 'permute').

The major flaw with this algorithm is that not all permutations are
equally possible. This may not be the worst problem with a
card-shuffling program, but i would be annoyed with it.

The algorithm (or one of them) that should be looked at is the
Fischer-Krause algorithm.

 

[Lasse Reichstein Nielsen]

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.

This is actually well-known to be a bad shuffle algorithm. ....
The major flaw with this algorithm is that not all permutations are
equally possible. This may not be the worst problem with a
card-shuffling program, but i would be annoyed with it.

I think you are misreading the algorithm. In particular, notice that
the call to Random uses the loop iterator as argument. It does perform
a permutation and all permutations are equally probable (if the Random
function is, at least ... there are small deviations because you can't
use a random number in the range, e.g., 0..2^32-1 to pick a random
number in the range 0..6 with equal probability, but that is not a
serious problem unless Q.length is very large)

/L

 

[Pete]

Also sprach lallous:


Well, I don't need anything statistically sophisticated. The background is,
I'm programming a game and need to lay out some cards in a random order to
start playing. Now I want to be able to get back to the same layout later by
simply selecting "game number 12345", where 12345 will be the seed that
should always generate the same deck of cards. Currently I shuffle the cards
by selecting two at random and swapping their places. This I do a number of
times, so more or less all the cards should be randomly displaced.

This is similar to Freecells game recall method:

<html>
<head>
<title>Game Id</title>
</head>
<body>

<script>
var gameNumber=1; //1 to 1,000,000
var n=52; //card numbers, id's or whatever.

function rnd(){
gameNumber=gameNumber*314591+343421;
gameNumber=gameNumber-1000000*Math.floor(gameNumber/1000000);
return gameNumber/1000000;
}

function doIt(){
chosenGame=new Array();
for (var i=0; i < n; i++){
chosenGame = i;
}
var k, x;
for (var i=0; i < n-1; i++){
k=Math.floor((n-i)*rnd());
if (k==(n - i)){
k=n-i-1;
}
x=chosenGame;
chosenGame=chosenGame[i+k];
chosenGame[i+k]=x;
}
alert("Game id = "+gameNumber+"\nHowever, your user would just"
+" input original 'gameNumber' to replay this game, #1 in this"
+" example.\n\n"+chosenGame);
}
doIt();
</script>

</body>
</html>

 

[Dr John Stockton]

JRS: In article <[email protected]>, seen
in Pete <[email protected]>
posted at Tue, 17 Feb 2004 20:10:43 :-

This is similar to Freecells game recall method:

var gameNumber=1; //1 to 1,000,000

I think that should be 0 to 999999

var n=52; //card numbers, id's or whatever.

function rnd(){
gameNumber=gameNumber*314591+343421;
gameNumber=gameNumber-1000000*Math.floor(gameNumber/1000000);

That looks like gameNumber %= 1000000

return gameNumber/1000000;
}

So that's a mod 10^6 version of the usual mod 2^32 or 2^n algorithm. I
expect it to be good if the numbers are well-chosen, but not if they are
randomly chosen. In Math.random, the method should be at least equally
good, but implemented faster.

for (var i=0; i < n; i++){
chosenGame = i;
}
var k, x;
for (var i=0; i < n-1; i++){
k=Math.floor((n-i)*rnd());
if (k==(n - i)){
k=n-i-1;
}
x=chosenGame;
chosenGame=chosenGame[i+k];
chosenGame[i+k]=x;
}

That looks similar to mine, but less efficient in its indexing.

The if (k==(n - i)){ k=n-i-1; } should not be necessary, since the
result of rnd seems to be less than 1.


"My" method was taken from a reliable-seeming source, and most people
seem willing to believe that it is best.

Discussion is at <URL:http://www.merlyn.demon.co.uk/pas-rand.htm#SDD>.

 

[Dr John Stockton]

JRS: In article <[email protected]>, seen in

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.

This is actually well-known to be a bad shuffle algorithm.

I don't believe you.

The
question comes up occasionally in sci.crypt, and also was discussed
in detail in the comp.lang.perl.moderated newsgroup. I think that
the perl FAQ was corrected with a much better shuffle as a result
(look for the key word 'permute').

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.

The major flaw with this algorithm is that not all permutations are
equally possible.

I certainly don't believe that.

This may not be the worst problem with a
card-shuffling program, but i would be annoyed with it.

Agreed that it would be a major flaw.

The algorithm (or one of them) that should be looked at is the
Fischer-Krause algorithm.

PGU.

 

[Thomas Mlynarczyk]

Also sprach Lasse Reichstein Nielsen:

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.

This is actually well-known to be a bad shuffle algorithm.

I think you are misreading the algorithm.

Thanks to all of you for your advice and pointing out that link in the FAQ.
The algorithm that I am currently using is this:

var i = 2 * cards.length;
while(i--) {
c1 = parseInt(Math.random() * cards.length);
c2 = parseInt(Math.random() * cards.length);
c = cards[c1];
cards[c1] = cards[c2];
cards[c2] = c;
}

I'm sure it could be optimized and maybe a lower initial value for i would
be sufficient.

 

[Thomas Mlynarczyk]

Also sprach Pete:

This is similar to Freecells game recall method:

var gameNumber=1; file://1 to 1,000,000
var n=52; file://card numbers, id's or whatever.

function rnd(){
gameNumber=gameNumber*314591+343421;
gameNumber=gameNumber-1000000*Math.floor(gameNumber/1000000);
return gameNumber/1000000;
}

function doIt(){
chosenGame=new Array();
for (var i=0; i < n; i++){
chosenGame = i;
}
var k, x;
for (var i=0; i < n-1; i++){
k=Math.floor((n-i)*rnd());
if (k==(n - i)){
k=n-i-1;
}
x=chosenGame;
chosenGame=chosenGame[i+k];
chosenGame[i+k]=x;
}
alert("Game id = "+gameNumber+"\nHowever, your user would just"
+" input original 'gameNumber' to replay this game, #1 in this"
+" example.\n\n"+chosenGame);
}
doIt();

Thanks a lot - that seems to be the thing I'm looking for!

Greetings,
Thomas

 

[Lasse Reichstein Nielsen]

"My" method was taken from a reliable-seeming source, and most people
seem willing to believe that it is best.

Knuth's "The Art of Computer Programming" is not just reliable-seeming.
It is authoritative, going on definitive.

/L

 

[Dr John Stockton]

JRS: In article <[email protected]>, seen in

Knuth's "The Art of Computer Programming" is not just reliable-seeming.
It is authoritative, going on definitive.

But I did not get the method directly from Knuth; I only have it on
hearsay that it's in Knuth, and the version I presented has been
translated at least twice.

 

[John M. Gamble]

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.

This is actually well-known to be a bad shuffle algorithm. ...
The major flaw with this algorithm is that not all permutations are
equally possible. This may not be the worst problem with a
card-shuffling program, but i would be annoyed with it.

I think you are misreading the algorithm. In particular, notice that
the call to Random uses the loop iterator as argument. It does perform

Yes. It's still possible that i'm misreading the algorithm, of course,
but i was aware of that.

In a posting to sci.stat.math, sci.math and sci.crypt, on Octorber 7
1999, subject: "Re: Perfect Shuffle Algorithm?" (I've changed the '>'
characters to '-' to avoid confusion with the current mesage).

-- The classic card-shuffling algorithm that I've seen and used does not
-- replicate the human technique at all, but it produces a throughly
-- scrambled deck instantly. In Pascal:

-- for n := 52 downto 2 do SwapCards(n, Random(1,n));

-- where "SwapCards" exchanges the position of two specified cards, and
-- "Random(1,n)" produces a random number in the inclusive range [1..n].

-I don't know your definition(s) of 'thoroughly' and 'instantly', but you
-might find the comments in volume 2 of Knuth, starting with the
-paragraph at the bottom of page 145 of the 3rd edition, of interest.
-Partial quote "...cannot possibly generate more than..." Even with just
-13 cards, the common random number generators based on 2^32 values can
-not generate all shuffles.

Herman Rubin then pointed out that you can if your random number
source is good, but i will wager that Random does not meet sci.crypt's
general criteria for 'good'.

 

[John M. Gamble]

JRS: In article <[email protected]>, seen in

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.

This is actually well-known to be a bad shuffle algorithm.

I don't believe you.

Uh, okay. Is that "I think you are a liar," or "I think you are
mistaken?"

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.

Hmm. I'm a dial-upper myself. I'm not surprised that sci.crypt FAQ
is not modified, since someone would actually have to take the time
to bother. I did mention the perl FAQ (hmm. Assuming that whoever
actually did bother - he said so, but i've not actually checked).

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.

Agreed that it would be a major flaw.


PGU.

Which stand for?

 

[Lasse Reichstein Nielsen]

Yes. It's still possible that i'm misreading the algorithm, of course,
but i was aware of that.

In a posting to sci.stat.math, sci.math and sci.crypt, on Octorber 7
1999, subject: "Re: Perfect Shuffle Algorithm?" (I've changed the '>'
characters to '-' to avoid confusion with the current mesage).

-- The classic card-shuffling algorithm that I've seen and used does not
-- replicate the human technique at all, but it produces a throughly
-- scrambled deck instantly. In Pascal:

-- for n := 52 downto 2 do SwapCards(n, Random(1,n));

You didn't misread then, that is the algorithm

-Even with just
-13 cards, the common random number generators based on 2^32 values can
-not generate all shuffles.

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.

If you can actually generate randomness enough to get 52! different
outcomes, this algorithm uses exactly that much, making each shuffle
equally likely.

Herman Rubin then pointed out that you can if your random number
source is good, but i will wager that Random does not meet sci.crypt's
general criteria for 'good'.

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

/L

 

[Brian Genisio]

You didn't misread then, that is the algorithm




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.

If you can actually generate randomness enough to get 52! different
outcomes, this algorithm uses exactly that much, making each shuffle
equally likely.




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

/L

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.

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

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.

Brian