Random values within a large range.

[mkstevo]

I'm trying to generate a random value for an MP3 mini jukebox. The maximum number of tracks I can have on my uSD card is 9,999 so I'd like to generate a random value that has an equal probability of creating any and all of the numbers that fall between 1 and 9999.

The value of MaxTracks is earlier set to the actual number of tracks on the uSD card (as reported by the MP3 module).

The best I've come up with so far is:

    If MaxTracks > 255 Then
       Do
          Let T_Hi = Random
          Let T_Lo = Random
          Let Track = T_Hi * 256
          Let Track = Track + T_Lo
          Let Track = Track & 0b0011111111111111   'Represents 16,383. Masks off the upper bytes,
                                                   'limiting the upper limit of the value.
       Loop Until Track <= MaxTracks
    Else
       Let Track = Random
    End If

Though I can't help thinking there should be a better way.

My next thought was to multiply a random value by 40 (giving a maximum value of 255 x 40 = 10,200) masking the upper byte and clearing the lower byte then moving a second random value into the lower byte. Something like this:

     If MaxTracks > 255 Then
       Do
          Let T_Hi = Random
          Let T_Lo = Random
          Let Track = T_Hi * 40 'gives a maximum value of 10,200
          Let Track = Track & 0b1111111100000000   'Represents 65,280. Masks off the upper bytes, clearing all lower bytes,
                                                   'limits the upper value to 9,984.
           Let Track = Track + T_Lo 'Add in the lower random value of up to 255
       Loop Until Track <= MaxTracks
    Else
       Let Track = Random
    End If

Which seems better, but then I wonder whether multiplying a random number removes some of it's "randomness". I also think that both these methods might favour higher numbers rather than lower ones.

I do seed the random, using Randomise, once earlier in the code, based on the time it took for the first selected track played for, or, if no track played initially, the time from startup before the key was pressed requesting a random track be played.

[stan cartwright]

There's the scale function to map a 16bit random number to 1 to 99999 but misses numbers and is integer.
try
10000/256=39.0625
256*39=9984
so pick a random 0 to 255 and a random 1 to 39 slot of 255 tracks.

[stan cartwright]

It should be
slot = random / 7 +1 ------------- 255/7=36--+1=37
track = random ------------------ 255
result = slot * track -------------- 255*37=
I think that's 9435 tracks ...not 9999 but won't in theory miss any in that range

[David Stephenson]

Of course if you multiply two numbers (even ramdom ones) you can never get a prime number. So all high prime numbers will be missing if you're not careful.

[stan cartwright]

howabout?
num=random
num = num * random / 4 ;-----16384 max
if num > 9999 then
num=16384 - num
end if

[stan cartwright]

I tried this and zeros come up every 12 to 18 seconds but no 9999 until zeros reached 26.
So it works...does it?

dim  track as word
dim bot,top as byte
top=0:bot=0
randomize
do
track = random
track = (track * random)/4 - 1
if track > 9999 then
  track = 16384 - track
end if
if track=9999 then top++
if track=0 then bot++
GLCDPrint_Nextion (0,48,str(track) + "  ", tft_yellow)
GLCDPrint_Nextion (0,96,str(top) + "  ", tft_yellow)
GLCDPrint_Nextion (0,144,str(bot) + "  ", tft_yellow)
loop

edit did it wrong...won't get 9999
trying track = (track * random)/4 - 1 ... in case random is 10000......running a few minutes
edit 10 minutes later one 9999 and two zeros
edit 5 minutes later two 9999 and two zeros

[David Stephenson]

The other standard way of getting a random number is to run the clock (timer1) continously then stop when when the user makes the selection. So you could set timer1 to overflow at 9999.

[stan cartwright]

or count in a loop to 9999 and wait for key press but thinks mkstevo wants no keypress

[mkstevo]

or count in a loop to 9999 and wait for key press but thinks mkstevo wants no keypress

The next track is 'selected' automatically once the current track stops playing. There is no keypress as such, but the timer could be sampled on track change. I think!

[mkstevo]

Thanks for the suggestions. Most of them are variations on ones that I tried.

The one I was using for a while was to generate 40 random numbers, and divide each by 128 adding the result of these calculations together (this gives a near 50/50 chance of being a 1 or 0) and then multiplying a final random value by the result. The output from this was nearly always near the 'middle' of the range, IE most values were between 4,000 - 6,000, very rarely either side. I then executed a random value inside a For ... Next loop 40 times while also multiplying the (random) value by the 'toss of the coin' which either did or didn't add this to the final value. This wasn't any improvement.

I also felt (as David pointed out) that multiplying a random number causes some of the values to be lost.

Perhaps I'll simply generate two random numbers, place one in the upper byte and one in the lower byte of my word value as per my first example, mask off the uppermost bits and then if that value exceeds 9999, deduct 9999 from the given value so that it 'wraps around' towards zero. I feel that this then tilts the generation towards that of numbers being in the lower two thirds of the range (6384 or below) and not an even chance of any one number being generated. Whether masking off the upper two bits compensates a little for this 'tilt' I'm not sure, it may help a little?

    If MaxTracks > 255 Then
          Let T_Hi = Random
          Let T_Lo = Random
          Let Track = T_Hi * 256
          Let Track = Track + T_Lo
          Let Track = Track & 0b0011111111111111   'Represents 16,383. Masks off the upper bytes,
                                                   'limiting the upper limit of the value.
         If Track > MaxTracks Then
                 Do
                     Let Track = Track - MaxTracks
                 Loop Until Track <= MaxTracks
          End If
    Else
       Let Track = Random
    End If

I do like the sound of using the timer and using it to generate the random value. I'll give this some consideration. I'll read up on using timers in GCB. My only concern would be that as any one track takes a fixed time to play, from any given track, the next 'random' track would be the same one that was chosen the previous time the track played. If I limited the timer to 9,744 and then added a random value to the timer that potential hitch should be eliminated though.

I might even go back to my last most recent iteration, that of generating a single random number, adding that to the current track and always jumping forwards from the current track until the maximum number of tracks is exceeded and the number of tracks is deducted so that play begins at (or near to) track 1 - 255 and start again [the sequence looking like: 1, 243, 421, 425, 601, 654, 728, 906 ... 9793, 9980, 17, 107, 181]. This doesn't give an even chance of any single number being generated, but it does give a fair degree of mix of music played which is the next best thing?

[David Stephenson]

Yes I think you are on the right track.
Put one random in the upper byte one in the lower byte and mask off the upper two bits as you have done (or divide by 6 might work)
I would discard any number above 9999 and recalculate a new number.
Another way I've seen described (but I haven't tried myself) is to use the watchdog timer as a method to stop the timer clock. The argument is that the watchdog timer is not that accurate so if it is set to s sufficiently long time (and your other timer is running using a fast oscillator) the output will be kind of random.
I've been meaning to try another type as I've bought so pin diodes which claim to be able to detect gamma-rays (this should provide a random method to stop the timer).

[Anobium]

Or, you can use the Great Cow BASIC ethernet stack. Call the https://www.random.org/clients/ API. Now this may be overkill........

[mkstevo]

More food for thought there...

I'm at least pleased that there seems not to be a single, simple answer. I've spent ages on this yet still haven't found a one size fits all answer.

This looks promising on first test though?

    If MaxTracks > 255 Then
          Do
            Let TempLong  = Random
            Let TempLong  = TempLong * Random
            Let TempLong  = TempLong * Random 'generate a random number
            Let TempLong  = TempLong * Random 'of up to 4 billion or so.
            Let Track.0  = TempLong.1  'Place some shuffled bits into
            Let Track.1  = TempLong.15 'the lower bits of Track
            Let Track.2  = TempLong.7
            Let Track.3  = TempLong.16
            Let Track.4  = TempLong.30
            Let Track.5  = TempLong.25
            Let Track.6  = TempLong.4
            Let Track.7  = TempLong.6
            Let Track.8  = TempLong.10
            Let Track.9  = TempLong.27
            Let Track.10 = TempLong.17
            Let Track.11 = TempLong.21
            Let Track.12 = TempLong.19
            Let Track.13 = TempLong.11
            Let Track.14 = 0
            Let Track.15 = 0
        Loop until Track < MaxTracks
        Let MaxTracks = MaxTracks + 1 'don't give a value of zero
    Else
       Let Track = Random
    End If

The above seemed to have an odd liking for generating a value of 1. I tried this 100 to 200 times and got a value of 1 about 5 or 6 times. This led me to refine it a little:

    If MaxTracks > 255 Then
          Do
            Let TempByte1  = Random
            Let TempByte3  = Random
            Let TempByte3  = Random 'generate a random number
            Let TempByte4  = Random 'of up to 4 billion or so.
            Let Track.0  = TempByte1.1 'Place some shuffled bits into
            Let Track.1  = TempByte2.2 'the lower bits of Track
            Let Track.2  = TempByte3.3
            Let Track.3  = TempByte4.4
            Let Track.4  = TempByte1.2
            Let Track.5  = TempByte2.3
            Let Track.6  = TempByte3.4
            Let Track.7  = TempByte4.5
            Let Track.8  = TempByte1.3
            Let Track.9  = TempByte2.4
            Let Track.10 = TempByte3.5
            Let Track.11 = TempByte4.6
            Let Track.12 = TempByte1.4
            Let Track.13 = TempByte2.5
            Let Track.14 = 0
            Let Track.15 = 0
        Loop until Track < MaxTracks
        Let MaxTracks = MaxTracks + 1 'don't give a value of zero
    Else
       Let Track = Random
    End If

This seems to work better. I wonder if the 'long' variable overflowed with the byte mathematics? At one point it became stuck on '1' and went no further. I have had odd results given when I mixed byte variables with word variables (for example Byte = Word / 1000) when the result is always a Byte value it swould sometimes give me unexpected results. I try to remember to always do maths on the same type of variable before assigning the 'Byte result, of Word maths' into a byte value.

Mind you, my maths isn't great.

Thanks to all for the suggestions. I think the ethernet stack solution could be a step too far, but thanks all the same!

[stan cartwright]

I can't think of 9999 tracks I'd want to hear

[mkstevo]

I've got a bigger player which has over 14,000 tracks on it...

[David Stephenson]

The problem with using random is that it uses a "linear feedback shift register" which will generate the same set of numbers each time it is run unless it is ramdomly seeded (using randomize).

[stan cartwright]

Gcb uses what seem "standard" random generator, shift and xor.
Does it produce 255 different numbers then repeat same numbers?
Otherwise you'd need an array of 1250 bytes-10000 bits, to store tracks already played.

[David Stephenson]

Hugh explained it many years ago. It actually repeats every 65536 as it uses a 16-bit shift register.

https://sourceforge.net/p/gcbasic/discussion/579126/thread/4a56ad47/