TheBackShed.com

Forum Index : Microcontroller and PC projects : Problem with rnd() function

Author

Message

William Leue
Guru

Joined: 03/07/2020
Location: United States
Posts: 405

Posted: 08:05pm 08 Feb 2021

Copy link to clipboard

Print this post

With any runtime library that I have used for many years, the rnd() function (sometimes called rand(), other names) generates uniformly distributed random numbers in the half-open interval [0...1): that is, zero appears as a possible output but 1 does not: the range of generated numbers gets close to 1 but never reaches it.

To create random integers in a range from Min to Max, use

Min + (int)(rnd() * ((Max - Min) + 1))

However, the MMBasic rnd() function doe not work this way. First, the range of generated numbers is the closed interval [0...1]; that is, 1 is included. But this is not the biggest problem. The ugly part is that, although zero and one are included in the range of generated numbers, but they only appear about half as often as other values in the range. (This is easy to see, just compute a histogram of a large number of trials.)

This means that to get a uniformly distributed range of values, you have to throw out the boundary values when they get generated.

-Bill

JohnS
Guru

Joined: 18/11/2011
Location: United Kingdom
Posts: 4044

Posted: 08:54pm 08 Feb 2021

Copy link to clipboard

Print this post

Could you convert 1 to 0 and it would then be right?

John

Nimue

Guru

Joined: 06/08/2020
Location: United Kingdom
Posts: 420

Posted: 09:05pm 08 Feb 2021

Copy link to clipboard

Print this post

William Leue said
However, the MMBasic rnd() function doe not work this way. First, the range of generated numbers is the closed interval [0...1]; that is, 1 is included. But this is not the biggest problem. The ugly part is that, although zero and one are included in the range of generated numbers, but they only appear about half as often as other values in the range. (This is easy to see, just compute a histogram of a large number of trials.)

-Bill

That's interesting -- MMBasic -- on what platform? On the CMM2 rnd() definitely does not generate 1 -- I ran 100,000,000 iterations for a pi simulation on an old thread and the rnd() generator works as expected.

I simulated 1 to 100 via (int(rnd*100) + 1)

Happy to repeat if needed.

I dont think anything has changed with rom upgrades?

Nim

Entropy is not what it used to be

Nimue

Guru

Joined: 06/08/2020
Location: United Kingdom
Posts: 420

Posted: 09:16pm 08 Feb 2021

Copy link to clipboard

Print this post

MMBasic (windows) I get:

Using this code:

Dim counts(100)
For x = 1 To 1000000
value=Int((Rnd()*10)+1)
Select Case value
Case value
counts(value)=counts(value)+1
Next

For x = 1 To 10
Print x,counts(x)
Next

This seems as expected.....

Entropy is not what it used to be

TassyJim

Guru

Joined: 07/08/2011
Location: Australia
Posts: 6283

Posted: 09:19pm 08 Feb 2021

Copy link to clipboard

Print this post

Getting the end points at half value sounds like you are converting from float to integer without using INT().

A simple conversion will round the float and cause the effect you are seeing.

x = Mn + int(rnd() * (Mx - Mn))

should do the job nicely.

This was discussed some time ago (before the CMM2 I think) but I can't find the discussion quickly.

DIM INTEGER mn = 10
DIM INTEGER mx = 790
DIM INTEGER x,y
DIM INTEGER hist1(800)
DIM INTEGER hist2(800)
CLS
LINE mn,0,mn,MM.VRES,1,RGB(RED)
LINE mx,0,mx,MM.VRES,1,RGB(RED)
DO
x = Mn + INT(RND() * ((Mx - Mn) + 1))
hist1(x) = hist1(x)+1
PIXEL x, MM.VRES-hist1(x)/20
LOOP UNTIL INKEY$<>"" OR hist1(x) > MM.VRES*10
SAVE IMAGE "histogram1.bmp"
CLS
LINE mn,0,mn,MM.VRES,1,RGB(RED)
LINE mx,0,mx,MM.VRES,1,RGB(RED)
DO
x = Mn + INT(RND() * (Mx - Mn))
hist2(x) = hist2(x)+1
PIXEL x, MM.VRES-hist2(x)/20
LOOP UNTIL INKEY$<>"" OR hist2(x)> MM.VRES*10
SAVE IMAGE "histogram1.bmp"

FOR x = mn-2 TO mx+2
PRINT x,,hist1(x),, hist2(x)
NEXT x

Jim

VK7JH
MMedit

Nimue

Guru

Joined: 06/08/2020
Location: United Kingdom
Posts: 420

Posted: 09:27pm 08 Feb 2021

Copy link to clipboard

Print this post

Nimue said

Dim counts(100)
For x = 1 To 1000000
value=Int((Rnd()*10)+1)
Select Case value
Case value
counts(value)=counts(value)+1
Next

For x = 1 To 10
Print x,counts(x)
Next

This seems as expected.....

Just realised this is overly complex:

Dim counts(100)
For x = 1 To 1000000
value=Int((Rnd()*10)+1)
counts(value)=counts(value)+1
Next

For x = 1 To 10
Print x,counts(x)
Next

Entropy is not what it used to be

TassyJim

Guru

Joined: 07/08/2011
Location: Australia
Posts: 6283

Posted: 09:47pm 08 Feb 2021

Copy link to clipboard

Print this post

And this version shows the problem when you assign floats to integers without using INT()

DIM INTEGER mn = 10
DIM INTEGER mx = 790
DIM INTEGER x
dim float y
DIM INTEGER hist1(800)
DIM INTEGER hist2(800)
CLS
LINE mn,0,mn,MM.VRES,1,RGB(RED)
LINE mx,0,mx,MM.VRES,1,RGB(RED)
DO
y = Mn + (RND() * (Mx - Mn))
hist1(y) = hist1(y)+1
PIXEL y, MM.VRES-hist1(y)/20
LOOP UNTIL INKEY$<>"" OR hist1(y) > MM.VRES*10
SAVE IMAGE "histogram1.bmp"
CLS
LINE mn,0,mn,MM.VRES,1,RGB(RED)
LINE mx,0,mx,MM.VRES,1,RGB(RED)
DO
x = Mn + INT(RND() * (Mx - Mn))
hist2(x) = hist2(x)+1
PIXEL x, MM.VRES-hist2(x)/20
LOOP UNTIL INKEY$<>"" OR hist2(x)> MM.VRES*10
SAVE IMAGE "histogram1.bmp"

FOR x = mn-2 TO mx+2
PRINT x,,hist1(x),, hist2(x)
NEXT x

Jim

VK7JH
MMedit

Nimue

Guru

Joined: 06/08/2020
Location: United Kingdom
Posts: 420

Posted: 09:48pm 08 Feb 2021

Copy link to clipboard

Print this post

100,000,000 iterations of my code above running on CMM2 gives:

1 10003977
2 9999902
3 10000003
4 9998315
5 10002146
6 9998978
7 10002886
8 9995661
9 9997045
10 10001087

Seems distributed to me - randomly over the range 1-10.

Good enough for me.

-- Sorry no fancy histograms!!!

Nim
Edited 2021-02-09 07:50 by Nimue

Entropy is not what it used to be

William Leue
Guru

Joined: 03/07/2020
Location: United States
Posts: 405

Posted: 11:49pm 08 Feb 2021

Copy link to clipboard

Print this post

I ran careful tests before I posted this.

Yes, I am talking about the CMM2. I have the latest non-beta firmware.

If you run a histogram you will see what I am talking about. And no, you can't just convert the out-of-range numbers and expect to have good statistics.

-Bill

TassyJim

Guru

Joined: 07/08/2011
Location: Australia
Posts: 6283

Posted: 01:51am 09 Feb 2021

Copy link to clipboard

Print this post

William Leue said I ran careful tests before I posted this.

-Bill

Please post code that demonstrates your problem.
The pseudo code doesn't help us help you.

Jim

VK7JH
MMedit

TassyJim

Guru

Joined: 07/08/2011
Location: Australia
Posts: 6283

Posted: 02:12am 09 Feb 2021

Copy link to clipboard

Print this post

DIM counts(11)
DIM INTEGER value, x

FOR x = 1 TO 1000000
value=((RND()*10)+1) ' float being cast to integer > uses rounding
'value=int((Rnd()*10)+1) ' this line works as expected due to using INT()
counts(value)=counts(value)+1
NEXT x

FOR x = 0 TO 11
PRINT x,counts(x)
NEXT x

Without INT()

0 0
1 49705
2 100084
3 99604
4 99934
5 100502
6 100064
7 100378
8 99552
9 99675
10 100091
11 50411

with INT()

0 0
1 100413
2 99930
3 100133
4 99991
5 99301
6 100013
7 100154
8 100044
9 99733
10 100288
11 0

Jim

VK7JH
MMedit

panky

Guru

Joined: 02/10/2012
Location: Australia
Posts: 1114

Posted: 03:44am 09 Feb 2021

Copy link to clipboard

Print this post

William Leue said With any runtime library that I have used for many years, the rnd() function (sometimes called rand(), other names) generates uniformly distributed random numbers in the half-open interval [0...1): that is, zero appears as a possible output but 1 does not: the range of generated numbers gets close to 1 but never reaches it.

To create random integers in a range from Min to Max, use

Min + (int)(rnd() * ((Max - Min) + 1))

However, the MMBasic rnd() function doe not work this way. First, the range of generated numbers is the closed interval [0...1]; that is, 1 is included. But this is not the biggest problem. The ugly part is that, although zero and one are included in the range of generated numbers, but they only appear about half as often as other values in the range. (This is easy to see, just compute a histogram of a large number of trials.)

This means that to get a uniformly distributed range of values, you have to throw out the boundary values when they get generated.

-Bill

Bill,

Your formula above is inclusive, that is all numbers from min to max (inluding both min and max themselves) have a random chance of occuring. That is, your formula creates a closed interval [min ... max] The rnd() function definitely does not return 1 - it returns a floating point number in the closed interval [0.0000000something ... 0.9999999something] - the minimum should be zero but with the lowest floating point number available being 0.22250738585072e-308, it may be a lifetime before a full zero turns up

In 100 million iterations, the highest and lowest numbers returned by rnd() were respectively 0.9999999478 and 0.00000004726462066

Doug

... almost all of the Maximites, the MicromMites, the MM Extremes, the ArmMites, the PicoMite and loving it!

matherp
Guru

Joined: 11/12/2012
Location: United Kingdom
Posts: 10315

Posted: 08:41am 09 Feb 2021

Copy link to clipboard

Print this post

Quote I ran careful tests before I posted this.

The random number generator H/W gives an answer as a 32-bit unsigned integer 0 to 2^32-1
I then divide this by 2^32 with both numbers converted to 64-bit floats so it can't give the answer 1 without an incorrect usage in your Basic code
Note that in my test code any value 1 (or less than 0) would give an array bounds check error. i.e. the RND function works perfectly

cls
dim a%(799)
for i%=1 to 800*300
inc a%(fix(rnd*800))
next i%
for i%=0 to 799
line i%,599-a%(i%),i%,599
next i%
do
loop

Edited 2021-02-09 19:07 by matherp

Print this page

To reply to this topic, you need to log in.