/* *********************************************** */ /* Program: shuffle.c */ /* Date: 091425PST Jan 1997 */ /* Name: Alfred A. Aburto Jr. */ /* Email: aburto@nosc.mil, aburto@cts.com */ /* Place: San Diego, CA, USA */ /* */ /* This very simple routine tests a random number */ /* generator using a card shuffling procedure. */ /* */ /* Shuffle.c counts the number of occurrences of */ /* card type (ace, two, three, ..., queen, king) */ /* at position 103 in a stack of cards ( 4 decks */ /* of 52 cards) for 26,000 shuffles. Ideally the */ /* number of cards observed of the same type at */ /* position 103 (or any other position) would be */ /* 26000 / 13 = 2000 assuming the random number */ /* generator provides a uniform distribution. */ /* *********************************************** */ [DEFINED] -work [IF] -work [THEN] MARKER -work \ ************************************ \ Parameters for the mother of random \ number generation programs: Mother() \ ************************************ #65536 =: m16Long \ 2^16 $FFFF =: m16Mask \ mask for lower 16 bits $7FFF =: m15Mask \ mask for lower 15 bits $7FFFFFFF =: m31Mask \ mask for 31 bits 4294967295e FCONSTANT m32Double \ 2^32-1 #3141592 =: kr CREATE mother1 #10 CELLS ALLOT CREATE mother2 #10 CELLS ALLOT 1 VALUE mStart 4 =: NDecks CREATE card #52 NDecks * CELLS ALLOT CREATE suit #14 CELLS ALLOT CREATE cname ( 13 x [1+5] ) ," ACE " ," TWO " ," THREE" ," FOUR " ," FIVE " ," SIX " ," SEVEN" ," EIGHT" ," NINE " ," TEN " ," JACK " ," QUEEN" ," KING " 1 [IF] /* Mother ************************************************************* | George Marsaglia's The mother of all random number generators | producing uniformly distributed pseudo random 32 bit values | with period about 2^250. | The text of Marsaglia's posting is provided in the file mother.txt | | The arrays mother1 and mother2 store carry values in their | first element, and random 16 bit numbers in elements 1 to 8. | These random numbers are moved to elements 2 to 9 and a new | carry and number are generated and placed in elements 0 and 1. | The arrays mother1 and mother2 are filled with random 16 bit | values on first call of Mother by another generator. mStart | is the switch. | | Returns: | A 32 bit random number is obtained by combining the output of the | two generators and returned in *pSeed. It is also scaled by | 2^32-1 and returned as a double between 0 and 1 | | SEED: | The inital value of *pSeed may be any long value | In the Forth version Seed is passed in but not passed out. | | Bob Wheeler 8/8/94 */ -- Here only a double is returned. Seed is not modified. : Mother ( Seed -- ) ( F: -- r ) 0 0 0 0 0 LOCALS| number number1 number2 'p sNumber Seed | mStart /* Initialize motheri with 9 random values the first time */ IF Seed m16Mask AND TO sNumber /* The low 16 bits */ Seed m31Mask AND TO number /* Only want 31 bits */ mother1 TO 'p 1 #18 DO number #16 RSHIFT sNumber #30903 * + DUP TO number m16Mask AND DUP TO sNumber 'p ! =CELL +TO 'p I 9 = IF mother2 TO 'p ENDIF -1 +LOOP /* make carry 15 bits */ mother1 DUP @ m15Mask AND SWAP ! mother2 DUP @ m15Mask AND SWAP ! CLEAR mStart ENDIF /* Move elements 1 to 8 to 2 to 9 */ mother1 CELL+ mother1 2 CELL[] 8 CELLS MOVE mother2 CELL+ mother2 2 CELL[] 8 CELLS MOVE /* Put the carry values in numberi */ mother1 @ TO number1 mother2 @ TO number2 /* Form the linear combinations */ mother1 2 CELL[] @+ #1941 * +TO number1 @+ #1860 * +TO number1 @+ #1812 * +TO number1 @+ #1776 * +TO number1 @+ #1492 * +TO number1 @+ #1215 * +TO number1 @+ #1066 * +TO number1 @ #12013 * +TO number1 mother2 2 CELL[] @+ #1111 * +TO number2 @+ #2222 * +TO number2 @+ #3333 * +TO number2 @+ #4444 * +TO number2 @+ #5555 * +TO number2 @+ #6666 * +TO number2 @+ #7777 * +TO number2 @ #9272 * +TO number2 /* Save the high bits of numberi as the new carry */ number1 m16Long / mother1 ! number2 m16Long / mother2 ! /* Put the low bits of numberi into motheri[1] */ /* Combine the two 16 bit random numbers into one 32 bit */ number1 m16Mask AND DUP mother1 CELL+ ! ( mother1[1] ) #16 LSHIFT number2 m16Mask AND DUP mother2 CELL+ ! ( mother2[1] ) OR ( Seed ) /* Return a double value between 0 and 1 */ U>D D>F m32Double F/ ; [ELSE] : Mother ( Seed -- ) ( F: -- r ) DROP FRANDOM ; [THEN] : SHUFFLE ( -- ) 1e 0e 0e FLOCALS| r x scale | /* ********************************** */ /* If you want to test rand() you */ /* will need to set the value of */ /* scale as follows: */ /* scale = 1.0 / (double)RAND_MAX; */ /* */ /* For Mother() however scale = 1.0; */ /* ********************************** */ 52 NDecks * ( j ) DUP S>F scale F* TO r #10 * ( k ) 1+ 1 DO kr Mother r F* F>S ( m ) kr Mother r F* F>S ( m n ) DUP card []CELL @ ( m n l ) >R OVER card []CELL @ SWAP card []CELL ! ( m ) R> SWAP card []CELL ! LOOP ; : MAIN ( -- ) 0 0 0 0 LOCALS| jj ICard NCards NShuf | 0e 0e 0e FLOCALS| x y z | PRECISION >R 1 SET-PRECISION /* #################### */ /* # Initialization # */ /* #################### */ #52 NDecks * TO NCards #26000 TO NShuf #103 TO ICard #14 0 DO 0 suit I CELL[] ! LOOP CR ." SHUFFLE: Test of Random Number Generator." CR ." Counts number of occurrences of card type at position " ICard DEC. CR ." in card deck for " NShuf DEC. ." shuffles. Ideal would be " NShuf #13 / DEC. CR ." occurrences for each type of card." CR ." Card Number Percent CR ." value observed from ideal" /* **************************** */ /* Preset the NDecks of cards. */ /* 1 is Ace */ /* 11 is Jack */ /* 12 is Queen */ /* 13 is King */ /* We ignore the suit... */ /* **************************** */ TIMER-RESET NDecks 0 DO I #52 * ( n ) 4 0 DO I #13 * OVER + ( n m ) #14 1 DO I I 2 PICK ( n m i i m ) + 1- card []CELL ! LOOP DROP ( n ) LOOP DROP ( -- ) LOOP /* ******************************* */ /* Pre-shuffle the NDecks of cards */ /* ******************************* */ SHUFFLE NShuf 1+ 1 DO SHUFFLE 1 card ICard CELL[] @ ( j ) suit []CELL +! LOOP 0 TO jj 13e NShuf S>F F/ TO y #14 1 DO suit I CELL[] @ ( k ) DUP +TO jj DUP S>F y F* F1- 100e F* TO x CR I 1- 6 * cname + 1+ 5 TYPE 3 SPACES 5 .R 4 SPACES x 6 F.R LOOP MS? CR ." Total Cards = " jj DEC. CR ." Elapsed Time (sec): " .KB R> SET-PRECISION ; DOC (* <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<( shuffle )>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> System OS CPU/FPU CPU Run Time REF (MHz) (seconds) ### ---------------------- -------------- ----------- ----- --------- --- ------------------------------------------------------------------------- AMD running iForth W2K Athlon 900 70.28 ------------------------------------------------------------------------- 001 SGI Origin 200 Irix 6.4 MIPS R10000 180 96.96 14 002 SGI Origin 200 Irix 6.4 MIPS R10000 180 102.91 7 003 SGI O2 Irix 6.3 MIPS R10000 175 136.69 4 004 SGI O2 Irix 6.3 MIPS R10000 175 160.22 4 005 Sun UltraSPARC-2 Solaris 2.5.1 UltraSPARC 300 168.41 14 006 AMD K6 Windows 95 AMD K6 200 173.13 13 007 Pentium Pro Windows 95 Pentium Pro 200 193.55 12 008 PC Clone Windows NT 4.0 AMD K5PR133 100 215.20 3 009 PC Clone Windows 95 AMD K5PR133 100 216.52 3 010 SGI Challenge S Irix 6.2 MIPS R4400 200 230.09 5 011 Pentium P5-166 Windows 95 Pentium 166 240.95 6 012 PC Clone SCO V5.0.2c AMD K5PR133 100 252.57 3 013 Dell XPS Pro 200n NT 3.51 Pentium Pro 200 252.85 2 014 SGI Indy Irix 6.2 MIPS R5000 150 261.23 7 015 IBM RS/6000 25E AIX 3.2.5 PPC601 66 264.87 11 016 Sun UltraSPARC-1 SunOS 5.5.1 UltraSPARC 143 314.08 1 017 HP 9000/J210XC HP-UX 10.20 PA7200_2CPU 120 329.82 10 018 Dell XPS Pr200n No opt NT 3.51 Pentium Pro 200 347.65 2 019 SGI Onyx Irix 6.2 MIPS R8000 75 366.55 8 020 Brett Station ATX Linux 2.0.0 Pentium Pro 180 393.02 9 021 Sun SPARCstation 20/HS SunOS 5.5 HyperSPARC 100 404.88 1 022 IBM RS/6000 25E AIX 3.2.5 PPC601 66 417.35 11 023 HP 9000/712 HP-UX 10.20 HP-PA7100LC 100 443.06 10 024 Sun SPARCstation 20/61 SunOS 5.5 SuperSPARC 60 472.07 1 025 PC Clone Linux 3.0.3 AMD K5PR133 100 474.63 3 026 Escom P100 Win95/DOS Pentium 100 478.78 2 ------------------------------------------------------------------------- P54C running iForth NT 4.0 Pentium 166 506.58 ------------------------------------------------------------------------- 027 PC Clone MS DOS 6.22 Am5x86-P75 133 559.84 1 028 Pentium P5-90 MS DOS 6.22 Pentium P5 90 578.63 1 029 Pentium P5-90 MS DOS 6.22 Pentium P5 90 580.44 1 030 Escom P100 No opt Win95/DOS Pentium 100 617.97 2 031 SPARCserver 690MP SunOS 4.1.3 SuperSPARC 50 832.23 1 032 Escom 486 Win95/DOS 80486DX2 66 1375.83 2 033 Escom 486 No opt Win95/DOS 80486DX2 66 1708.36 2 --- ### ---------------------------------------------------------------------- *) ENDDOC /* ---------- End of shuffle.c, Say goodnight Carrie ---------- */