random number generator

[MrDEB]

I downloaded the random number generator that is supposed to generate nmbers from 1 - 5 but it doesn't do what it is supposed to

Swordfish Wiki | SwordfishUser / PseudoRandomNumberGenerator browse

here is the code including the "rand" module


Device = 18F43K22
Clock = 16

// int osc and IO pin libraries
Include "intosc.bas"
#option DIGITALIO_INIT = true // automatically call setalldigital
Include "setdigitalio.bas"

// lcd
#option LCD_DATA = PORTD.4
#option LCD_RS = PORTD.2
#option LCD_EN = PORTD.3
Include "LCD.bas"
Include "convert.bas"

//Include "RNDByte.bas"
Include "Rand.bas"
Include "convert.bas"
Dim Y As Byte



TRISB=0

InitializeRND(4)'if desired

main:
Y=GetRND()
PORTB = (Y)

WriteAt(1,1,DecToStr(Y)," ")
DelayMS(2000)
Cls
GoTo main


{
RandGen Module
This is the Module code For the above example. Just copy And paste into the Swordfish IDE And Save in you UserLibrary folder As "RNDByte.bas"...

{
*****************************************************************************
* Name : RndByte.BAS *
* Author : David Eather *
* Notice : This code is placed into the Public Domain *
* : *
* Date : 19/07/2011 *
* Version : 1.0 *
* Notes : call InitializeRND(pValue) with a value between 0-255 *
* : call GetRND() to get a Byte 0 to 255 *
*****************************************************************************
}

{
Module Rand

Dim LCG,GLFSR As Byte

Public Function GetRND() As Byte
'LCG
LCG=(7*LCG+17)

'Galios LFSR
If (GLFSR And 1) = 1 Then
GLFSR = GLFSR Xor 135 '135 is the tap
GLFSR = (GLFSR >> 1) Or $80
Else
GLFSR = (GLFSR >> 1)
End If
result = GLFSR Xor LCG
End Function

Public Sub InitializeRND(ByVal ReSeed As Byte)
LCG = ReSeed
GLFSR = LCG Xor $55 'just making the start values very different - not realy important
If GLFSR = 0 Then 'except that GLFSR must not be zero
GLFSR=1
EndIf
End Sub

GLFSR=1
LCG=84
End

 

[Pommie]

Back in 2009 MrDeb wanted to build a critter ridder, I posted full working code which included a random number generator. It was a psuedo Random number but worked for this instance. I repeat it here for any comments,

Function Rand(Range As Byte) As Byte
Dim i As Byte, feed As Bit, temp As Word
    For i = 0 To 7                      //generate 8 bits
        Feed = Seed.30 Xor Seed.27      //make new bit
        Seed=Seed*2+Feed                //shift seed left and add new bit
    Next  
    Temp=(Seed And 255) * Range         //change Rand from 0 to 255
    Rand = Temp/256                     //to 0 to (Range-1)
End Function

To seed it I added Seed=$12345678 to the startup code.
I also added a i=rand(255) to a loop controlled by a keypress to make it more (psuedo) random.
Note, it's zero based but could easily be changed. I.E. rand(5) would return 0 to 4

And here 14 years later, pretty much the same problem.

Mike.
Edit, BTW, been away over Easter hence late post.

 

[For The Popcorn]

For my own gratification, I played with the idea I described in post #19. It's pretty simple to implement and reasonably random. The function I described needs a minor change - the MOD function needs the MaxDesiredValue, without the 1 subtraction:

RandomNumber = (TimerValue MOD (MaxDesiredValue)) + 1

Two registers need to be set up on the PIC18F25k22 for timer 1. These registers may be called something different on other chips. The timer source is set to Fosc, and the prescaler to 1. The pertinent part of the code is shown below. Each time S1 is pressed, a new random number is generated. Post #19 explains how this works. Please consult the 18F25k22 datasheet to understand the timer setup.

 'timer setup for PIC18F25K22
    '
    T1CON = %01000011
    T1GCON = %00000000


    If S1 =  Pressed Then
        TimerValue.byte0 = TMR1L
        TimerValue.byte1 = TMR1H
        Rand = (TimerValue Mod 5) + 1
        USART.Write("Timer Value : ", DecToStr(TimerValue),"     Rand: ", DecToStr(Rand), 13, 10)  
        DelayMS(367)
    End If

The dots in the graph below are the random numbers generated; there's roughly an even distribution of numbers 1 - 5.

 

[For The Popcorn]

Back in 2009 MrDeb wanted to build a critter ridder, I posted full working code which included a random number generator. It was a psuedo Random number but worked for this instance. I repeat it here for any comments,

As tumbleweed stated a MrDEB topic or two ago, the answers to most MrDEB questions can be found in previous MrDEB posts.

 

[jpanhalt]

The use of modulo to limit the span has bothered me since I used it in an earlier post. In brief, we know you can do certain manipulations to a random set without biasing the distribution, except as is obvious. For example, you can multiply every number by 2. Of course, the result doesn't include odd values, but the remaining distribution is not changed. You can add to every value or delete all of certain values without changing the relative distribution of the remaining values, but modulo is different. It adds to some but not to all values.. At least as I understand how it is being used.

Take the values 0...9 and do mod5. The distribution of values 0 to 4 are not changed initially, but 5 becomes 0, which adds to the frequency of 0 and so forth for 6,, 7, 8, and 9. Thus, 5 values are affected and add to 5 existing values. Maybe that's OK as done in this thread. But what if you wanted to limit the range to 0...7 and did a %8 conversion? An 8 would increase the frequency of 0's and 9 would increase 1's.. The frequencies of 2...7 are not affected. That disturbs the randomness.

I mean this as a question, as I do not understand the C function. Does this:

{
    return (rand() % (upper - lower + 1)) + lower;
}

delete values outside the range or change their values to be in range?

 

[Nigel Goodwin]

The use of modulo to limit the span has bothered me since I used it in an earlier post. In brief, we know you can do certain manipulations to a random set without biasing the distribution, except as is obvious. For example, you can multiply every number by 2. Of course, the result doesn't include odd values, but the remaining distribution is not changed. You can add to every value or delete all of certain values without changing the relative distribution of the remaining values, but modulo is different. It adds to some but not to all values.. At least as I understand how it is being used.

Take the values 0...9 and do mod5. The distribution of values 0 to 4 are not changed initially, but 5 becomes 0, which adds to the frequency of 0 and so forth for 6,, 7, 8, and 9. Thus, 5 values are affected and add to 5 existing values. Maybe that's OK as done in this thread. But what if you wanted to limit the range to 0...7 and did a %8 conversion? An 8 would increase the frequency of 0's and 9 would increase 1's.. The frequencies of 2...7 are not affected. That disturbs the randomness.

I mean this as a question, as I do not understand the C function. Does this:

{
    return (rand() % (upper - lower + 1)) + lower;
}

delete values outside the range or change their values to be in range?

It changes values to be within the supplied range - rand() itself returns a value between 0 and RAND_MAX (a constant set in the compiler, which is at least 32767).

 

[jpanhalt]

Thanks, Nigel,
That's what I thought it did and suspect it disturbs the distribution, except as in the case of 5, where the changes are "balanced." Perhaps, it is better in the general case to delete values out of range.

EDIT: When I mention using tables, this is a more modern edition the book we used before PC's: https://books.google.com/books/abou...s.html?id=kTb6xgEACAAJ&hl=en&output=html_text

 

[For The Popcorn]

I don't believe the MOD function creates any errors.

I'm struggling with Google Sheets on my phone (since I should be asleep!) so it's not too polished. I did MOD (X, 5) over the range from 1 to 255 (without adding 1 to every value to offset from Zero) and the resultant pattern is:

1
2
3
4
0
1
2
3
4
0
●
●
●

with a totally uniform distribution. The randomness of the method comes from a human triggering an event, so I believe there would be no bias to any particular number.

 

[Nigel Goodwin]

Thanks, Nigel,
That's what I thought it did and suspect it disturbs the distribution, except as in the case of 5, where the changes are "balanced." Perhaps, it is better in the general case to delete values out of range.

I don't think it does, as it effectively picks out different 'ranges' - and as it's supposed to be 'random' there doesn't want to be any 'distribution'. Deleting values out of range would be a complete disaster, and serious skew the results - not to mention taking a VERY long time.

For a crude example - wanting 1 to 5 from a RANDOM_MAX of 1000 - 0-100 would be 1, 101 to 200, would be 2, 201 to 300 would be three and so on.

If you've ever tried to write a cards game, you have the 'problem' of selecting random cards - and trying to select each card individually is a really poor way, as you have to check for clashes etc.

The easy way is to create a 52 byte array and store the numbers 1 to 52 sequentially in them. You then 'shuffle' the pack by looping through 52 times selecting each address in turn (so for 'x = 1 to 52') and swapping each value with a randomly selected address between 1 and 52. So you always do a simple 52 times loop, and create a nicely shuffled pack - then you simply take cards off the 'top' of the pack in sequential order. It can obviously be applied to any similar situation.

This was known as the 'British Shuffle', and presumably was developed by a British guy?.

 

[Ian Rogers]

LOL... This thread has gone "tits up" !!

MrDeb wanted the function HE ALREADY HAD to generate 1 to 5 BUT!!! that function generates 0 to 255

Ergo... just divide by 60 and add 1.. or use a different one..

 

[Pommie]

The easy way is to create a 52 byte array and store the numbers 1 to 52 sequentially in them. You then 'shuffle' the pack by looping through 52 times selecting each address in turn (so for 'x = 1 to 52') and swapping each value with a randomly selected address between 1 and 52. So you always do a simple 52 times loop, and create a nicely shuffled pack - then you simply take cards off the 'top' of the pack in sequential order. It can obviously be applied to any similar situation.

I always use this method if I need to shuffle any number of items. It works perfectly and has a fixed execution time.

Mike.

 

[jpanhalt]

Does modulo affect a random distribution? I demonstrated that using %8 on a random distribution of values between 0 and 9 can . A random distribution should have an equal probability that a subsequent number will be any of the in-range numbers, including the number itself. Modulo 8 increases the proportion/likelihood that the next number will be a 0 or 1.

Effectively, the probability of 0 or 1 is doubled compared to to the probability of digits 2 through 7. Deleting any value more than 7 doesn't cause that change; although, the probability for each number is increased by the same amount., i.e., 1 in 8 rather than 1 in 10. Discarding values out of range is easy code, but not as simple a masking.

I just did a Google search and found this: https://crypto.stackexchange.com/qu...~:text=1) Does modulo affect the,Yes, it does.

I agree this does little to help the TS get his code to work, but it might benefit applying modulo to the general case of limiting any random distribution to a particular range.

 

[Nigel Goodwin]

I always use this method if I need to shuffle any number of items. It works perfectly and has a fixed execution time.

Mike.

Last time I used it was in Delphi, to write a simple Windows program to generate random lottery numbers, for a lottery syndicate at work.

 

[For The Popcorn]

I just did a Google search and found this: https://crypto.stackexchange.com/qu...~:text=1) Does modulo affect the,Yes, it does.

This is comparing apples and frosted flakes. As I have described, a human presses a button which retrieves a WORD value from a timer. This value can range from zero to 2^16. Modulo is the remainder when a input number is divided by another, in this case, 5. As I illustrated above, the result of applying the MOD function to 1, 2, 3, 4, 5 ... 65,536 is a regular repeating sequence of 1, 2, 3, 4, 0. The MOD function in this case adds no bias. Look at the screen shot of a snippet of spreadsheet.

Ok, the changes of any number are not entirely equal, since a few digits are lost at the end of the sequence because the full range of the remainder sequence may not be required in the maximum value of a WORD. For a value of 5, there's a 2621/13107 chance of getting most values, with a couple numbers having a better chance of 2622/13107 of being picked.

 

[Tony Stewart]

What is a good entropy test for randomness?

in a sequence of 100 numbers of 1~5 , we can assume each number is generated evenly.

if you count the number of consecutive values,
what is the highest value of consecutive values 6 or ?
How many times before 0 or 6 may occur?

This could be applied to dice also

 

[For The Popcorn]

From the article linked in post #31:

"Your intuition is correct here; if you're taking the result modulo some small number, then you can reduce bias to an acceptably small amount by using a really large range of numbers to begin with."

Exactly what I illustrated above.

 

[jpanhalt]

You can add, subtract, multiply, and delete to change range without affecting the remaining numbers. Modulo is different. Consider the extreme: i.e., %1 converts every value to 0. I am not suggesting anyone do that, but you can do the other operations with immunity with 1. %2 will also give 50% 0's. At some point modulo doesn't cause a big problem. I manually did a 4-bit binary test and %C causes the same bias as %8 did with decimal. %5 seems safe.

My point is that modulo can bias the result. The fact that effect can be minimized in certain cases doesn't' make it any better compared to safe alternatives, like deletion.

 

[For The Popcorn]

You are ignoring the details as I have explained.* In this case, there's a 1/13107 bias for one or two values. The gives one or two values a 0.008% advantage over the 20% chance of getting one of the five possible values in this case. It's far into the noise.

For this to happen, the button presser has to manage to press when the timer is within 4 digits of 2^16.

* And also as your link discusses in point #3.

 

[Tony Stewart]

A random number generator using mod can be implemented using the following steps:

1. Choose two large prime numbers, p and q.
2. Compute n = p*q.
3. Choose a random number, x, between 1 and n-1.
4. Compute y = x^2 mod n.
5. Return y as the random number.

The idea behind this generator is that the output is based on the value of x, which is randomly chosen within the range of 1 and n-1. The value of y is then computed using the modulus operator (%), which ensures that the output remains within the range of 0 and n-1. The use of large prime numbers helps to increase the randomness of the output and reduce the likelihood of generating repeating patterns. However, it is important to note that this method is not cryptographically secure and should not be used for secure applications.

 

[rjenkinsgb]

The method I suggested is ultra simple and fits JPs "no bias" method.

AND with 7 is a shortcut for modulo 8, which has zero bias on an 8 bit value is it repeats 32 times exactly.

Then loop back if the result is not in the required range, so ignoring invalid results.

 

[For The Popcorn]

Please understand – I suggested my timer/modulo idea for the specific situation where a human is causing a trigger event. In this situation, it's a straightforward way of converting a human-generated random number to a usable result with a minimum of code.

If the extremely tiny error (20% chance of some values (of a set of 5) vs. 20.008% chance of other values being generated) is too large for your taste, the solution is trivial. Simply throw away whatever few values at the upper bound exceed the integer number of sets of N (5 in this case).

Timer range = 2^16 = 65,536

Complete sets of N values = 65,536/N = 65536/5 = 13107.2 so there are 13107 complete sets with a remainder of 0.2. If my brain is working correctly, that means we need to throw out the highest value to get an integer number of complete sets:

65,535/5 = 13,107.

So adding a single IF/THEN totally fixes the possible distribution error.


In actuality, the point is moot. If I have to guess, MrDEB wants a 1 – 5 value to determine who goes first in his Mexican train game.

I am somewhat disappointed that a few people latched onto "modulo will lead to biased results" and shut down all thought about why that could be true without any analysis.

But please do understand – I'm not arguing against any of the methods presented here. I did this as a thought exercise to explore what seemed like a simple approach.