code for random numbers

Peter Rand

How do I code the Basic Stamp to generate random numbers, but only from 1 to 10, or 1 to 100?

Phil Pilgrim (PhiPi)

These two subroutines should do what you want:

randw VAR Word  'Seed and result for RANDOM.
randb VAR Byte  'Returned result.

Random1to10:

  DO
    RANDOM randw
  UNTIL randw < 65530
  randb = randw // 10 + 1
  RETURN

Random1to100:

  DO
    RANDOM randw
  UNTIL randw < 65500
  randb = randw // 100 + 1
  RETURN

The DO loops remove any bias due to the fact that 65536 is not divisible by either 10 or 100.

-Phil

Post Edited (Phil Pilgrim (PhiPi)) : 9/6/2007 11:40:10 PM GMT

Peter Rand

Many thanks Phil

Sassy

Hello All,

While we are on this subject I was wondering how many random numbers may be selected and and not selected again until all numbers have been picked. I have seen Jon Williams uMP3 Player that has a number of sixteen. I would like to use that concept to play as many random songs as possible....So what would be the maximum number? and How would you write code to accomplish this?

Sassy

cyplesma

I don't know what the limits of the stamp are on this, but.....


if there is a limit (I would have to imagine it would be the binary equivilant to a word variable, 65535?), but you could do some fancy multiplication to get numbers higher then the 16.

Ol' Geo

The BASIC Stamp manual says the pseudo-random numbers is ranging from 0 to 65535. Try to use the manual as your friend.

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
Ol' Geo
Retired Software Engineer

An oscilloscope is a window of unseen electronic world. - GM

TechnoRobbo

Sassy

The Random command will not produce a zero without a modulus operator. Therefore; the help file is half right and half wrong. It does have 65535 numbers in the sequence it generates without repeats, not the 65536 numbers it needs to do the 0 to 65535 that it claims.

To be more specific, a seed of 0 will yield a Result of 64992 as will a seed of 128.

Would this be considered a bug? Personally I think it's a just quirk. If I were Parallax, I'd just correct the help file entry.

So, I leave you all with this advice - if you want all numbers considered in your code, always use a modulo (//) operator.

Sassy - I hope this is what you meant.

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
Have Fun


TR

Post Edited (TechnoRobbo) : 9/9/2007 5:12:29 AM GMT

Sassy

Thank You all,

TechnoRobbo, I have played around with this random number and playing selected Songs from a uMP3 Player and I have had a problem with after playing the selected Song the Song comes up again,within a few songs.

··DO
····RANDOM·randw
··UNTIL·randw·<·65500
··randb·=·randw·//·300·+·1····· ' 1-300 Songs
· randb = song
· serout uMP3,t9600,[noparse][[/noparse]dec song]
· Gosub·Wait························· 'Check for Song Completed
··RETURN

I do not know, maybe I am reseeding the random number code and having this problem

TechnoRobbo

Sassy said...

··DO
····RANDOM·randw
··UNTIL·randw·<·65500
··randb·=·randw·//·300·+·1····· ' 1-300 Songs

· randb = song
· serout uMP3,t9600,[noparse][[/noparse]dec song]
· Gosub·Wait························· 'Check for Song Completed
··RETURN

I do not know, maybe I am reseeding the random number code and having this problem

Sassy,
Any Pseudo-Random Number Generation Algorithm (as the one used by the RANDOM command ) repeats! It's the nature of math to be repeatable. Add to that a MOD command like "//300? and it will repeat 300 times more. So every 65535 iterations, instead of repeating once,there will be 218 repetitons of every number. Here are the 1st 15 repetitions of the #1.


In order to do what you want you will have to keep a log somewhere on (or off) the stamp for 300 songs.· If you use "bits" to keep track the songs played, you would need 38 bytes. The DS1302 would give you 31 bytes (248 songs) and the other 6 bytes can go on the stamp. You can also use the clock on the· DS1302 to generate a truly random seeding for the RANDOM command.
I caution using the EEPROM for storage 'cause you'll wear it out like a bad pair of shoes. EEPROMS can only take so many "writes" 'til you can write no more. How 'bout that for planned obsolecense?






▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
Have Fun


TR

Post Edited (TechnoRobbo) : 9/8/2007 6:56:52 PM GMT

Phil Pilgrim (PhiPi)

Sassy,

There are two kinds of "sampling" involved here: sampling with replacement and sampling without replacement. The random number generator presented samples with replacement. It's like taking a pack of playing cards, picking one at random, sticking it back in the deck, picking another, etc. Eventually you will pick a card that's already been picked before having seen all the cards in the deck. In sampling without replacement, once you pick a card, you discard it. Therefore you never see the same card twice.

There's a way to do what you want using RANDOM that takes advantage of the fact that all 65535 numbers get cycled through before repeating. It involves selecting a block of n consecutive numbers from the range 1 to 65535, then calling RANDOM until all of those n numbers have been returned. Then pick a different block, and repeat.

Here's the code:

' {$STAMP BS2}
' {$PBASIC 2.5}

n     CON 10

randw VAR Word
randb VAR Byte
block VAR Byte
i     VAR Byte

FOR block = 1 TO 20
  FOR i = 1 TO n
    GOSUB Pick1ofn
    DEBUG DEC randb
    IF i < n THEN DEBUG "," ELSE DEBUG CR
  NEXT
NEXT

Pick1ofn:

  DO
    RANDOM randw
  LOOP UNTIL randw >= block * n AND randw < (block + 1) * n
  randb = randw // n + 1
  RETURN

The main disadvantage of this method is that it's really sloowww. But in your application, that may not matter. While one song is playing, you have plenty of time to pick the next one.

-Phil

Post Edited (Phil Pilgrim (PhiPi)) : 9/8/2007 4:51:39 PM GMT

Tracy Allen

In these routines, I think it is usually best to keep the random variable as a word and not restrict it with the // operator. I.e.,

DO
  RANDOM randb
  randb = randw // n + 1
  DEBUG ? randb
LOOP

restricts the range of randb to 1 to n+1, so when a new random number is chosen it comes from that restricted set of n and will not cycle thrrough all 65535 values. Better to split off into a second variable and leave random to fall where it may in its full range.

DO
  RANDOM randb     
  x = randw // n + 1
  DEBUG ? x   ' larger assortment of sequences
LOOP

For the purpose of shuffling songs, the sequence would not have to be too fancy. Suppose you have 307 songs. That is a prime number. Pick any number N less than 307 and pick a starting point, song #M. Play song #M, then move to song number M = M+N // 307. Then continue adding N mod That will play all 307 songs without repetition. The next time, pick a different N and M to start. You can use a number of songs that is not prime, say 301, but then you can't choose an N that shares a factor, the prime factors being 7*43=301.

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
Tracy Allen
www.emesystems.com

Phil Pilgrim (PhiPi)

Tracy,

I used randw as the seed, not randb. I do like your shuffling method, though.

-Phil

TechnoRobbo

Tracy's·algorithm·offers a great alternative to the RANDOM command since it will give you 306 possible Psuedo Random play list derangements (mathematical term -·not a medical one)·. The key in all this is that·your are·using·a subset to a large repeating pattern and the more you can obscure this fact the better. That's where Modulo and prime numbers come into play, but·above all, generating a decent seed is the key·to the illusion.

The help file does have a great "example" program complete with a circuit schematic that will show you how to use the best Random Number Generator of them all - the human finger.

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
Have Fun


TR

Post Edited (TechnoRobbo) : 9/8/2007 9:25:12 PM GMT

Tracy Allen

Oh, sorry, I misread the w and the b. That makes a big difference. The trick with blocks is very clever.

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
Tracy Allen
www.emesystems.com

Phil Pilgrim (PhiPi)

This thread does bring up an interesting question: Is it possible to generate a random permutation from a set of sequential integers using a processor that's too small to enumerate the entire set, even as a sequence of bits? By "random", I mean that each possible permutation has an equal probability of being generated, given a pseudorandom number generator like RANDOM.

-Phil

TechnoRobbo

Phil,

Without some kind of white noise generator or external input? I believe not. The precise clock is what makes sequential processes possible in the first place. (Wow that's alot of P's in that sentence.)·With out rigid predictability this type of technology would not exist.

·

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
Have Fun


TR

Phil Pilgrim (PhiPi)

TR,

No, I didn't mean truly random, which would require external input. I meant pseudo-random, with the proviso that all the permutations be equally probable, but where n bits of RAM (where n is the size of the set) are not available for bookkeeping.

In other words, pick a seed (or several for large sets) using RANDOM, and use that to generate the output sequence. But every possible sequence has to be accessible by this generator, each with the same frequency of occurence.

For example, the set {1,2,3} has 3! = 6 permutations:

····123
····213
····231
····321
····312
····132

What I'm after is a generator that will generate one or more of these at random, such that each has the same probability of being output.

-Phil

Post Edited (Phil Pilgrim (PhiPi)) : 9/8/2007 9:25:05 PM GMT

TechnoRobbo

It would definitely be a firmware mod. Perhaps output a clock timing like Microsoft does. I'd add that to your wishlist for Parallax. It would make sense for encryption and other security applications.

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
Have Fun


TR

Phil Pilgrim (PhiPi)

I see now that this will not be possible, given the constraints I've posited. Any seed that can generate all n! unique permutations would have to be at least log₂(n!) bits long. For n>3, that's more bits than are required to maintain a "numbers remaining" bit array.

But that leads down yet another path: any pseudo-random permutation generator has to use a random number generator with a seed of the aforementioned size. For example, to generate equiprobable permutations of 64 elements, you'd need a seed with log₂(64!) = 296 bits and a RANDOM function that uses it! This really calls into question most all the published permutation generators that seem tacitly to assume that the root pseudo-random number generator will not repeat for n! iterations.

-Phil

cyplesma

you could always limit the number of cards you keep out of the deck.


so you have say 25 cards in your discard (no repeat) pile. When you pick the 26th card you use it to replace the oldest card in the discard pile, which basically puts that card back in the deck.

I don't see the ability to do arrays with pbasic. Is the best way to deal with arrays is to use the eeprom (data) section?

Ol' Geo

No need to use EEPROM for flag storage. You only need 2 bytes for storage. Here is how:

Add 4 jokers to the playing cards, you got 56 cards in total. Divide the deck into 7 groups of 8 cards. Randomly select a group and then randomly select a card from that group. Hence, you have only 15 bits for flags, 7 for the groups and 8 for the cards. Whenever the group is exhausted, reset the card flags for the next group. If it is a joker, simply discard it.

Hope you get the draft.

PS For the guy who wants 300 or more songs to select, he needs only 3 bytes for the flag storage! Hint: 5 x 8 x 8 = 320 songs and 21 flag bits.

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
Ol' Geo
Retired Software Engineer

An oscilloscope is a window of unseen electronic world. - GM

Phil Pilgrim (PhiPi)

Ol' Geo,

You seem to be saying that, once you pick a group, you have to select all the cards in that group before moving on to the next group. Correct?

-Phil

Ol' Geo

That is correct. This is just an idea how to select a card or song from MCU with very limited storage. Of course, it is not an ideal algorithm but it guarantees no repeats in selection.

There is another algorithm I developed many years ago (around 1972). I need time to recall how I did.

Geo

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
Ol' Geo
Retired Software Engineer

An oscilloscope is a window of unseen electronic world. - GM

TechnoRobbo

Ol' Geo said...
·Whenever the group is exhausted, reset the card flags for the next group. If it is a joker, simply discard it.

Unless I misunderstood,this skews the results in groups - given 300 songs and human memory you could perceive repetition where its not.


And for anyone who is interested in a hardware random generator I've attach a circuit and program I've been playing with - it's pretty wild and random. I think it works with the heat sensitivity of an LED - I started with regular diodes and found the red LED to be more erratic. Circuit is in the program.

Update:

Program was reposted with newer subroutine - shecmatic appears inlater post

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
Have Fun


TR

Post Edited (TechnoRobbo) : 9/10/2007 2:28:49 AM GMT

Phil Pilgrim (PhiPi)

This is proving to be an interesting thread!

I did a web search for random permutation algorithms, and came across the Fischer-Yates Shuffle. There's a so-called "modern" version, popularized by Donald Knuth in his Art of Computer Programming (Vol. 2) that seemed like it might work with a BASIC Stamp. The algorithm, as given, requires an array of elements that get shuffled in place by a strategic sequence of random swaps. This may seem to rule out using a BASIC Stamp, since it doesn't have the RAM for that sort of thing. But I realized that if you invert your thinking and consider only one element at a time, you don't really need the array, or even a bit array for bookkeeping.

Starting with the sequence (1,2,3,...,n), for each element, we can ask, "What position does it end up in after the shuffle?" For example, if (1,2,3) gets permuted to (3,1,2), the "1" ends up in position 2; the "2", in position 3; and the "3" in position 1. But there's another way of looking at what the final sequence might represent. Rather than each value at a certain index representing an element from the original set {1,2,3} positioned at that index, suppose its index in the permuted array represents the value from the initial array (1,2,3). So [noparse][[/noparse]3,1,2] in index space would mean that the first element in the permuted array is "2" (1 ends up in the second position in index space); the second element, a "3" (2 ends up in the third position in index space); and the third element, a "1" (3 ends up in the first position in index space). So this would be equavalent to (2,3,1) in value space.

Now each sequence of the form [noparse][[/noparse]a,b,c,...] has one and only one corresponding sequence of the form (x,y,z...). So generating a sequence [noparse][[/noparse]a,b,c,...] at random is equivalent to generating a sequence (x,y,z...) at random. To demonstrate, here's an enumeration of the permutations of [noparse][[/noparse]1,2,3] in index space and their equivalents in value space:

····[noparse][[/noparse]1,2,3] = (1,2,3) First position is 1, second position is 2, and third position is 3.
····[noparse][[/noparse]1,3,2] = (1,3,2) First position is 1, second position is 3, and third position is 2.
····[noparse][[/noparse]3,1,2] = (2,3,1) First position is 2, second position is 3, and third position is 1.
····[noparse][[/noparse]3,2,1] = (3,2,1) First position is 3, second position is 2, and third position is 1.
····[noparse][[/noparse]2,3,1] = (3,1,2) First position is 3, second position is 1, and third position is 2.
····[noparse][[/noparse]2,1,3] = (2,1,3) First position is 2, second position is 1, and third position is 3.

So, for any position in the final permutation, we can shuffle an element representing that position to see where it ends up. If the index for the first position, say, ends up in position 7 in index space, we'll say that the first position in value space is a "7". That way we can permute each index one at a time to see where it ends up, thus selecting the value for that position. The permutations are performed by random swapping, per the Knuth alogorithm. But since we're only interested in where a single value ends up, for each index, we just track it and ignore where the other indices end up, since each one will get its turn. That way we don't need to keep the whole array around. But each time we move to the next index, we reset the RANDOM seed to its original value, so we get the same shuffle. Then, once we're done, we can go to a new random seed for the next permutaiton.

Here's the program:

' =========================================================================
'
'   File...... randpermute.bs2
'   Purpose... Generate random permutations of the numbers 1 through n.
'   Author.... Phil Pilgrim
'   Started... 2007.09.09
'
'   {$STAMP BS2}
'   {$PBASIC 2.5}
'
' =========================================================================

' -----[noparse][[/noparse] Program Description ]---------------------------------------------

' This program continuously generates random permutations (shuffles) of the
' numbers 1 through n, using a modified version of the algorithm
' popularized by Donald Knuth in The Art of Computer Programming, Vol 2.

' -----[noparse][[/noparse] Constants ]-------------------------------------------------------

n     CON 10        'The number of items in the set to shuffle.

' -----[noparse][[/noparse] Variables ]-------------------------------------------------------

index VAR Byte      'Declare as Word if n > 255.
i     VAR Byte      'Declare as Word if n > 255.
rand  VAR Byte      'Declare as Word if n > 255.
pos   VAR Byte      'Declare as Word if n > 255.

seed  VAR Word      'Seed for RANDOM
seed0 VAR Word      'Saved value of seed.
limit VAR Word      'Used to unbias modulo operator on seed.

' -----[noparse][[/noparse] Program Code ]----------------------------------------------------

DO
  RANDOM seed0                 'Randomize the initial seed.
  FOR index = 1 TO n           'Run index through all the indices.
    seed = seed0               'Reset seed to seed0.
    pos = index                'Initialize current position to current index.
    FOR i = n TO 1             'n possible swaps...
      GOSUB Rand1toi           'Pick a potential position to swap with i.
      IF (pos = i) THEN        'Is current position equal to i?
        pos = rand             '  Yes: Swap it with the random position.
      ELSEIF (pos = rand) THEN '  No:  Is current position equal to random position?
        pos = i                '         Yes: Swap it with i.
      ENDIF                    'Note: If rand = i the swap is moot.
    NEXT
    DEBUG DEC pos              'Display the new position.
    IF (index = n) THEN DEBUG CR ELSE DEBUG ","
  NEXT
LOOP

' -----[noparse][[/noparse] Subroutines ]-----------------------------------------------------

' Rand1toi: Return a random number between 1 and i in the variable rand.

Rand1toi:
  limit = 65535 - (65535 // i)  'Set limit to remove modulo bias.
  DO
    RANDOM seed                 'Get new random seed.
  LOOP UNTIL seed <= limit      'Make sure it's less than or equal to limit.
                                'Note: <=, since seed is always > 0.
  rand = seed // i + 1          'Return modulo + 1.
  RETURN

Of course, the number of actual permutations that can be generated is limited by the size of the random seed (2¹⁶ - 1). But after 65535 different shuffles, who's going to recognize that the songs in shuffle number 65536 come out in the same order as those in shuffle number one?

-Phil

TechnoRobbo

Phi,

Nice Job! It's like a morphing "bubble sort". It appears complex on the surface but it's simplicity is brilliant.

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
Have Fun


TR

Ol' Geo

TechnoRobbo said...

Unless I misunderstood,this skews the results in groups - given 300 songs and human memory you could perceive repetition where its not.

With the algorithm without bookkeeping, it is possible to repeat the same song heard after a few songs back.

Anyway, I remember how I did develop cyclic psuedo-random number generator in 1972. I used 8-bit shift register to generate white noise. I remember it produced exactly 256 non-repetitive numbers in a single cyclic sequence. But I don't remember which bits to feedback the shifting register. For ref, see wiki site at:
en.wikipedia.org/wiki/Linear_feedback_shift_register

Since I am still new to BASIC Stamp, wonder if someone would like to implement LFSR algorithm in BASIC Stamp. I am Delphi/C# guy, BTW.

8-bit shifting register would produce 256 different songs. This algorithm do not require any bookkeeping save the shifting register.

Have fun!

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
Ol' Geo
Retired Software Engineer

An oscilloscope is a window of unseen electronic world. - GM

TechnoRobbo

I polished up the code for the Hardware Random Generator and created a subroutine that can be used in any program. It draws out·4 lowest nibbles from the result and compiles a 16 bit random number.

'subroutines

---

Get_Rnd:
FOR x = 0 TO 3·························· '4 Nibbles for max randomness
··· HIGH cap
··· PAUSE 1····························· '·· for 1 ms
··· RCTIME cap, 1, result··············· ' measure RC discharge time
··· Rand16.LOWNIB(x)=result.LOWNIB
NEXT
RETURN

I've graphed the result and analyzed it over and over - it appears to be purely random, no harmonic. Maybe I'll have it pick my lottery numbers.



▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
Have Fun


TR

Post Edited (TechnoRobbo) : 9/10/2007 2:52:45 AM GMT

Tracy Allen

The Stamp code for the LFSR is pretty simple. This is one I used for a 15 bit sequence:

y VAR Word
randomBit VAR y.bit0
taps:    ' maintains psuedo-random variable y, good source for y.bit0
   y=(y<<1)|(y.BIT15^y.BIT13^y.BIT4^1)
RETURN

If you run this and display the values of y scrolling down the screen, you can clearly see the bits marching to the left. While a good source of random y.bit0, it is not so good for nibs, bytes or words. It would be okay though for a song randomizer.

All this is very interesting, with the shuffling algorithm Phil came up with and the LED circuit. I'm stlll wondering why that particular red LED would randomize the RCTTIME. Is is perhaps acting as a photodiode responsive to light variations? Some kind of heat slushing around?

Several of my son's friends work for Pandora, an internet radio service. They provide a customized play list that is built on a kind of genome of music--the premise being if you tell us a couple of things you like, then, there is a high probablity you will like similar play list drawn from a enormous data base of music that has been dissected and analyzed in many dimensions. Quite an algorithm.

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
Tracy Allen
www.emesystems.com

TechnoRobbo

Tracy,

I did base the circuit on the fact that you could use a diode as a temp sensor. The experiment was based on a Maxim apps note where they used a temp sensing chip for such a purpose (RNG). Regular diodes responded to the touch of my finger or my breath. The LED did not (atleast to the extent that I could detect it)·and I covered it up to block all light and it still yielded plenty of variance - much more than the other diodes.· I assumed that the heat from it's light is being trapped by its plastic coating and the same coating acted as an insulator from outside stimuli. As for why Red? I assumed that it's because of the forward voltage being greater than the regular diode. But still, your guess is as good as mine.

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
Have Fun


TR

TechnoRobbo

Tracy,

I think I have a clue as too why RED LED's works - an Infrared LED also works , both are probably made from gallium arsenide. Some red LED are not made with this substance and I'm not sure if they will work. The key to spotting the right LED might be in the voltage drop. The red ones I used were 1.72v and 1.68 and the infrared is 1.11v. The Yellow and Green LED that did not work were greater than 1.8v. Not exactly the scientific method, I know, but that may be the telling characteristic.

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
Have Fun


TR

Post Edited (TechnoRobbo) : 9/11/2007 1:22:04 AM GMT