how random is RND in Basic and Turbo Basic? (seems to be different)

[Marius]

Hi all!

 

After years of absence I am trying to do some (turbo) basic coding again. I was trying to create a dice game, but I was doing some experiments by creating a proof of concept first.

 

Now I did run in something very strange. I simulate a throw of 5 dices (just like in a Yatzee game) and I wanted to see whether all numbers (1, 2, 3, 4, 5, and 6) are facing upwards in a (rather) equal amount. So after more than 20.000 throws (23176 to be more specific, which was simply the moment I paused the process), what is the frequency of every "number" that has been thrown. 

I did let run the Atari for a few hours, first in Turbo Basic and then, same routine in Basic. I was surprised by the difference in results:

TurboBasic:

 

Atari Basic:

 

Sorry for the Dutch language, but the pictures mention this:

 

After throw 23176:
 

Turbo Basic:

1: 23560 times f. most

2: 22858 times b.

3: 23290 times c.

4: 23488 times e.

5: 22537 times a. least

6: 23323 times d.

 

Difference between result "5" (least) and "1" (most): 1023
Smallest difference (33 times) between "4" and "6".
 

b-a: 321 (difference between result "2" and "5")

c-b: 432 (difference between result "3" and "2")

d-c: 165 (difference between result "6" and "3")

e-d: 33 (difference between result "4" and "6")

f-e: 72 (difference between result "1" and "4")

Atari Basic:

1: 23152 times c.

2: 22884 times a. least

3: 23414 times f. most

4: 23371 times e.

5: 23040 times b.

6: 23195 times d.

 

Difference between result "2" (least) and "3" (most): 530

Smallest difference (43 times) between "6" and "1"
 

b-a: 156 (difference between result "5" and "2")

c-b: 112 (difference between result "1" and "5")

d-c: 43 (difference between result "6" and "1")

e-d: 176 (difference between result "4" and "6")

f-e: 43 (difference between result "3" and "4")

 

The routine to find random numbers:

 

X = INT(RND(0)*6)+1

 

My questions

1. Who can explain the much more noticeable difference between Turbo Basic and Basic. I mean: there is still quite a noticeable difference between the most frequent and least frequent result in Basic (530) but this difference is almost double the size in Turbo Basic. 

2. Is there a better alternative to the routine I used? I am looking for a routine that will generate a number: 1, 2, 3, 4, 5, or 6 where every result will have (as close as possible to) nearly the same frequency.

3. Is there a chance that this is really a random coincidence? I find it hard to believe, since I stopped it at 20.000+ throws. But perhaps you have experience with this subject?

 

Thanks anyway!

(Meanwhile I will do a few more runs, perhaps I get completely different results).

 

 

 

Edited January 21, 2023 by Marius
added words "least" and "most"

[Rybags]

Would need to check the routines in both cases.

Atari Basic does (random #) / 65536 where the initial random # comes from reading $D20A into the low/hi bytes of a 16 bit integer then converting to FP before the divide.

 

Possibly TBasic uses a software LFSR though that's usually when you want a deterministic sequence.

I only just realised Atari Basic did it that way, my thought beforehand was that it populated the mantissa of a BCD number from $D40A reads checking that each digit was valid BCD before continuing (in theory that could cause a long delay)

 

I looked into software LFSR and generated one for a project, though have to say it's randomness isn't so great.  The problem you can get is that although you can get a nonrepeating long sequence of numbers they generally never have sequences of near results.

 

 

[danwinslow]

I have no certain knowledge about randomization testing, but I would not have considered your results unusual for an 8bit 1980s randomizer. Is it just the once, or did you repeat this process many times? My first impulse would be to run the whole thing at least 10 more times to see if its consistent (with different start seeds).

You can find a WHOLE LOT online about randomness testing and RNGs if you poke around....almost too much, its a very heavily studied area.

[Rybags]

OK, from a quick look at TBXL 1.5 - it seems that it is the one that constructs a BCD mantissa a digit at a time, validating each one as it goes.

I guess possibly this method might be faster since there's no need to do the binary -> FP conversion followed by an FP divide.

 

I also would theorise that due to throwing away any nybble value >= $0A that it's probably screwing with the distribution which could be cause of some value ranges becoming more common than others.

Or possibly not... with the 17-bit LFSR sequence you get each number appearing once.  Throwing out invalid BCD candidates should still mean equal chance of hitting 0 thru 9.

 

    DA84: C6 AA             DEC $AA
    DA86: A9 3F             LDA #$3F
    DA88: 85 D4             STA FR0
    DA8A: A2 05             LDX #$05
    DA8C: AD 0A D2          LDA RANDOM
    DA8F: 29 F0             AND #$F0
    DA91: C9 A0             CMP #$A0
    DA93: B0 F7             BCS $DA8C
    DA95: 85 E0             STA FR1
    DA97: AD 0A D2          LDA RANDOM
    DA9A: 29 0F             AND #$0F
    DA9C: C9 0A             CMP #$0A
    DA9E: B0 F7             BCS $DA97
    DAA0: 05 E0             ORA FR1
    DAA2: 95 D4             STA FR0,X
    DAA4: CA                DEX
    DAA5: D0 E5             BNE $DA8C

Edited January 21, 2023 by Rybags

[Marius]

Thank you both for your answers! very interesting! I am testing in Turbo Basic for the 2nd run, this time it is at 34724th result, and the "5" is again pretty much behind (about 1400 less than the max. threw result) ...

I will keep testing this. 

 

 

[Wrathchild]

You could try using the Pearson's Chi-Squared test mentioned here

[dmsc]

Hi!

10 hours ago, Marius said:

Hi all!

 

After years of absence I am trying to do some (turbo) basic coding again. I was trying to create a dice game, but I was doing some experiments by creating a proof of concept first.

 

Now I did run in something very strange. I simulate a throw of 5 dices (just like in a Yatzee game) and I wanted to see whether all numbers (1, 2, 3, 4, 5, and 6) are facing upwards in a (rather) equal amount. So after more than 20.000 throws (23176 to be more specific, which was simply the moment I paused the process), what is the frequency of every "number" that has been thrown. 

I did let run the Atari for a few hours, first in Turbo Basic and then, same routine in Basic. I was surprised by the difference in results:

.... snipped ...

10 hours ago, Marius said:

 

After throw 23176:
 

Turbo Basic:

1: 23560 times f. most

2: 22858 times b.

3: 23290 times c.

4: 23488 times e.

5: 22537 times a. least

6: 23323 times d.

 

Difference between result "5" (least) and "1" (most): 1023
Smallest difference (33 times) between "4" and "6".

 

Those results implicate that you threw 6 dices 23176, or the same as you threw 1 dice 139056 times.

 

A little probability quiz, this is what you should be asking:

- What is the probability that the difference between the times of occurrence of the 6 different outcomes of each throw is more than 1022?

 

The result is not easy to calculate, but it is about 3×10⁻⁵. This means that in fact, your distribution is a little off, as there is very little probability of occurrence of your result (one in 33000 tries).

 

In your second example:

10 hours ago, Marius said:

Atari Basic:

1: 23152 times c.

2: 22884 times a. least

3: 23414 times f. most

4: 23371 times e.

5: 23040 times b.

6: 23195 times d.

 

Difference between result "2" (least) and "3" (most): 530

Smallest difference (43 times) between "6" and "1"

 

Here, our confidence test is: 

- What is the probability that the difference between the times of occurrence of the 6 different outcomes of each throw is more than 529?

 

The answer is about 0.135, so 13.5% of the time the difference will be bigger than 530. This implies that your result has a fair probability of occurring.

 

So, it seems that Turbo Basic XL has a problem with the RND() function, or with the rounding of the multiplication.

 

You are using the expression X = INT(RND(0)*6)+1 to calculate the dice number. 

 

Both Atari and Turbo Basic use decimal representation of numbers, with 10 significant digits at most. In the case of the RND function, the result is between 0.0000000000 to 0.9999999999. If each of those numbers occurred with the same probability, the probabilities of each dice with your formula are:

- 1 : 0.1666666667

- 2 : 0.1666666667

- 3 : 0.1666666666

- 4 : 0.1666666667

- 5 : 0.1666666667

- 6 : 0.1666666666

 

I checked this in Trubo Basic, and it gives correct results for all the corner cases. So, there are very little difference in probabilities of each number, and the 3 and 6 are the lowest probable. For the differences that you found, the probability mismatch should be bigger than that.

 

This is the code of the RND() function in Turbo Basic: https://github.com/dmsc/turbo-dis/blob/master/asm/x-random.asm#L15

 

Assuming that RANDOM (from POKEY LSFR) gives correctly distributed numbers, the result should be correctly distributed also. BUT, the POKEY LSFR is not a real random number generator, it has a limited period and it is correlated from one cycle to the next. In the code, there are 13 cycles between each read of RANDOM, perhaps the correlation means that certain digit distributions are more probable than others.

 

On the other hand, in Atari BASIC, the code of RND is much simpler, it gets a random number between 0 and 65535, and then divides it by 65536 and just uses it. This means that you can´t use it to get numbers in big ranges, as the distribution will be very bad.

 

Well, for the time being, the discrepancy in probabilities will not be that noticeable, and if you want better results, you can use FastBasic and generate the dice with " RAND(6)+1 ", I tested this in real Atari and it gives a very stable distribution.

 

Have Fun!

 

[phaeron]

The 17-bit LFSR is actually slightly biased in that its sequence has one more '1' bit than '0' bit, but you'd hardly notice the 0.00038% bias.

 

Throwing away numbers above a threshold is a commonly recommended way to wrap to a lower range without introducing bias, compared to modulo which can short the final value. The catch is that this assumes that the retries use values that are independent from the previous value. This isn't really true since the 17-bit LFSR used by RANDOM has a short feedback cycle. In the TBXL loop, each retry retrieves a new value 11 or so cycles after the previous one, so there is probably some influence from the previous value known to be >=10 or >=100. When I implemented a similar routine for Altirra BASIC, it was pretty sensitive to the cycle count -- certain cycle counts produced noticeably poorer results.

 

[TGB1718]

Just for the heck of it, I did a run using assembler (I know, not BASIC), these are the results of 4 runs, all FP is used for is

the conversion of the output from INT to TEXT  reasonably even split

 

Ones   =  10978
Twos   =  11113
Threes =  10774
Fours  =  10924
Fives  =  10932
Sixes  =  10813

 

Ones   =  10864
Twos   =  11018
Threes =  11047
Fours  =  10998
Fives  =  10741
Sixes  =  10866

 

Ones   =  10644
Twos   =  10959
Threes =  11036
Fours  =  11103
Fives  =  10901
Sixes  =  10891

 

Ones   =  10776
Twos   =  10927
Threes =  11028
Fours  =  10754
Fives  =  11065
Sixes  =  10984 

 

 

[Rybags]

Which RND algorithm is being used though?

 

[TGB1718]

Nothing special, just read $D20A

AND #$07

check if Zero -> read again

check if 7 -> read again

else

increment appropriate counter

increment loop counter

exit if reached limit

read again

 

[Rybags]

I think to determine there's no bias going on you would need to do ranking of how many of each # comes up.

Then do multiple runs (maybe total of about 60)

Then check distribution of rankings.

[+David_P]

On 1/22/2023 at 11:05 AM, TGB1718 said:

Nothing special, just read $D20A

AND #$07

check if Zero -> read again

check if 7 -> read again

else

increment appropriate counter

increment loop counter

exit if reached limit

read again

 

Split into two nibbles, and you may get two dice from each read.

[TGB1718]

6 hours ago, David_P said:

Split into two nibbles, and you may get two dice from each read.

Very true, but if either is out of range, you still have to got back and read again, plus the extra processing required.

[Wrathchild]

Waste half a page with a lookup table of valid/invalid flags. cost=1 indexed lookup and 1 branch, e.g. returns one value in X and the other in A

 

LegitDicePairs:
:128	.byte [$80*[#>=$70 || #<$10 || #&$0F>=$07 || #&$0F=$00]]+(#>>4)

GetRandomDicePair:
	JSR GetRandomInA
	AND #$7F
	TAY
	AND #$0F
	LDX LegitDicePairs,Y
	BMI GetRandomDicePair
	RTS

 

 

As this has more chance of needing to obtain a random value again this can be catered for:

LegitDicePairs:
:128	.byte [$80*[#>=$70 || #<$10 || #&$0F>=$0D || #&$0F=$00]]+(#>>4)

GetRandomDicePair:
	JSR GetRandomInA
	AND #$7F
	TAY
	AND #$0F
	CMP #$07
	BCC ok
	SBC #$06
ok:    
	LDX LegitDicePairs,Y
	BMI GetRandomDicePair
	RTS

 

Edited January 24, 2023 by Wrathchild

[Marius]

This is so cool! You people are so helpful and I learn a lot from you. I came up with a much more complicated routine in Turbo BASIC which I compiled and I let it run without screen output. It did run for millions of throws and it gave around 16,67% for each of the 6 numbers, so my conclusion was that eventually the results are indeed random enough.

 

When I compare my code to what is presented here, I feel not very bright haha. I will share the code soon. Perhaps you can give some feedback on it and tell me whether the path I chose is neeeded or not.

 

Without having the code here, this is what I did:

 

I read the RANDOM memory location by X=PEEK(RANDOM) and then I check the result and do a few If Then instructions. 

 

X >=0 and X<42 then R=1

X>=42 and X<84 then R=2

X>=84 and X<126 then R=3

X>=126 and X<168 then R=4

X>=168 and X<210 then R=5

X>=210 and X<252 then R=6

X>=252 then no result, reread random

 

I thought: by using almost all possible results from 0 to 255 divided by 6 (so that leads to 6 blocks of usable random results) it gives a pretty good random image.

 

Will checking for just 1-6 and ignoring all other results be just as reliable (as in random) as the method I chose now?

 

I will have to try to get my code here. But the most important part of it (the concept) is in this post....

 

 

[rcamp48]

On 1/21/2023 at 5:51 AM, Marius said:

Hi all!

 

After years of absence I am trying to do some (turbo) basic coding again. I was trying to create a dice game, but I was doing some experiments by creating a proof of concept first.

 

Now I did run in something very strange. I simulate a throw of 5 dices (just like in a Yatzee game) and I wanted to see whether all numbers (1, 2, 3, 4, 5, and 6) are facing upwards in a (rather) equal amount. So after more than 20.000 throws (23176 to be more specific, which was simply the moment I paused the process), what is the frequency of every "number" that has been thrown. 

I did let run the Atari for a few hours, first in Turbo Basic and then, same routine in Basic. I was surprised by the difference in results:

TurboBasic:

 

Atari Basic:

 

Sorry for the Dutch language, but the pictures mention this:

 

After throw 23176:
 

Turbo Basic:

1: 23560 times f. most

2: 22858 times b.

3: 23290 times c.

4: 23488 times e.

5: 22537 times a. least

6: 23323 times d.

 

Difference between result "5" (least) and "1" (most): 1023
Smallest difference (33 times) between "4" and "6".
 

b-a: 321 (difference between result "2" and "5")

c-b: 432 (difference between result "3" and "2")

d-c: 165 (difference between result "6" and "3")

e-d: 33 (difference between result "4" and "6")

f-e: 72 (difference between result "1" and "4")

Atari Basic:

1: 23152 times c.

2: 22884 times a. least

3: 23414 times f. most

4: 23371 times e.

5: 23040 times b.

6: 23195 times d.

 

Difference between result "2" (least) and "3" (most): 530

Smallest difference (43 times) between "6" and "1"
 

b-a: 156 (difference between result "5" and "2")

c-b: 112 (difference between result "1" and "5")

d-c: 43 (difference between result "6" and "1")

e-d: 176 (difference between result "4" and "6")

f-e: 43 (difference between result "3" and "4")

 

The routine to find random numbers:

 

X = INT(RND(0)*6)+1

 

My questions

1. Who can explain the much more noticeable difference between Turbo Basic and Basic. I mean: there is still quite a noticeable difference between the most frequent and least frequent result in Basic (530) but this difference is almost double the size in Turbo Basic. 

2. Is there a better alternative to the routine I used? I am looking for a routine that will generate a number: 1, 2, 3, 4, 5, or 6 where every result will have (as close as possible to) nearly the same frequency.

3. Is there a chance that this is really a random coincidence? I find it hard to believe, since I stopped it at 20.000+ throws. But perhaps you have experience with this subject?

 

Thanks anyway!

(Meanwhile I will do a few more runs, perhaps I get completely different results).

 

 

 

Those numbers will vary by a little amount , in essence the more different the numbers are the more pseudo-random they will be , and actually numbers on a 1980s computer will be what we call pseudo-random depending on how they are seeded. I am not sure if Turbo Basic or Atari Basic have a similar command to Randomize in Quick Basic 64 but if they do it would be more appropriate to use a Randomize Timer function or create a function that will do that in either Turbo or Atari Basic. In Atari Basic if you have a way of seeding the number or even using several cycles in loops to increase the cycles between each RND pick, it would make it more random. Actually the closer together in cycles that Basic calls the RND function the less random that number will be. 

 

Russ

 

[rcamp48]

In the above you use the following:

 

I read the RANDOM memory location by X=PEEK(RANDOM) and then I check the result and do a few If Then instructions. 

 

IF X >=0 and X<42 then R=1

IF X>=42 and X<84 then R=2

IF X>=84 and X<126 then R=3

IF X>=126 and X<168 then R=4

IF X>=168 and X<210 then R=5

IF X>=210 and X<252 then R=6

IF X>=252 then no result, reread random

 

If you wanted to make sure that each of the 6 numbers were not the same then try the following code:

 

10 DIM Y(6),U(6),V(6),R(6)

15 PRINT CHR$(125)

17 PRINT "Range of Numbers Drawn [1 to Y] "

18 PRINT "With Y being largest Number ==> ",number

20 for Z = 1 to 30000

30 FOR A=1 TO 6

40 GOSUB 10000

50 IF R=0 THEN GOSUB 10000

60 GOSUB 10000

70 FOR U=1 TO 2

80 IF R=Y(U) OR R=0 THEN GOSUB 10000

90 NEXT U

100 GOSUB 10000

110 FOR U= 1 TO 3

120 IF R=Y(U) OR R=O THEN GOSUB 10000

130 NEXT U

140 GOSUB 10000

150 FOR U=1 TO 4

160 IF R=Y(U) OR R=0 THEN GOSUB 10000

170  NEXT U

180 GOSUB 10000

190 FOR U=1 TO 5

200 IF R=Y(U) OR R=0 THEN GOSUB 10000

210 NEXT U

220 FOR U=1 TO 6

230 Y(U)=0

240 NEXT Y

250 NEXT Z

360 FOR U=1 TO 6

370 PRINT "1st Num: ";V(1); " ";

380 PRINT "2nd Num: ";V(2);" ";

390 PRINT "3rd Num: ";V(3);" ";

400 PRINT "4th Num: ";V(4);" ";

410 PRINT "5th Num: ";V(5);" ";

420 PRINT "6th Num: ";V(6);" ";

430 PRINT

440 NEXT U

450 END

10000 X=INT(RND(0)*NUMBER)+1

10100 R(1)=X:Y(1)=Y(1)+1:V(1)=R(1)

10200 R(2)=X:Y(2)=Y(2)+1:V(2)=R(2)

10300 R(3)=X:Y(3)=Y(3)+1:V(3)=R(3)

10400 R(4)=X:Y(4)=Y(4)+1:V(4)=R(4)

10500 R(5)=X:Y(5)=Y(5)+1:V(5)=R(5)

10600 R(6)=X:Y(6)=Y(6)+1:V(6)=R(6)

10700 RETURN

 

Anyways the above should make sure that each six numbers picked are all different, and

you could theoretically use this for a lottery picker of 6 numbers.

 

Russ

 

[_The Doctor__]

No that's not how it works, random numbers can repeat or not be seen at all for quite some time, they are random after all. Some days you won't see a number at all other days it seems the number you didn't see the day before is all you see

 

the lottery is slightly different in that numbers aren't repeated in a series except the last ball on some called a power or key ball insert state nickname there, as it can repeat one number from the previous series

 

Edited January 31, 2023 by _The Doctor__

[rcamp48]

10 minutes ago, _The Doctor__ said:

No that's not how it works, random numbers can repeat or not be seen at all for quite some time, they are random after all. Some days you won't see a number at all other days it seems the number you didn't see the day before is all you see

 

 I was referring to random numbers in possibly a lottery, I have run the above program in my Altirra program, corrected any errors , I basically wanted to show how to pick 6 different numbers , say however times you want, and you are right , random numbers an appear more than once in a row, but not in a lottery draw, as I have written in the above.

 

Russ

 

[_The Doctor__]

The original poster was talking about random numbers like in yahtzee and dice games, or role playing games etc. straight up random numbers, not the lottery so maybe we can do a lottery picker thread... oh there is one already, maybe we join that one.

[rcamp48]

 

 

1 hour ago, _The Doctor__ said:

The original poster was talking about random numbers like in yahtzee and dice games, or role playing games etc. straight up random numbers, not the lottery so maybe we can do a lottery picker thread... oh there is one already, maybe we join that one.

Right you are , I will correct the above for Yahtzee

Russ

 

[danwinslow]

The odd thing about randomness is that it impossible to prove, or even define completely. If you could, then by definition it wouldn't be random.

[rcamp48]

11 minutes ago, danwinslow said:

The odd thing about randomness is that it impossible to prove, or even define completely. If you could, then by definition it wouldn't be random.

Agreed, I am working the above program  to :

 

(A) Allow for the user to choose whether or not there are multiple instances of the same #

(B) Allow for the user to choose to have only 1 instance of the same #

(C) Allow for the user to choose how many numbers to draw

(D) Allow for the user to choose what the upper limit is for each set of (x) numbers.

(E) Use as little IF THEN statements as possible , instead use more loops and sub-routines

(F) No GOTOS in the program.

 

This program should allow the user to preset each condition (A-E) in a data file and then

load in that data file when running the program each tie, ie: you would only set each 

condition once.

 

This would allow the OP to use the program for Yahtzee type games or lotteries , and in fact 

could be programmed as an online game for a BBS. Doing this for a BBS would be easy.

 

I will what I have in a changed program in about an hour.

 

Russ

 

[Marius]

On 1/31/2023 at 2:27 AM, _The Doctor__ said:

The original poster was talking about random numbers like in yahtzee and dice games, or role playing games etc. straight up random numbers, not the lottery so maybe we can do a lottery picker thread... oh there is one already, maybe we join that one.

Yes! But everything that happens here is very educational for me (but goes beyond my comprehension too haha). 

 

The answers are so expert level that I now can not find the answer on my question I asked in my last post above this one.

 

What will result to a more balanced randomized output:

 

From the "Random" generator picking just the 1-6 and ignore all the other values (leading to a new PEEK) or using almost all the results from 0-251 and then divided over 6 equal sized groups. I am typing on my phone right now, but with RANDOM I mean the memlocation that gis peekable to get a random number.

 

I did the last thing which gave after millions of "throws"  very balanced result. But I am slightly afraid that I have a "biased" eye. So can someone shine some light on this.

 

And yes: for me it is just the goal to simulate the throw of a die where the results are as random as possible (I am aware by the way that throwing a die in real life will in real life practice also not as random as it seems, but I am talking here about a theoretical situation where every result (1-6) has the same frequency.