aldweb

Fermer I. aldweb

Fermer II. Gratuitiels PC

Fermer III. Gratuitiels Palm

Fermer IV. Partagiciels Palm

Fermer V. iziBasic Palm

Fermer VI. Connaissance Palm

Fermer VII. Ordinateur Poche

Fermer VIII. miniPortail

Recherche




Newsletter
Pour avoir des nouvelles de ce site, inscrivez-vous à notre Newsletter.
S'abonner
Se désabonner
298 Abonnés
Webmaster - Infos
Visites

   visiteurs

   visiteurs en ligne

article.gifTRS-80 Pocket Computer et générateur de nombres aléatoires

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 ) + 1
Remark : 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.
Number12345678910
Probability10%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
Number12345678910
Probability14%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.

Date de création : 01/01/2003 @ 00:00
Dernière modification : 01/01/2003 @ 00:00
Catégorie :


Imprimer l'article Imprimer l'article

 
react.gifRéactions à cet article


Réaction n°2 

par isidroco le 23/04/2018 @ 22:48

Hhi from argentina, also did some speed test of different stuff, an interesting thing I found in other machine, is that (x*0.5) is a lot faster than (x/2), so it's better to replace any division by a constant by a multiplication.
For random I used to pick Clock seconds as a seed (if available).

Réaction n°1 

par Paul le 01/01/2004 @ 22:20

Hi,
I must be your father's age. I have many computers but still use my TRS80 pocket computer - after all these years. I wish the Palm Pilot series were as battery efficient as the TRS-80.

Thanks for the fun article.

-Paul
 
Spécial !



Version mobile
de l'aldweb Site

m.aldweb.com


Ni Français, ni Anglais ?

Essayez donc l'un de ces drapeaux :
[de] [es] [it] [pt]
Météo / Spam / www

Météo Lyon


aldweb contre le SPAM


Sites web de la famille

News Amis
Sondage
Comment trouve-tu le nouvel habillage de l'aldweb Site ?
 
Superbe !
Joli
Moyen
Moche...
Résultats
^ Haut ^