Random Number Generation

Anything QL Software or Programming Related.
Post Reply
stevepoole
Super Gold Card
Posts: 712
Joined: Mon Nov 24, 2014 2:03 pm

Random Number Generation

Post by stevepoole »

Hi,
Just over a year ago, I needed large random numbers, so I tried to write my own code to do generate them.

Finally, after much statistical testing, I obtained results as good as the Sinclair ROM RND() functions.

The listing produces screen output to compare the two sets of functions.

Of course you can get large random numbers by concatenating smaller ones, but you may find the core routines interesting.

Regards,
Steve Poole.

100 ::
110 REMark QLforum_random_bas v12mar19
120 REMark Calculates random numbers:
130 REMark core code is in function r()
140 :
150 CLEAR
160 bc=1: q$='': FOR f=1 TO 5: q$=q$&R$
170 IF q$>65537: GO TO 160: ELSE q=q$
180 WINDOW 256,256,256,0: PAPER 0: CLS
190 WINDOW#2,256,256,0,0: PAPER#2,0: CLS#2
200 screen_test : INK#2,7: INK 7
210 PRINT#2, 'QL ROM..': PRINT 'SBasic..'
220 PAUSE 500: GO TO 160
230 ::
240 DEFine PROCedure screen_test
250 SCALE 127,0,0: SCALE#2,127,0,0
260 FOR ch=1,2
270 FOR i=1 TO 16384
280 IF ch=2
290 x=RaND_int(127): y=RaND_int(127)
300 INK#ch, RaND_int(7)
310 ELSE x=RND(127): y=RND(127)
320 INK#ch, RND(7)
330 END IF
340 FILL#ch,1: CIRCLE#ch,x,y,.6: FILL#ch,0
350 END FOR i
360 END FOR ch
370 END DEFine
380 ::
390 DEFine FuNction r(d)
400 LOCal k,c,g
410 REMark random generator 0 to 65537:
420 c=8421: g=65537
430 k=d*c+1: k=k-(INT(k/g)*g)
440 RETurn INT(k)
450 END DEFine
460 :
470 DEFine FuNction R$
480 LOCal rs,kt: REMark PC reseeder:
490 BEEP 123,bc: bc=bc+1: IF bc>24: bc=1
500 REPeat rs
510 FOR kt=1 TO 10
520 IF BEEPING=0: EXIT rs
530 END FOR kt
540 END REPeat rs
550 RETurn '0123456789'(kt)
560 END DEFine
570 :
580 DEFine FuNction MOD_(ms,md)
590 REMark calculate MODulus:
600 RETurn ms-(INT(ms/md)*md)
610 END DEFine
620 :
630 DEFine FuNction RaND_int(mo)
640 REMark random integer (1 to 999999)
650 q=r(q): RETurn MOD_(q,mo+1)
660 END DEFine
670 ::


User avatar
Dave
SandySuperQDave
Posts: 2765
Joined: Sat Jan 22, 2011 6:52 am
Location: Austin, TX
Contact:

Re: Random Number Generation

Post by Dave »

stevepoole wrote:...as good as the Sinclair ROM RND() functions....
That sets a low bar! :P

The best home-made number generator I've seen was a software-defined radio. It was programmed to set frequency to whatever noise came out of it, digitized. So the static would be interpreted as, say, 01101111, so the frequency was set to whatever 01101111 pointed to, which then gave 11100111, 01001000, etc etc. The output was latched into a 16-bit device that sat on his data bus. So any time he'd check he could get a "random" 16-bit number.

He collected stats on its performance by logging the number distribution, frequency distribution, etc. He did find an anomaly that if he hit one specific frequency, within 2-3 samples he would more often than chance hit another specific frequency. So he got two radios and combined them together, each with different frequency tables, and made it so the sample frequency was altered slightly - such that even if two square waves were the input he'd still get acceptably 'random' numbers.

He never did say why he needed such a convoluted system.


stevepoole
Super Gold Card
Posts: 712
Joined: Mon Nov 24, 2014 2:03 pm

Re: Random Number Generation

Post by stevepoole »

Hi,
Yes Dave, the 'Ernie' Premium Bonds prize random number generator used two interfering Zenner Diodes to operate. I don't know if this is still the case.

The DIY routines use a Randomiser before generating a series. This works because on an emulator, PCs are constantly multitasking many programs. So when you beep, the beep lasts a slightly random time depending on job priorities. This is used to reseed the routines. This is the simplest method I could think of to reseed. On a QL with just basic runnig, this would not be the case ! If you don't reseed before generating, you may get repeated series occurring.

Of couse, numbers are only truly random when you generate a long series. 11 calls are only 33% random, whereas 16384 calls gets 99.64% ...
While testing with scatter diagrams, I got moirage patterns on screen, until I realised that the 16-bit r() function divisor needed the vertical SCALE parameter to be adapted to it. I rewrote the test program to cater for such cases...

The new program returns all the ROM random types and much more, but only in the 65537 range !

Why bother ? It is always interesting to look how core routines operate ... and to see their limitations too.

Regards,
Steve.


User avatar
Dave
SandySuperQDave
Posts: 2765
Joined: Sat Jan 22, 2011 6:52 am
Location: Austin, TX
Contact:

Re: Random Number Generation

Post by Dave »

Also, random number generation in digital systems is surprisingly difficult. In school I was taught it was harder than solving the N body problem which I had to simulate for a game I tried to write.


stevepoole
Super Gold Card
Posts: 712
Joined: Mon Nov 24, 2014 2:03 pm

Re: Random Number Generation

Post by stevepoole »

Hi,
The book 'ALGORYTHMS' by Robert Sedgewick (1983) illustrates many fundamental core routines, written in an older Pascal.
It discusses random number generation among others, and shows an incomplete method being investigated by maths boffins at that time.
After some experimentation, I was able to complete the core routine, r(), which surprisingly they had not succeeded in doing.
No doubt after 1983 this had been done by them too, (as the DIY basic and QL ROM routines seem to be equivalent in results).
I enjoy tinkering with core routines, and trying to convert Pascal ones into Basic, sometimes finding optimisations...

The n-body problem can be 'solved' using epicycles for a few specific cases, which are not adequate for real-life situations however, where the foci themselves move...
I have written code to illustrate this, which If I remember correctly, Quanta printed.

Enjoy Tinkering...

Steve.


Post Reply