147 and 997 Random Generator Algorithm

[Gamo]

Recently read an old book that teach kid "Math Algorithm" and one of the topic was about the "Random Number Generator."

This book mention using the 147 Algorithm to generate Random Integer.

The steps on how to generate random integer is similar to the 997

Is there any much difference of the random output with these 147 and 997 ??

Thanks

Gamo

[Nihotte(lma)]

Hi Gamo !

Thanks for your question in this thread
I have found it interesting !

I asked me how to answer to it and I thought of a method
So !

In first time, I decided to experiment a distribution of 1000 items between 100 numbers : from 0 to 99.
In perfect world, I can expect a fair distribution of 10 items by number (because 100 x 10 = 1000).
I can consider a couple of data as the number (0..99) and its number of draws obtained all along the distribution
And, if I manage to position and accumulate each pair on a line, I should get a correlation of 1 for a slope of 10.

I needed 4 steps to do this :

1) make a distribution of 1000 generations between the 100 numbers
2) see the result of the distribution
3) transfer the results to a statistical structure
4) collect the calculation of the correlation coefficient of the line and calculate the value of its slope. And I would also like to recover the standard deviation of the data.

Well. I said to me : it's a job for my HP35s, it can do this !
It has a huge memory, easy to adress from 0 to 99.
It's not really slow
It has on-board (built-in) statistical functions

Then, I made 3 little programs, one for each step 1 to 3.
(I will make the step 4 from the keyboard of the calculator)

Code:


001 LBL H
    RCL M
    STO I
    0
005 STO (I)     // puts 0 in registers 99..1
    DSE I
    GTO H005
    STO (I)     // puts 0 in register 0
    RCL M       // M is constant for the number of values to join from 0 to M-1
    STO I
    STO (I)     // stores a value in register 100 (to reserve the array from 0 to M-1 and M)
    RCL L       // L is constant 1000 loops/items
    STO I       // I is the loops counter
    PI
    FP
    STO O       // FRAC(PI) in O
017 RCL O       // RAN#
    RCL S       // S is constant 147, 997, ... you need to test
    x
    FP
    STO O       // stores the next seed for random
    RCL M
    x
    IP          // gives a number from 0 to M-1
    STO J
    1
    STO + (J)   // adds 1 to the winning location
    DSE I
    GTO H017
    RCL I
    RCL S
    RTN

Usage of LBL H to obtain the initial distribution and try to test 147 :
147 STO S (or 997 STO S)
100 STO M
1000 STO L
XEQ H

Code:


001 LBL G
    RCL M
    STO I
    1
    STO - I    // stores M-1 in I
006 RCL I
    RCL (I)    // displays number i (from 99 to 1) and its total of draws
    PSE
    DSE I
    GTO G006
    RCL I      
    RCL (I)    // displays number 0 and its total of draws
    RTN

Usage of LBL G to display each result of the distribution from "winners" 99 to 0 :
XEQ G

Code:


001 LBL F
    CL SIGMA   // clears stats registers
    0
    STO T      // stores 0 in the cumulative registers
    STO I
006 RCL (I)
    STO + T    // adds the number of draws of the number i (0..99) in the cumulative register
    RCL T
    FS? 0      // uses cumulative register if flag 0 is not set, 
    x <> y     // otherwise directly uses the number of draws for number i
    1
    RCL + I
    STO I
    SIGMA +    // adds on stats register the couple [i, draws(i-1)] for flag 0 on, otherwise it's [i, Sum of the draws(0..i-1)]
    RCL I
    RCL M
    x > y ?
    GTO F006   // loops if i is less than M (0..99)
    RCL S      // displays basis number generator and stops
    RTN

Usage of LBL F to insert the results of LBL H in the stats registers :
2 axes :
1) to obtain the standard deviations
SF 0
XEQ F
then Sy and oy from the keyboard (blue arrow and +)
2) to evaluate the quality of the linear regression
CF 0
XEQ F
then L.R results with r and m from the keyboard (yellow arrow and -)


Finally, with this set of programs and the proposed sequence of steps :
--> I examine the result of a distribution of 1000 random generations of numbers based on 147 or 997
--> I summary evaluate the quality of this distribution

What do I obtain ?
I think that gives a better correlation for the random numbers obtained on the basis of generator 997 than on the basis of 147
and also it gives less disparity for the total of the draws of each possible number.
That is, the output of numbers over the entire range is more consistent using the generator based on the 997 than on the 147.

Therefore, I thought at first it was better to choose a high number 997 > 147
So I have also tested 23, 653, 1283, 1999, 9929, 9931, 62927, 689459 and 851801
In the reality, there are disparate results !
You should see by yourself. I just give you 3 results on 1000 and 10000 draws each.

Code:


           loops    Sy      oy        r             m
     147  1000     3.54    3.52     0.99987    10.1828
     997  1000     3.19    3.17     0.99988     9.9682
837799  1000     0.00    0.00     1.00000    10.0000
     147 10000    10.78   10.73    0.99996    99.8426
     997 10000    10.21   10.16    0.99995   100.2374
837799 10000     0.00   0.00     1.00000   100.0000

Now, in my turn, I have a question!
Look at the results and see how idyllic the generation obtained on the basis of the number 837799 is ...
Could somebody say how is that?


Keep you healthy !

[EdS2]

With 100 values sampled 1000 times, you shouldn't expect exactly 10 of each value: that would indicate a non-random process, because it's a very improbable result.

(Although you should expect the average to be somewhat close to 10.)

Someone with more knowledge than I have might be able to say what the expected distribution is, and what its characteristics are. You'd then be able to compare your results with the expected, and with even more knowledge, say something about "how random" your process is.

In the absence of analytical techniques, I think it would be fair to repeat the overall experiment, 10 or 100 times, and see how the means and standard deviations vary. You would of course use the same algorithm but a different seed.

It's certainly interesting that some choices of parameter, for the very same algorithm, can give results which are better or worse than others.

[Namir]

(12-08-2020 06:57 AM)Gamo Wrote:  Recently read an old book that teach kid "Math Algorithm" and one of the topic was about the "Random Number Generator."

This book mention using the 147 Algorithm to generate Random Integer.

The steps on how to generate random integer is similar to the 997

Is there any much difference of the random output with these 147 and 997 ??

Thanks

Gamo

Using 997 give suprisingly good results. I gave a presentation at the HHC2017 meeting (you can view the presentation on YouTube, click here) about new PRNG algorithms and looked at legacy PRNGs used by HP.The 997 algorithm stood out among the legacy PRNGs.

The study I conducted for the HHC2017 generated a BILLION random numbers and ran for several weeks on multiple PCs.

Namir

[Nihotte(lma)]

(12-08-2020 06:57 AM)Gamo Wrote:  Recently read an old book that teach kid "Math Algorithm" and one of the topic was about the "Random Number Generator."

This book mention using the 147 Algorithm to generate Random Integer.

The steps on how to generate random integer is similar to the 997

Is there any much difference of the random output with these 147 and 997 ??

Thanks

Gamo

Hi Gamo !

Our dear HP11C is not out of the game or simply forgotten.
I suggest you a version of the test module suitable for this machine.

I have made it in 2 modules only

A first one for the generation of the distribution, based on 147 or 997 for example.
Here it is.

Code:


** f  LBL  A
     g Clx
     STO  . 0
     STO  . 1
     STO  . 2
     STO  . 3
     STO  . 4
     STO  . 5
     RCL  7
     STO  0
     f  π
     f  FRAC
     STO  1
  * f  LBL  0
     RCL  1
     RCL  8
     x
     f  FRAC
     STO  1
     RCL  6
     x
     g  INT
     1
     0
     +
     STO  I
     EEX
     STO  +  (i)
     STO  -  0
     RCL  0
     g  x > 0
     GTO  0
     g  RTN

With this usage :

6 STO 6 : for draws from 0 to 5
1200 STO 7 : for 1200 draws (you can begin with 120 to see)
997 STO 8 : to test 997, for example
GSB A

You can read the results of the draws by this sequence :

RCL . 0
RCL . 1
RCL . 2
RCL . 3
RCL . 4
RCL . 5


The 2nd one puts the results in the stats registers of the HP11C
Here it is.

Code:


 ** f  LBL  A
      f  CLEAR  Σ
      STO  9
   * f  LBL  1
      1
      0
      RCL  0
      +
      STO  I
      RCL  (i)
      STO  +  9
      RCL  9
      g  F ?  0
      x <> y
      RCL  0
      EEX
      +
      Σ+
      RCL  0
      RCL  6
      f  x > y
      GTO  1
      g  RTN

This is the usage :

g CF 0
GSB E
- f ŷ, r and x<>y
- f L.R. and x<>y

g SF 0
GSB E
g s and x<>y
g x and x<>y

Just a word on the results !
Curiously, the results I get on the HP11C seem better for the based 147 distribution than this one for 997 !

With 997 for 6 possibilities on 1200 draws, I get these data in registers :
RCL . 0 : 187
RCL . 1 : 184
RCL . 2 : 222
RCL . 3 : 192
RCL . 4 : 223
RCL . 5 : 192

With 147 for 6 possibilities on 1200 draws, I get this data in registers :
RCL . 0 : 210
RCL . 1 : 202
RCL . 2 : 191
RCL . 3 : 195
RCL . 4 : 203
RCL . 5 : 199



One more small precision about the program :
It supports distribution with 10 numbers rather than 6 but you have to add the next steps at the right position :
STO . 6
STO . 7
STO . 8
STO . 9
under
g Clx
STO . 0
STO . 1
STO . 2
STO . 3
STO . 4
STO . 5
and modify the content of the R6 by 10 rather than 6 !

Beware of the possible adaptation for the HP15C : Σ registers are R0..5 on the HP11C


Keep you healthy !