Best two PRNG for calculators

[Namir]

I have finished my little research (and literally days of non-stop number crunching) regarding good PRNG for calculators. The best two PRNGs I found are:

Best is:

u(i) = Frac((u(i-1) + 1 / (phi + u(i-2))) * 997)

and

u(i) = Frac((u(i-1) + 1/phi) * 997)

Where phi = 1.61803398875 (= the Golden Ratio)

Using 997 does not come as a surprise for many. The following PRNG comes in an honorary mention:

u(i) = Frac(u(i) * 4357)

The problem with the last one (and with u(i) = Frac(u(i-1) * 997)) is that if u(i-1) is an integer, the PRNG generates a stream of zeros!!!

Enjoy!

Namir

PS: A Cowboy's work is never done!

[Paul Dale]

(08-30-2014 11:57 AM)Namir Wrote:  I have finished my little research (and literally days of non-stop number crunching) regarding good PRNG for calculators. The best two PRNGs I found are:

Care to elucidate on your methodology for testing these for randomness?
There is a mass of statistical literature and tests available for doing just this.

Quote:The problem with the last one (and with u(i) = Frac(u(i-1) * 997)) is that if u(i-1) is an integer, the PRNG generates a stream of zeros!!!

This isn't a significant shortcoming. I'd be more concerned about a seed that when multiplied by 4357 or 997 became an integer -- this can be readily checked for to determine if it is possible or not. Mitigation is also straightforward: x=0? PI after loading \(u_{i-1}\)


- Pauli

[robert rozee]

someone might care to look at fibonacci sequences, where:
1. f(0) and f(1) are the initial (positive integer) seeds;
2. f(0) and f(1) are not allowed to both be even.

as i recall, if the word size used is n, then the sequence length (before repeating) is something like (2^n)*1.5 with the parity of the next value at each step forms the output. ie, one pseudo-random bit is generated for each step.

i played around with this many many years ago, and got some interesting results. all maths is positive integers based, with overflow bits abandoned. it is quite simple to implement the algorithm in dedicated hardware, which was a key requirement at the time. the application was cryptography.

rob :-)

[Namir]

(08-30-2014 11:38 PM)Paul Dale Wrote:  Care to elucidate on your methodology for testing these for randomness?
There is a mass of statistical literature and tests available for doing just this.
- Pauli

I am aware that there is a massive suite of tests. I chose a subset of tests for a variety of reason (not to mention time, practicality, and not being paid to do this). I use Excel (and Excel VBA code) to test PRNG functions in groups of 8. I perform the following steps:

1) Generate 32 runs for each PRNG function.
2) Each run generates 100,000 numbers.
3) I calculate and observe the following statistics for each 100,000 numbers:
a. The mean value.
b. The standard deviation.
c. The auto-correlation for the first 30 lags. I record the minimum value, maximum value and sum of the auto-correlations.
d. The Chi-square stat for the histograms with bins of 0.1 size. The ideal value for each bin is 1000.
e. The Chi-square stat for the histograms with bins of 0.05 size. The ideal value for each bin is 500.
4) I calculate an empirical factor based on the mean, standard deviation, minimum auto-correlation, maximum auto-correlation, sum of auto-correlations, Chi-Square for the 10-bins histogram data, Chi-Square for the 20-bin histogram data. The empirical factors tend to penalize a run of random numbers for deviating from expected values.
5) I rank the results based on the empirical factors, seeking the smallest rank values. I calculate the mean, standard deviation, minimum, maximum, and confidence interval for the 32 factor values for each PRNG function.
6) I select the minim mean factor value.

[Paul Dale]

A beginning at least

For those who aren't aware there are some good sources of tests for randomness. Donald Knuth's The Art of Computer Programming Volume 2: Seminumerical Algorithms is a good beginning. There are also prewritten randomness test suites. Dieharder e.g.


- Pauli