440,117 Members | 2,142 Online
Need help? Post your question and get tips & solutions from a community of 440,117 IT Pros & Developers. It's quick & easy.

# Math.random()

 P: n/a 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 Jul 20 '05 #1
23 Replies

 P: n/a 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() + "
"); // 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 "Thomas Mlynarczyk" wrote in message news:c0*************@news.t-online.com... 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 Jul 20 '05 #2

 P: n/a 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. Jul 20 '05 #3

 P: n/a JRS: In article , seen in news:comp.lang.javascript, lallous posted at Mon, 16 Feb 2004 14:26:56 :- Responses should go after trimmed quotes, as per FAQ; corrected. "Thomas Mlynarczyk" wrote in messagenews:c0*************@news.t-online.com... I remember there is a programming language where you can initialize the random number generator, so that it can - if you want - give you theexactly 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 inthe 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? AFAIK, This cannot be done w/ JavaScript, but allowed with languages such asC, 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 seedfunction randomize(){ // use math.random() to generate a random number and assign to initialseed}function random(){ randSeed = (randSeed * 1232) + (randSeed % 212) - randSeed & 0xFA11; // put any forumla you want....i am not an export at writing pseudo numbergenerators 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 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. -- © John Stockton, Surrey, UK. ?@merlyn.demon.co.uk Turnpike v4.00 IE 4 © Jim Ley's FAQ for news:comp.lang.javascript jscr maths, dates, sources. TP/BP/Delphi/jscr/&c, FAQ items, links. Jul 20 '05 #4

 P: n/a Dr John Stockton wrote in message news:... JRS: In article , seen in news:comp.lang.javascript, lallous posted at Mon, 16 Feb 2004 14:26:56 :- Responses should go after trimmed quotes, as per FAQ; corrected."Thomas Mlynarczyk" wrote in messagenews:c0*************@news.t-online.com... 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?AFAIK, This cannot be done w/ JavaScript, but allowed with languages such asC, 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 seedfunction randomize(){ // use math.random() to generate a random number and assign to initialseed}function random(){ randSeed = (randSeed * 1232) + (randSeed % 212) - randSeed & 0xFA11; // put any forumla you want....i am not an export at writing pseudo numbergenerators functions} 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 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. 0xFA11 = 1111 1010 0001 0001, with 8 bits set; we have, in effect, an 8-bit seed and a maximum cycle length of 256. -- Elias Jul 20 '05 #5

 P: n/a 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. Jul 20 '05 #6

 P: n/a JRS: In article , seen in news:comp.lang.javascript, Thomas Mlynarczyk posted at Mon, 16 Feb 2004 21:16:45 :-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 tostart playing. Now I want to be able to get back to the same layout later bysimply selecting "game number 12345", where 12345 will be the seed thatshould always generate the same deck of cards. Currently I shuffle the cardsby selecting two at random and swapping their places. This I do a number oftimes, 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 Jim Ley's FAQ for news:comp.lang.javascript jscr maths, dates, sources. TP/BP/Delphi/jscr/&c, FAQ items, links. Jul 20 '05 #7

 P: n/a In article , Dr John Stockton wrote:JRS: In article , seen innews:comp.lang.javascript, Thomas Mlynarczyk posted at Mon, 16 Feb 2004 21:16:45 :-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 tostart playing. Now I want to be able to get back to the same layout later bysimply selecting "game number 12345", where 12345 will be the seed thatshould always generate the same deck of cards. Currently I shuffle the cardsby selecting two at random and swapping their places. This I do a number oftimes, so more or less all the cards should be randomly displaced. Your shuffling is, therefore, very probably not enough to achieve fullrandomness, or more than is necessary to achieve full randomness, ordoes not give equal probability to all possible results (assuming, thatis, a perfect Random function).By reading the FAQ and following its "shuffling" reference, you couldhave 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. -- -john February 28 1997: Last day libraries could order catalogue cards from the Library of Congress. Jul 20 '05 #8

 P: n/a jg*****@ripco.com (John M. Gamble) writes: In article , Dr John Stockton wrote: By reading the FAQ and following its "shuffling" reference, you couldhave 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 -- Lasse Reichstein Nielsen - lr*@hotpop.com DHTML Death Colors: 'Faith without judgement merely degrades the spirit divine.' Jul 20 '05 #9

 P: n/a "Thomas Mlynarczyk" wrote in message news:... 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. This is similar to Freecells game recall method: Game Id Jul 20 '05 #10

 P: n/a 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. Jul 20 '05 #11

 P: n/a 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] = 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[i]; chosenGame[i]=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 Jul 20 '05 #12

 P: n/a JRS: In article <1a**************************@posting.google.com >, seen in news:comp.lang.javascript, Pete 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] = 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[i]; chosenGame[i]=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 . -- © John Stockton, Surrey, UK. ?@merlyn.demon.co.uk Turnpike v4.00 MIME. © TP/BP/Delphi/&c., FAQqy topics & links; RAH Prins : c.l.p.b mFAQ; Timo Salmi's Turbo Pascal FAQ. Jul 20 '05 #13

 P: n/a JRS: In article , seen in news:comp.lang.javascript, John M. Gamble posted at Tue, 17 Feb 2004 20:31:07 :-By reading the FAQ and following its "shuffling" reference, you couldhave 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. Thequestion comes up occasionally in sci.crypt, and also was discussedin detail in the comp.lang.perl.moderated newsgroup. I think thatthe 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 areequally possible. I certainly don't believe that. This may not be the worst problem with acard-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 theFischer-Krause algorithm. PGU. -- © John Stockton, Surrey, UK. ?@merlyn.demon.co.uk Turnpike v4.00 IE 4 © Jim Ley's FAQ for news:comp.lang.javascript jscr maths, dates, sources. TP/BP/Delphi/jscr/&c, FAQ items, links. Jul 20 '05 #14

 P: n/a Dr John Stockton writes: "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 -- Lasse Reichstein Nielsen - lr*@hotpop.com DHTML Death Colors: 'Faith without judgement merely degrades the spirit divine.' Jul 20 '05 #15

 P: n/a JRS: In article , seen in news:comp.lang.javascript, Lasse Reichstein Nielsen posted at Wed, 18 Feb 2004 20:13:54 :-Dr John Stockton writes: "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. :) 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 Stockton, Surrey, UK. ?@merlyn.demon.co.uk Turnpike v4.00 IE 4 © Jim Ley's FAQ for news:comp.lang.javascript jscr maths, dates, sources. TP/BP/Delphi/jscr/&c, FAQ items, links. Jul 20 '05 #16

 P: n/a In article , Lasse Reichstein Nielsen wrote:jg*****@ripco.com (John M. Gamble) writes: In article , Dr John Stockton wrote:By reading the FAQ and following its "shuffling" reference, you couldhave 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 thatthe 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 February 28 1997: Last day libraries could order catalogue cards from the Library of Congress. Jul 20 '05 #17

 P: n/a In article , Dr John Stockton wrote:JRS: In article , seen innews:comp.lang.javascript, John M. Gamble posted atTue, 17 Feb 2004 20:31:07 :-By reading the FAQ and following its "shuffling" reference, you couldhave 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?" Thequestion comes up occasionally in sci.crypt, and also was discussedin detail in the comp.lang.perl.moderated newsgroup. I think thatthe 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 beequivalent 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). The major flaw with this algorithm is that not all permutations areequally possible.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. This may not be the worst problem with acard-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 theFischer-Krause algorithm.PGU. Which stand for? -- -john February 28 1997: Last day libraries could order catalogue cards from the Library of Congress. Jul 20 '05 #18

 P: n/a jg*****@ripco.com (John M. Gamble) writes: 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 -- Lasse Reichstein Nielsen - lr*@hotpop.com DHTML Death Colors: 'Faith without judgement merely degrades the spirit divine.' Jul 20 '05 #19

 P: n/a Lasse Reichstein Nielsen wrote: jg*****@ripco.com (John M. Gamble) writes: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 71999, 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 numbersource is good, but i will wager that Random does not meet sci.crypt'sgeneral 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 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 Jul 20 '05 #20

 P: n/a In article <40********@10.10.0.241>, Brian Genisio wrote:Lasse Reichstein Nielsen wrote: jg*****@ripco.com (John M. Gamble) writes: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 71999, 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 numbersource is good, but i will wager that Random does not meet sci.crypt'sgeneral 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 :). /LTo add a left turn into the conversation, a human, using a typicalshuffle, splitting a deck in two, and joining them, cannot create all52! 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 havemore 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 reallyonly need to have random numbers between 1 and 10, where 1,2,3 are morelikely than 10 (if you are en experienced shuffler). Then, you take agiven deck, split it in half (with a random deviance), and take randomammounts from each side, one side, and then annother.Then, do it one or two more times. This, to me seems more likely to bea good shuffle algorithm for a card game. Oh yeah... dont forget tosplit 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 testbetting techniques over a long period of time. I actually shuffled adeck of cards about 20 times, and tallied up the probabilty of thedifferent card chunks that added together to a single deck. I foundthat numbers such as 2 and 3 were much more common than 1 and 4, where 5and 6 were practically unheard of. I used these stats to generate myshuffle.Ultimately, I scrapped the program, because it didn't deal with the manyfactors that cannot be programmed, such as human emotion around thetable, and bad playing decisions on other player's parts. This threw amix into the final hand that made the my subtle shuffling algorithmpractically useless :)Anyways, that is just a sidenote. Interesting though. Thanks. -- -john February 28 1997: Last day libraries could order catalogue cards from the Library of Congress. Jul 20 '05 #21

 P: n/a In article , Lasse Reichstein Nielsen wrote:jg*****@ripco.com (John M. Gamble) writes: 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, anda 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. -- -john February 28 1997: Last day libraries could order catalogue cards from the Library of Congress. Jul 20 '05 #22

 P: n/a JRS: In article , seen in news:comp.lang.javascript, John M. Gamble posted at Thu, 19 Feb 2004 21:29:45 :-In article ,Dr John Stockton wrote:JRS: In article , seen innews:comp.lang.javascript, John M. Gamble posted atTue, 17 Feb 2004 20:31:07 :-By reading the FAQ and following its "shuffling" reference, you couldhave 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 beequivalent to the above, encoded in C. The major flaw with this algorithm is that not all permutations areequally possible.I certainly don't believe that."Thus, for example, if m = 2**32, certain permutations of 13 elementswill 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. The algorithm (or one of them) that should be looked at is theFischer-Krause algorithm.PGU.Which stand for? The words "Please Give URL" appeared earlier in my previous article ... -- © John Stockton, Surrey, UK. ?@merlyn.demon.co.uk Turnpike v4.00 MIME. © Web - FAQish topics, acronyms, & links. Proper <= 4-line sig. separator as above, a line exactly "-- " (SonOfRFC1036) Do not Mail News to me. Before a reply, quote with ">" or "> " (SonOfRFC1036) Jul 20 '05 #23

 P: n/a JRS: In article , seen in news:comp.lang.javascript, Lasse Reichstein Nielsen posted at Thu, 19 Feb 2004 23:53:54 :- 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 the13! needed. I never thought of that restriction. :)In fact, that restriction holds for any shuffling algorithm using aPRNG 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. ( ) 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, ... -- © John Stockton, Surrey, UK. ?@merlyn.demon.co.uk Turnpike v4.00 MIME. © Web - FAQish topics, acronyms, & links. Proper <= 4-line sig. separator as above, a line exactly "-- " (SonOfRFC1036) Do not Mail News to me. Before a reply, quote with ">" or "> " (SonOfRFC1036) Jul 20 '05 #24

### This discussion thread is closed

Replies have been disabled for this discussion.