At 10:33 AM 8/13/02 -0700, Brendan wrote: > > At 09:27 AM 8/13/02 -0700, Brian wrote: > >Err... Brendan, but yeah. Sorry about that. My email program doesn't automatically supply the name on reply. > > A better method for a PIC in assembler is to use a Hammersley > > sequence: > > > > For each k=1,2,3,... > > > > 1. Express k in binary (e.g., "6" = "1100"). (This is easy on a > > PIC!) 2. Reflect the number to give a binary fraction (e.g., for > > "6" -> "0011"). (This is also easy on a PIC). > > 3. Express the answer as a number x in [0,1]. > > 4. If you want a die roll from 1..6, use 6*x+1 as your value. > > > > Very simple, but it gives equidistribution to O(1/N) and has high > > apparent randomness (i.e., low autocorrelations). > > > > By the way, this sequence of numbers is superior for any purpose to > > any form of pseudorandom numbers. The equidistribution even on > > subsets is asymptotically guaranteed, it gives more accurate > > answers in estimation problems. It also has guaranteed low > > autocorrelations. > >I have got to say that that is the best answer that I have ever heard >about this subject, though I am having some difficulty understanding >your algorithm. > >First, does your algorithm take a random seed? From here, it looks >like it doesn't. Or is a random seed in this case used by forcing a >specific value as a starting point? No. The downside of this sequence is that the index k of each number must be known and maintained. Think of it as equivalent to the "seed". Each time you take a result k->k+1. > > 1. Express k in binary (e.g., "6" = "1100"). (This is easy on a > > PIC!) > >Ok, so use the common dice numbers multiplied by 2? No. ALL numbers on a PIC are in binary. Visual a 4-byte (or 2-byte if you don't need many numbers out of the algorithm) integer as k. It's already stored in binary on the PIC. E.g., k=1 => k=00000001H. > > 2. Reflect the number to give a binary fraction (e.g., for "6" -> > > "0011"). (This is also easy on a PIC). > >Yep So k=1 becomes 10000000H. This is the hard part of the algorithm. > > 3. Express the answer as a number x in [0,1]. > >Meaning express the binary reflection of the each number as >0= >If so, how is this done in assembly, given that there are no >fractions available? You simply place an imaginary binary point at the far left: x = 0.10000000H = 0.5D. > > 4. If you want a die roll from 1..6, use 6*x+1 as your value. > >Is k then the result so that the generator feeds back into itself? >Or would that produce the very autocorrelations that we're attempting >to avoid? No, 6*x+1 is the result. Multiply the 4-byte x fraction by a 1-byte 6 in binary (06H). The top byte is your die roll, and will be a value between 0 and 5. You can increment to add the "1" if you need a number between 0 and 6. You then need to increment k so that the next time it's 1 larger than before. >Given that this algorithm seems not to look at previously selected >numbers, how is equidistribution guaranteed? > >My original thought on the way to handle this was to generate a >random number from 0 to 255, then take all the possible numbers, and >give them catchment zones equaly distributed from 0 to 255. Then, >the system would take the results and store them, and weight the >catchment zones accordingly. Here is a table of the first few values to make the algorithm easier to follow: HAMMERSLEY SEQUENCE FOR RADIX 2 Index Binary Reflection Decimal Die Roll Count 100 Average 3.4 Std Dev 1.71 1 00000001 10000000 0.50000 4 2 00000010 01000000 0.25000 2 3 00000011 11000000 0.75000 5 4 00000100 00100000 0.12500 1 5 00000101 10100000 0.62500 4 6 00000110 01100000 0.37500 3 7 00000111 11100000 0.87500 6 8 00001000 00010000 0.06250 1 9 00001001 10010000 0.56250 4 10 00001010 01010000 0.31250 2 11 00001011 11010000 0.81250 5 12 00001100 00110000 0.18750 2 13 00001101 10110000 0.68750 5 14 00001110 01110000 0.43750 3 15 00001111 11110000 0.93750 6 16 00010000 00001000 0.03125 1 17 00010001 10001000 0.53125 4 18 00010010 01001000 0.28125 2 19 00010011 11001000 0.78125 5 20 00010100 00101000 0.15625 1 If you wish, you can "randomize" the sequence by using a "random" number for the starting index k. ================================================================ Robert A. LaBudde, PhD, PAS, Dpl. ACAFS e-mail: ral@lcfltd.com Least Cost Formulations, Ltd. URL: http://lcfltd.com/ 824 Timberlake Drive Tel: 757-467-0954 Virginia Beach, VA 23464-3239 Fax: 757-467-2947 "Vere scire est per causas scire" ================================================================ -- http://www.piclist.com#nomail Going offline? Don't AutoReply us! email listserv@mitvma.mit.edu with SET PICList DIGEST in the body