Random Number between 1-100

Bits · 2011-12-18 08:07

Does anyone have a random number function that fills an array with numbers that range between 0-100 without reusing the numbers? I want to make a math game and wanted to check first.

Kye · 2011-12-18 08:27

http://obex.parallax.com/objects/627/

Bits · 2011-12-18 08:32

Nice object Kye but its not going to work unless I am mistaken. I need a real random number that fills and array and wont repeat. So if 9 was picked as number 3 then 9 can no longer be used in the array and 3 is filled.

John Abshier · 2011-12-18 08:39

From http://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle

To shuffle an array a of n elements (indices 0..n-1):
for i from n − 1 downto 1 do
j ← random integer with 0 ≤ j ≤ i
exchange a[j] and a

John Abshier

Kye · 2011-12-18 08:52

Oh, i see...

You'll need to do some post processing on the output of the function then.

Jorge P · 2011-12-18 08:53

If John's method don't work for you...

If you have an empty list, you will need to add the generated number to the list, only if it is not already in the list, if it is, just run the generator and try again, repeat. There is a possibility when nearing the end of the list for the generator to not select the desired number for quite some time. I've done it that way for other languages but not for spin. If you want to download some non spin source for the method I used you can get it from http://moekeno.sourceforge.net/ but you will need Game Maker 7 or greater from www.YoYoGames.com, free versions available.

I used that to generate keno ball picks and it took me quite a while to figure it out so I hope the code can be useful even if it is not spin/pasm.

Edit: Thought I'd add the actual section where I did that in the following code since there are a bunch of scripts in my code that you probably wouldn't want.

do
        {
            var tmp;
            // store a random number between 1 and 80
            tmp = round(random(79)) + 1;
            // add the number to the list ONLY if it is NOT
            // akready there
            while(ds_list_find_index(myList, tmp) < 0)
            {
                ds_list_add(myList, tmp);
            } // end while
        }

Edit again: I forgot the until section after do

until(ds_list_size(myList) = 20) // keep going till we have 20 numbers

Duane C. Johnson · 2011-12-18 10:30

Hi Bits;

BTW, I assume you meant an array of 0 to 99 and not 0 to 100.

I don't have the code but if I explain the process it should
be clear as to how to do it.

1. Initialize an index variable pointing to the end of the array.
2. Pre load the array with sequential integers. (0, 1 ,2 ... 97, 98, 99)
3. Using an integer RND function that outputs a number
from 0 to the index which points to an element in the array
between positions 0 and the index position.
4. Swap the contents in the positions.
5. Decrement the index
6. if index = 0 then quit
7. go to 3

Since the contents of the array starts out with unique values
the resultant array will still contain unique values.
This routine just mixes them up.

Duane

Phil Pilgrim (PhiPi) · 2011-12-18 10:35

Here's a program that will do what you want:

CON

  _clkmode      = xtal1 + pll16x
  _xinfreq      = 5_000_000

  RANGE         = 25            'Range is 0 to RANGE.
  SAMPLES       = 10            'Number of samples to pick: 1 to RANGE + 1

VAR

  long  seed
  byte  numbers[RANGE + 1]

OBJ

  pst   : "Parallax Serial Terminal"

PUB start | i

  pst.start(9600)
  fill_array
  pst.str(string("Samples:   "))
  repeat i from 0 to RANGE
    pst.dec(numbers[i])
    if (i == SAMPLES - 1)
      pst.str(string(13, "Remainder: "))
    else
      pst.char(" ")

PUB fill_array | i, j, sample

  repeat i from 0 to RANGE                              'Fill numbers array in order.
    numbers[i] := i
  repeat i from 0 to SAMPLES - 1
    j := ||?seed // (RANGE - i + 1) + i                 'Pick a number at random from the remaining choices.
    sample := numbers[j]
    bytemove(@numbers[i + 1], @numbers[i], j - i)       'Shift the values to make room.
    numbers[i] := sample                                'Put the selected number in the newly vacated spot.

It starts by filling an array, in order, with all the numbers in the selected range. This array will be divided by a moving partition. IOW, pick a number at random from the remaining choices in the second half, shift the contents between the next sample position and the spot from which the sample was taken, then write the sample in the newly-vacated position.

-Phil

Bits · 2011-12-18 10:49

Phil
Looks good but I wanted real random number so I included this object

 obj 
rand : "RealRandom"

and changed this line of code

j := ||?seed // (RANGE - i + 1) + i

with this

j := (rand.random >> 1) // (RANGE - i + 1) + i

So far its working ill need to do a lot of testing. Thanks

cessnapilot · 2011-12-18 22:29

Bits, when you want to shuffle hundred things (numbers from 1 to 100, this case) you want to have all permutations of those hundred things with equal chance, do you? However, the number of those permutations is pretty large, is about 9.3x10^157, and a 32-bit random number generator (true or pseudo) has only 4.3x10^9 number of outcomes. I am not sure, but this can be an issue and can make your results heavily biased. A 544-bit generator would be an overkill, I guess, for a game, but for a math game, it might not. Well, I am probably mistaken.

Cheers,
Istvan

Bits · 2011-12-19 06:24

cessnapilot wrote: »

Bits, when you want to shuffle hundred things (numbers from 1 to 100, this case) you want to have all permutations of those hundred things with equal chance, do you? However, the number of those permutations is pretty large, is about 9.3x10^157, and a 32-bit random number generator (true or pseudo) has only 4.3x10^9 number of outcomes. I am not sure, but this can be an issue and can make your results heavily biased. A 544-bit generator would be an overkill, I guess, for a game, but for a math game, it might not. Well, I am probably mistaken.

Cheers,
Istvan

So what you're suggesting is more randomness? How can this be accomplished?

Heater. · 2011-12-19 07:30

Looking at the article it claims:

"What the specific algorithm provides is a way of doing this numerically in an efficient and rigorous manner that, properly done, guarantees an unbiased result."

http://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle

So you should not have a problem with lack of randomness.

cessnapilot · 2011-12-19 09:22

Heater: Please read the last 5 or 6 paragraph of the wiki article you cited.

Bits: If you have to use all the 100 numbers in your game with equal role, then there are random number generator algorithms written in c that can have more than 500 bits internal states easily. (Recode one in SPIN.) On the other hand, a truly random generator does not have a "state", so using one may be ok for your program. You can do it with PASM, as you mentioned, but you can have a truly random generator using a few lines of SPIN code only. See SPIN_TrigPack object how to do this very simply.

If you just draw some numbers from the 100, like cards from a pack, you do not have to shuffle the whole deck. It is enough to draw those numbers using again a truly random generator.

Phil Pilgrim (PhiPi) · 2011-12-19 09:38

cessnapilot wrote:

If you just draw some numbers from the 100, like cards from a pack, you do not have to shuffle the whole deck. It is enough to draw those numbers using again a truly random generator.

That's what the algorithm I provided, as modified by the OP using RealRandom, does. Pursuant to your comment, though, it would have been adequate to fill the array with values just once and to continue drawing from it for each new set of values, since none of the values disappears from the array.

-Phil

Bobb Fwed · 2011-12-19 10:37

I used something like this for shuffling an array in my sorting algorithm tests:

PUB Main

  RND.start
  randAddr := RND.random_ptr

  REPEAT i FROM 0 TO 99
    ar[i] := i + 1 '' should be word to work with current shuffle method

  shuffle (@ar, 100)

PUB shuffle (arrayAddr, arraylength) | i, rd, tmp
'' shuffle the array

  REPEAT i FROM 0 TO constant(arraylength - 1)
    rd := ||long[randAddr] // arraylength                                       ' get a real random value less than arraylength
    tmp := word[arrayAddr][i]                                                   ' swap the two values     (change to long[...] to use a long array)
    word[arrayAddr][i] :=  word[arrayAddr][rd]                                  ' swap the two values     (change to long[...] to use a long array)
    word[arrayAddr][rd] :=  tmp                                                 ' swap the two values     (change to long[...] to use a long array)

Heater. · 2011-12-20 02:54

cessnapilot,

Thanks for pushing me along, that's interesting stuff in the article. So, if I understand correctly everything works fine provided:
1) The Fisher-Yates algorithm is implemented correctly. (Well of course)
2) The input to the algorithm is good, ie. the source of random numbers.

Luckily the Prop has a source of real random numbers, the RealRandom object as mentioned above.

Bits · 2011-12-20 09:26

Phil

If it is okay with you I would like to place your code along with my small addition in the Object Exchange. Please let me know if this is okay with you.

Here is the code - all your code with my addition of chips random number object.

CON
  _clkmode   = xtal1 + pll16x
  _xinfreq      = 5_000_000


  RANGE         = 100          
  SAMPLES     = 101  


VAR


  Long  seed
  Byte  numbers [ RANGE + 1 ]
  
OBJ


  RandomNumb : "RealRandom"
     
PUB start | i


  RandomNumb.start 
  Fill_array  


PUB Fill_array | i, j, sample   


  repeat i from 0 to RANGE                              'Fill numbers array in order.
    numbers[ i ] := i
  repeat i from 0 to SAMPLES - 1
    j := (RandomNumb.random >> 1) // (RANGE - i + 1) + i              
    sample := numbers[ j ]
    bytemove(@numbers[ i + 1 ], @numbers[ i ], j - i)       'Shift the values to make room.
    numbers[ i ] := sample                                'Put the selected number in the newly vacated spot.

Phil Pilgrim (PhiPi) · 2011-12-20 10:11

I don't mind the code going into the exchange, but I think it's premature to do so with the code as-is, since it's not a bona-fide useful object as written. Here's what it needs:

1. A lot more comments.

2. For general use, the array should at least be word-sized.

3. The start method should do the following:

a) Start RealRandom.
b) Seed Spin's pseudo-random generator just once from RealRandom and use the ? operator from there on.
c) Stop RealRandom (if it has a stop method).
d) Initialize the result array just once from a range of values given as arguments low and high, rather than in the fill_array method (see post #14). It will need to do a range check on high - low + 1.

4. The fill_array method should accept an argument for samples instead of using a constant, and do a range check on it. It should also return the address of the array.

As you can see, creating a useful, OBEX-worthy object from working code requires a few more steps.

-Phil

Bits · 2011-12-20 19:02

Phil

I apologize. It was my intention to include all that you listed and more. I just wanted to make sure that I did not step on your toes first and that I had your permission.

Phil Pilgrim (PhiPi) · 2011-12-20 19:10

No problem. Go for it!

-Phil

cessnapilot · 2011-12-20 22:02

Heater: I promised to myself not to mention again in this thread that you can do RealRandom with SPIN code only. Apparently this fact is Taboo on this forum since I never got any reflections. However, hundreds did try and could see that RealRandom with only SPIN works correctly and that is what really matters. Well, I am really sorry for mentioning that again.

Cheers,
Istvan

PS: I do not expect any comments on this Taboo fact this time, too.

potatohead · 2011-12-20 22:30

Well, I'll comment. Do you have a link to the Spin code? Hate to dedicate, or unload - load a COG to get a few random numbers.

cessnapilot · 2011-12-20 23:21

The essence is only 2 lines of SPIN code, like

seed := (?seed) + CNT
seed := (?seed) * CNT

You can find it in the Q_TRNG procedure of the SPIN_Trig_Pack object

http://obex.parallax.com/objects/501/

So, no need for extra COG.

There is a bunch of statistical tests on OBEX to verify RealRandom property of that simple trick

http://obex.parallax.com/objects/624/

Cheers,
Istvan

Phil Pilgrim (PhiPi) · 2011-12-20 23:36

Istvan,

Since it's deterministic, it's not "real random", though, in the sense that the RealRandom object is. Seeding the pseudo-random ? operator from RealRandom virtually guarantees a different outcome every time the program is run.

-Phil

Heater. · 2011-12-21 00:37

A few problems with selecting random numbers from a range come to light here:

In Phil's code I see this:

    j := ||?seed // (RANGE - i + 1) + i     'Pick a number at random from the remaining choices.

In Bob Fwed's code we have:

    rd := ||long[randAddr] // arraylength    ' get a real random value less than arraylength

Thanks to Cessnapilot we learn that using the modulus operator to limit the
range of random numbers gives biased results.

For example, suppose my random number generator returns numbers from 0 to 15
but I want random numbers in the range 0 to 12. I could write

R = someRandomGenerator // 13

Clearly R will be in range 0 to 12 and I'm happy. But wait. What is
happening here?

1) someRandomGenerator produces equal quantities of each number from 0 to 15.
2) By using the modulus operator the generators random numbers 0 to 12 become my
final R values 0 to 12.
3) BUT the random numbers 13 to 15 ALSO get mapped onto a final result of 0 to 2 as
well.

Result is that 0, 1 and 2 are now more likely to be in the final result R than the other values. We have a bias.

This bias will exist when ever the required range does not divide evenly into the generators output range.

The way to remove this bias is:
1) Get a random number from your generator.
2) Mask out all the high order bits leaving only the bits need to cover the required range.
3) If the number is bigger than your range discard it and go back to step 1) else it's a good result to use.

N.B. Step 2) is a modulus operation but we are assuming that our generator produces numbers in a range that is a power of two so there is no bias introduced here.

For a better explanation of this see the section on "Modulo bias" here:

http://http://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle

Heater. · 2011-12-21 00:45

By the way Bits, why not use the "modern algorithm" as shown in that wiki article? Which looks like this is pseudo code:

    'To shuffle an array a of n elements (indices 0..n-1):
    for i from n &#8722; 1 downto 1 do
        j &#8592; random integer with 0 &#8804; j &#8804; i
        exchange a[j] and a[i]

It's simpler and does not need all that byte moving business.

cessnapilot · 2011-12-21 01:01

Phil,

Try the SPIN_TrigPack object. It starts with the demonstration of a different random sequence using RealRandom SPIN code only. Every time you start the SPIN code, it will produce a different random sequence for you. Have a look at that al least twice. Before submitting the object I made a several days long test to check that. So, SPIN code itself actually guarantees a different outcome every time the program is run. I have no explanation for this real random behavior of SPIN driven Propeller, though.

Cheers,
Istvan

Heater. · 2011-12-21 01:25

cessnapilot,

Heater: I promised to myself not to mention again in this thread that you can do RealRandom with SPIN code only. Apparently this fact is Taboo on this forum since I never got any reflections. However, hundreds did try and could see that RealRandom with only SPIN works correctly and that is what really matters. Well, I am really sorry for mentioning that again.

I had no idea what you were talking about but your last post makes it all clear.

I have not tried your random technique yet but if it works as advertised this is really shocking and distressing news. Perhaps you had no replies to the suggestion when you made it as everyone was dumbfounded, their minds unable to grasp the magnitude of the situation.

Our beloved Propeller is renowned for it's deterministic behavior and here you are pointing out this seriously non-deterministic phenomena. Clearly this information should be suppressed, any such objects removed from OBEX, any mention of it here deleted, you and your family should be banned from the forum and outcast to a remote prison island with no internet connection. The deterministic integrity of the Propeller must be preserved.:)

On the other hand, this might be damn useful...

Heater. · 2011-12-21 01:31

cessnapilot,

SPIN code itself actually guarantees a different outcome every time the program is run. I have no explanation for this real random behavior of SPIN driven Propeller, though.

I have to try this for myself eventually but perhaps you could elaborate "on every time the program is run". Does this imply:
1) Every run is from a power up
2) Every run is from a reset whilst powered up
3) Every run is from a download
4) Every run is "every run" no matter what?

Seems to me that if a "run" is from reset whilst powered up then the clock (CNT) is not being reset so it has random values depending on when the reset occurs hence your result.

But what about from power up? I might expect the clock to always start from zero on power up and then the program will always be in synch with the clock and the randomness disappears.

cessnapilot · 2011-12-21 05:14

Heater,

From power up, or from any other reboot SPIN only code yields RealRandom sequencies. Please try it to see it with your eyes.

kuroneko · 2011-12-21 05:32

FWIW, cnt is important as is its alignment to the hub window for the cog which runs the test. I just ran 3 tests with hub alignment 16n+1, before the test I placed a waitcnt(0). All tests had the same result, I had my wife pick two numbers, sequence number (77) and test (4, Chi-squared) which also came up with the same value.

Random Number between 1-100

Comments