New PRNG method

[Namir]

I present a new PRNG that I implemented on an HP41CX emulator. The following program includes the test code and the code for the PRNG in LBL "RAND". The algorithm basically takes a random number and extracts the five leading digits and add them to the remaining digits (using scaling). The method adds pi to the random number to ensure enough decimal places. It allso adds pi at the end to ensure enough digits. The test returns results close to the mean of 0.5 and standard deviation of 0.288. An example for the results is a mean of 0.50047 and standard deviation of 0.28882.

Code:

1    LBL AA
2    LBL A
3    "SEED/^ITERS"
4    PROMPT
5    STO 01
6    X<>Y
7    FRC
8    ABS
9    STO 00
10    SigmaREG 94
11    CLSigma
12    LBL 00
13    XEQ "RAND"
14    STO  02
15    XEQ "RAND"
16    Sigma+
17    DSE 01
18    GTO 00
19    MEAN
20    +
21    2
22    /
23    PROMPT
24    SDEV
25    +
26    2
27    /
28    RTN
29    LBL RAND
30    RCL 00
31    PI
32    +
33    FRC
34    1E5
35    *
36    STO Y
37    INT
38    1E5
39    /
40    X<>Y
41    FRC
42    +
43    PI
44    +
45    FRC
46    STO 00
47    RTN

[Albert Chan]

Because New PRNG only do shift + addition, it is not very random.

Chi Square percentage number are extremely weak. (i.e. not random)
We want 10% to 90%, close to 50% is excellent (see ent.exe Chi-square Test)

I reuse ent.lua to test randomness
This use 10-digits integer random state, to avoid binary to decimal float conversion errors.

Code:

local s = floor(math.random()*1e10)
local k = floor((pi-3)*1e10)
local r = function(n) 
    local t = s + k
    s = t % 1e5
    s = (t-s + s*1e5 + k) % 1e10
    return floor(n * s/1e10)
end

Note: seed = 0 --> s = floor(0.8438413544573831 * 1e10) = 8438413544

C:\LuaJIT\bit>run ent.lua 0 | ent
seed = 0
Entropy = 7.999983 bits per byte.

Optimum compression would reduce the size
of this 1000000 byte file by 0 percent.

Chi square distribution for 1000000 samples is 23.65, and randomly
would exceed this value more than than 99.99 percent of the times.

Arithmetic mean value of data bytes is 127.5018 (127.5 = random).
Monte Carlo value for Pi is 3.281245125 (error 4.45 percent).
Serial correlation coefficient is 0.091133 (totally uncorrelated = 0.0).

---

I don't quite understand your proposed algorithm.

(s + pi) % 1 = 0.xxxxxyyyyy
next(s) = (0.xxxxx + 0.yyyyy + pi) % 1

Above next(s) least sig. digts always matched pi's. Perhaps more mixing is better?

next(s) = (0.xxxxxyyyyy + 0.yyyyy + pi) % 1

Patch is trivial

Code:

< s = (t-s + s*1e5 + k) % 1e10
> s = (t + s*1e5 + k) % 1e10

C:\LuaJIT\bit>run ent.lua 0 | ent
seed = 0
Entropy = 7.999923 bits per byte.

Optimum compression would reduce the size
of this 1000000 byte file by 0 percent.

Chi square distribution for 1000000 samples is 106.69, and randomly
would exceed this value more than than 99.99 percent of the times.

Arithmetic mean value of data bytes is 127.4946 (127.5 = random).
Monte Carlo value for Pi is 3.140748563 (error 0.03 percent).
Serial correlation coefficient is -0.000728 (totally uncorrelated = 0.0).

[Namir]

Thanks Albert. I will also run the algorithm with my more extensive multi-stat tests.

Namir

[Namir]

Hello Albert,

Can you run your randomness test calculations using 1000 samples. The PRNG that I am proposing is for calculators. Simulations in calculators usually need limited number of random numbers.

Namir

[Albert Chan]

(09-12-2024 10:03 PM)Namir Wrote:  Can you run your randomness test calculations using 1000 samples.

Sure. But with tiny samples, random test mean very little.
I wasn't sure what your algorithm is, so I try both ways.

Code:

(s + pi) % 1 = 0.xxxxxyyyyy
next(s) = (0.xxxxx + 0.yyyyy + pi) % 1

seed = 0
Entropy = 7.919917 bits per byte.

Optimum compression would reduce the size
of this 1000 byte file by 1 percent.

Chi square distribution for 1000 samples is 122.82, and randomly
would exceed this value more than than 99.99 percent of the times.

Arithmetic mean value of data bytes is 127.2360 (127.5 = random).
Monte Carlo value for Pi is 3.253012048 (error 3.55 percent).
Serial correlation coefficient is 0.091111 (totally uncorrelated = 0.0).

Code:

(s + pi) % 1 = 0.xxxxxyyyyy
next(s) = (0.xxxxxyyyyy + 0.yyyyy + pi) % 1

seed = 0
Entropy = 7.800628 bits per byte.

Optimum compression would reduce the size
of this 1000 byte file by 2 percent.

Chi square distribution for 1000 samples is 260.03, and randomly
would exceed this value 40.10 percent of the times.

Arithmetic mean value of data bytes is 125.7310 (127.5 = random).
Monte Carlo value for Pi is 3.325301205 (error 5.85 percent).
Serial correlation coefficient is -0.004294 (totally uncorrelated = 0.0).

[Albert Chan]

Code:

(s + pi) % 1 = 0.xxxxxyyyyy
next(s) = (0.xxxxxyyyyy + 0.yyyyy + pi) % 1

Let's say this version is better, with more mixing of least sig. digits.
We can scale it so that we work with integer math.

K = 1415926535
next(S) = ((S+K) + (S+K)*1e5 + K) % 1e10 = (100001*S + 100002*K) % 1e10

This is just simple linear congruential generator (scaling/offset constants may be improved)

[ttw]

As I read the method (didn't do the code), the only source of new data is the repeated addition of Pi. This produces something like a Kronecker-Weyl-Richtmeyer sequence using Pi as the irrational generator. One gets a uniformly distributed sequence, not a pseudo-random sequence. Two obvious problems are that the terms of the sequence are highly correlated and the discrepancy (counts in intervals vs interval sizes) is too uniform.

To some extent, this can be mitigated by something similar to the generators I've presented here somewhere. One needs to take several sequences to defeat the correlation. Quick example: let a1,a2,a3...,ak be a set of k irrationals that are linearly independent over the rationals; I like the square roots of the primes, the square-free numbers, or (my favorite) the fractional parts of the square roots of primes, P, of the form: 4*j+1. Then take Frac((Sqrt(P))+1)/2. Start with a set of initial values (zero is good as is any other number between 0 and 1), x1,x2,x3...xk. One forms a sequence xj=xj+aj mod 1, equivalent to xj=Frac(xj+aj). It's fairly fast.

This construction is provably uniformly distributed in the k-cube. Then one adds the numbers for the same number of steps and again takes the fractional part. Using k terms, the k-fold autocorrelation must quickly converge to 0.

For various reasons, I like to use continued fractions close to the irrationals; it allows for exact arithmetic regardless of the floating point style used on a computer and can be completely portable.

Homework: try the sequences formed from (Sqrt(P)+1)/2, with P being 5,13,17,39,37,41,...

[Namir]

Hi Albert,

I tested the algorithm with my extensive-testing app in Matlab (rounding the random numbers to 10 digits) and the results are poor. I saw high auto correlation between the numbers.

Namir

[AnnoyedOne]

Personally I've used shift register PRNG's in the past (on computers).

Harder to implement on a programmable calculator.

https://github.com/russm/lfsr64/blob/mas...app052.pdf

A1

PS: One can always use https://www.random.org to obtain true random numbers.

Quote:The randomness comes from atmospheric noise, which for many purposes is better than the pseudo-random number algorithms typically used in computer programs.

[Namir]

The PRNG method hat I proposed generated random numbers with good mean and standard deviations. I obtained these results using an HP-4CX emulator on my iPhone. These results were initially encouraging. But when I ran the algorithm in my Matlab suite of statistical tests, the overall result (which I called the penalty factor) was very high, indicating that the quality of the random numbers generated was poor. So, the proposed method goes into the algorthims' trash can!

[ttw]

I probably have several hundred attempts at pseudo-random number generators; not to mention some quasi-random stuff. Almost all (maybe 3 or 4) failed my quick tests. It's normal (sometimes the distributions are too.)

[Namir]

(09-15-2024 04:15 PM)ttw Wrote:  I probably have several hundred attempts at pseudo-random number generators; not to mention some quasi-random stuff. Almost all (maybe 3 or 4) failed my quick tests. It's normal (sometimes the distributions are too.)

Same experience here. I do a quick preliminary test to calculate the mean and standard deviation, usig an HP-41CX emulator. if the results are encouraging then I use my full suite of tests.

Namir