TRS-80 Pocket Computer - Missing RND function
TRS-80 Pocket Computer and Random Number Generator
The missing RND function of the TRS-80 Pocket Computer
Random numbers are very widely used for programming purposes : games (like dice rolls), simulation of events....
The TRS-80 Pocket Computer and its clone, the Sharp PC-1211, came with many inbuilt functions, but they badly did not have a random function... Yes, you may want to check but the RND Basic statement was not implemented in this very first Pocket Computer.
So, I will take the opportunity of this web page, not only to give you nice formulas to generate random numbers for the TRS-80 Pocket Computer, but also to explain you the way that these formulas are built.
A little piece of theory : what is a random number?
Our goal with random numbers will usually be to pick randomly an integer value within a certain range : 1 to 6 for a dice, 1 to 52 for a card game, 1 to 2 for coin flop game...
What rules should a random generator follow?
- all numbers should have an equal chance to be picked. For a dice game, all 6 numbers should be picked about the same number of times, but not exactly the same over a certain number of tries, to make sure that chance is still here.
- no periodic sequence should occur like 1, 4, 2, 3, 5, 6, 1, 4, 2, 3, 5, 6, 1, 4, 2...
In the specific case of our ancestor of all Pocket Computers, we should also be careful about the hardware limitations, so our randomizer generator should :
- be quick to calculate
- use few variables and resources
How to build a random generator?
Building a random generator available for all purposes
We have seen that we will always pick randomly a value within a certain range but this range will vary from case to case. So, the idea is to have the generator always build a number between 0 and 1. Then this generated number will just need to be multiplied by an integer value. by keeping the integer part of the result of this multiplication, you will obtain an integer in the wanted limits.
For example, for the dice game :
If
R in ]0,1[ is the random number that our function will generate, we can say that R will look like
0.xxxx...Then to get a number N between 1 and 6, you will calculate it this way :
N = INT( 6 * R ) + 1Remark : INT( 6 * R ) will give you a number in the [0,5] range. Adding 1 to this number will translate it in the [1,6] range.
Building a 0.xxxx... random number
The idea always is to build a number where xxxx... digits are not predictable, like widely explained before.
Some numbers, Pi=3.141592654... for example, already have this property but computers usually only have from a 10 to 12 digits precision for numbers so they only know the first digits of these numbers that cannot be used so immediately.
So, a first solution, very commonly used by the computers is to start with any 0.xxxx... number as a seed, to add Pi to it, to exponent the result of this addition with a number that will give unpredictable results. We then just need to keep the xxxx... numbers of the result to have built a new seed for our next random generation.
Then, our formula will be :
R= ( Pi + R ) ^ 5 : R= R - INT R |
A second widely used solution, is the following one : some divisions of prime numbers P have a period of P-1. For example, a division by 17 will have, if the initial number is not a multiple value of 17, a period of 16 digits. Add a "nice" seed to this principle and you will get a nice random generator.
Our formula will be :
R= 221 * R + 0.2113 : R= R - INT R |
Notice : the initial value that you will put in R will give you the initial "seed" of your random generator. And you will see that the new value of R is remarkably independant of the old value of R, which is exactly what we were looking for... but let's demonstrate it a little bit further in our following paragraph.
What is the efficiency of our random generators?
Did we create two great random generators?
The only way to know it is to make sure that the two rules are well followed (equal chance for all numbers to be picked and no repetitive sequence of numbers).
- For the check of non repetitive sequence of numbers, just get a pen and a piece of paper, run the following programs and check that all consecutive numbers (between 0 and 9) that will appear on the screen of the TRS-80 Pocket Computer follow this rule.
- Program #1 :
10 GOSUB 20 : PRINT INT( R * 10 ) : GOTO 10 20 R = ( Pi + R ) ^ 5 : R = R - INT R : RETURN |
- Program #2 :
10 GOSUB 20 : PRINT INT( R * 10 ) : GOTO 10 20 R = 221 * R + 0.2113 : R = R - INT R : RETURN |
- Now, to check that all numbers have about the same probability to be picked by the formula, run the following programs and look how many time each of the 10 numbers stored in A(1) to A(10) were picked.
- Program #1 :
10 FOR N = 1 TO 10 : A(N) = 0 : NEXT N : N = 0 20 GOSUB 60 30 Z = INT( R * 10 ) + 1 : A(Z) = A(Z) + 1 : N = N + 1 40 IF N < 100 PAUSE N : GOTO 20 50 BEEP 1 : END 60 R = ( Pi + R ) ^ 5 : R = R - INT R : RETURN |
- Program #2 :
10 FOR N = 1 TO 10 : A(N) = 0 : NEXT N : N = 0 20 GOSUB 60 30 Z = INT( R * 10 ) + 1 : A(Z) = A(Z) + 1 : N = N + 1 40 IF N < 100 PAUSE N : GOTO 20 50 BEEP 1 : END 60 R = 221 * R + 0.2113 : R = R - INT R : RETURN |
Repeat these tests many times and you will see that :
- there is no repetitive sequence of numbers.
- you will never obtain exactly the same figures in the second test, but on the average all 10 numbers should be picked about the same number of times.
Which of our two formulas is the fastest one?
Just type in these little programs and time how long it takes between the moment you press the
key after having typed the RUN instruction and the time it beeps.
Program #1 :
10 FOR Z = 1 TO 500 20 R = ( Pi + R ) ^ 5 : R = R - INT R 30 NEXT Z : BEEP 1 : END |
Program #2 :
10 FOR Z = 1 TO 500 20 R = 221 * R + 0.2113 : R = R - INT R 30 NEXT Z : BEEP 1 : END |
Here are the results obtained on my TRS-80 Pocket Computer :
- Program #1 : about 490 seconds
- Program #2 : about 265 seconds
Knowing that the 500 times repeated FOR / NEXT loop itself requires about 90 seconds of execution time (please refer to my page about Optimizing execution speed of Basic programs in the TRS-80 Pocket Computer), here is the execution time of one random instruction :
- Program #1 : (490-90)/500 = 0.8 second
- Program #2 : (265-90)/500 = 0.35 second
So, the results are pretty clear, the second formula is much faster to execute.Two other formulas for a Random Number Generator...
First other formula
The following formula was my first formula, I created it when I was in Junior High School... waouh, so long ago . I had needed it for programming a Dungeon & Dragons like game in the TRS-80 Pocket Computer, which was quite hard due to its 1 KB small RAM...
55 REM WORKS ONLY IN RADIAN MODE (NOT IN DEGREE OR GRAD MODES) 60 R = EXP(SQR(Q)) : R = ABS(COS(SQR(R))) : Q = Q + R * 10 : IF Q > 99 LET Q = Q / 103 70 RETURN |
Well, this early brainstorming provided us with a R number between 0 and 1. It already had weak points :
- two variables are needed instead of one to manage the formula.
- it only works in Radian mode, so you will usually have to insert a program line that makes sure Radian mode is set.
Now, do the preceeding tests... and point out why this formula is not as good as the two first ones :
- First, execution time is not very good : about 880 seconds, so (880-90)/500 = 1.58 second per call of this random function.
- Second, all numbers do not have an equal probability to be taken.
Number | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
---|
Probability | 10% | 6% | 5% | 8% | 8% | 8% | 10% | 10% | 10% | 25% |
---|
Second other formula
This formula is taken from a French book about the Sharp PC-1211 (La Conduite du PC-1211 ou TRS-70 Pocket, by Didier Bicking, (C) Editions Eyrolles, 1982) that Jean very kindly lent to me.
60 S = 97 * (9711 + S + Q) : Q = INT (S / 1000) : S = S - 1000 * Q : IF S = 0 GOTO 60 70 S = ( 1000 / S ) ^ 5 : R = S - INT S : RETURN |
Right away, we see that this formula requires three variables.
Now, do the preceeding tests... and point out why this formula is not as good as the two first ones :
- this formula brings a not so good answer in terms of equal chances for all numbers to be picked
Number | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
---|
Probability | 14% | 10% | 10% | 10% | 10% | 10% | 9% | 9% | 9% | 9% |
---|
- But, its main limitation is its execution time which is the slowliest one of all formulas : about 940 seconds, so (940-90)/500 = 1.7 second for each random function call.