# hp41programs

Alea Random Number Generators for the HP-41

Overview

-Several pseudo random number generators are listed on this web page:
-"RNG1" "RNG2" "RNG3" work on every HP-41.
-"RNG4" & the M-Code routine RAND require a Time-Module.
-Finally, the last program is an attempt to play ( win? ) the lottery...

Program#1

-A well known RNG is given by the formula:  xn+1 = FRC ( 9821 xn + 0.211327 ) which provides 1 million random numbers.
-The following program gives 1,000,000,000  random numbers r  ( 0 <= r < 1 ). The formula  xn+1 = FRC ( 98 xn + 0.236067977 ) is used.
-The coefficient 98 = 43,046,721 may be replaced by  a   where  a = 1 ( mod 20 )
and  0.236067977  may be replaced by  b  where   b*109 is not divisible by 2 or 5.

 01  LBL "RNG1" 02  9 03  ENTER^ 04  ENTER^ 05  R^ 06  * 07  FRC             08  * 09  FRC 10  * 11  FRC 12  * 13  FRC             14  * 15  FRC 16  * 17  FRC 18  * 19  FRC             20  * 21  FRC 22  5 23  SQRT 24  + 25  FRC             26  END

( 35 bytes / SIZE 001 )

 STACK INPUTS OUTPUTS X xn xn+1

Example:

0.2   XEQ "RNG1"  yields  0.436067977
R/S    0.779021394   ... etc ...

Program#2

-"RNG2" provides 9,999,999,996 random numbers with the formula:  xn+1 = ( 1059 xn ) MOD p   where p = 9,999,999,967 is the greatest prime < 1010
xn are integers between 0 and p ( exclusive ) which are then divided by p to be reduced to a number between 0 and 1.
-This routine works well because the MOD function gives exact results even when the operands are greater than 1010.
-Actually, the exponent 59 may be replaced by any integer m provided m is relatively prime to p-1 = 2*3*11*457*331543
but I don't know what is the best choice.
-Unlike "RNG1" and other routines based upon the same type of formulae, the least significant digits don't go through any cycle of ten, one hundred and so on.
-Register R00 is used to store the different  xn integers.

 01  LBL "RNG2"  02  RCL 00  03   E59  04  *  05  10  06  10^X  07  33  08  -  09  MOD  10  STO 00  11  LASTX  12  /  13  END

( 26 bytes / SIZE 001 )

 STACK INPUTS OUTPUTS X / 0 < r < 1

Example:

1  STO 00
XEQ "RNG2" gives  0.3129146797   ( and R00 = 3129146787 = 1059 ( mod p ) )
R/S                   0.6904570204    ( R00 = 6904570181 ) ... etc ...

-Actually if p is a prime,  ( Z/pZ-{0} ; * ) is a group
and if a is an integer,  the number of distinct elements in the subset   { 1 ; a ; a2 ; ....... ; ak ; .... } ( mod p )   divides  p-1
-If  p-1 is the smallest positive integer q such that aq = 1 ( mod p ) , then the sequence   a ; a2 ; ....... ; ak ; .... ; ap-1 ( mod p )
is a permutation of  1 ; 2 ; ...... ; p-1
-In particular, if  p = 2p' + 1  where p' is also a prime, and if ap' is not equal to 1 ( mod p )  then  a  satisfies the required property.
-For instance,  p = 7,841,296,787 = 2*3,920,648,393 + 1              7,841,296,787 and 3,920,648,393 are primes and  -1024 = 4,851,307,369  ( mod p )
satisfies  (-1024)p' = -1  therefore the routine:

E24
*
CHS
7841296787
MOD                  gives  7,841,296,786  random integers

-These ideas may be used to create your own RNG.

Program#3

-The following algorithm is given by Clifford Pickover in "Keys to Infinity" ( John Wiley & Sons )  ISBN 0-471-11857-5

 01  LBL "RNG3"  02  LN  03   E2  04  *  05  1  06  MOD  07  END

( 17 bytes / SIZE 001 )

 STACK INPUTS OUTPUTS X xn xn+1

Example:

0.1   XEQ "RNG3" produces  0.74149070
R/S                          0.09073404  ... etc ...

Program#4

 01  LBL "RNG4"  02  DATE  03  TIME  04  +  05   E49  06  *  07  PI  08  MOD  09  LN1+X  10  R-D  11  FRC  12  END

( 25 bytes / SIZE 000 )

 STACK INPUTS OUTPUTS X / 0 < r < 1

-I cannot give any example since the result depends on the instant you press R/S

M-Code Routine

-This M-Code routine uses the TIME module - or an HP41-CX

084  "D"
00E  "N"
001  "A"
012  "R"
130  LDI S&X
010  16d
270  RAMSLCT
130  LDI S&X
0FB 251d
3F0  PRPH SLCT
3E8  WRIT 15(e)
1BC RCR 11
046  C=0 S&X
270  RAMSLCT
05E  C=0 MS
130  LDI S&X
041  65d
2A0  SETDEC
10E  A=C ALL
04E  C=0 ALL
35C  PT=12
1D0  LD@PT- 7
210  LD@PT- 8
110  LD@PT- 4
050  LD@PT- 1
090  LD@PT- 2
250  LD@PT- 9
190  LD@PT- 6
1D0 LD@PT- 7
210  LD@PT- 8
1D0  LD@PT- 7
044  CLRF 4
070  N=C ALL
171  ?NCXQ
064  195C
10E  A=C ALL
0B0  C=N ALL
261  ?NCXQ
060  1898
0E8  WRIT 3(X)
3E0  RTN

( 42 words / SIZE 000 )

-"RAND" uses no data register
-XEQ "RAND" returns a pseudo-random number ( between 0 and 1 ) in X-register
-The previous content of register X is overwritten.
-Execution time = 0.22 second

Winning the Lottery?

-If you need, for instance, 7 integers between 1 and 49 , you can use 7 random numbers between 0 and 1,
multiply them by 49 , add 1 and take the integer part of the result.
-The small routine hereafter is another possibility, if you accept to calculate the integer part in your mind:

 01  LBL "\$\$\$"  02  R-D  03  49  04  MOD  05  1  06  +  07  END

( 16 bytes / SIZE 000 )

 STACK INPUTS OUTPUTS X r 0 < N < 50

Example:

41  XEQ "\$\$\$"  yields   47.1270
R/S                      6.1759
R/S                    11.8535
R/S                    43.1567
R/S                    23.6963
R/S                    35.6962
R/S                    37.2418         suggesting     47-06-11-43-23-35-37

Notes:

1-I'm not a statistician and I can't assure all these RNGs would stand up to sophisticated tests, but one may use his imagination in devising variations.
2-If you win one million dollars thanks to one of these programs, I accept to share the jackpot...