The design
The idea behind this exceedingly simple algorithm is inspired by the simplicity of the Mersenne twister. The basic design philosophy of the mersenne twister is that it’s based on a large array of pre-computed “really random” numbers. This works as a large source of entropy to feed to some other algorithm(In particular, a Linear Congruential Generator) so that you don’t have to rely on the entropy from the single number fed to it as a seed.
Stealing that basic premise, but not using a linear congruential generator, my idea was the following:
- Take the seed as state(Called input), and keep an index in state as 0 (Called Index). Let arr be a pre-computed list of random numbers
- input = input xor arr[index]
- ROL or ROR input arr[index] by *input
- arr[index] = input
- index = input % len arr (If it’s a power of two, you only need a bitmask. This is probably how it’ll actually be implemented)
- jump to 2, until satisfied with # iterations
Some questions:
- How well does this work as a random number generator (GIven the output at the end is input). Could you test and analyse the algorithm and get a semi-definitive answer?
- How efficient would this be in terms of speed? Would this be slower than the mersenne twister?
- What are some ways to improve this without making it much more complicated? I was considering having the ROL after storing input, instead of before, but I thought that might end up limiting entropy because of how the operations worked. Here are the results of the dieharder tests applied to this algorithm. All in all, for my first attempt at prng, I think it did pretty well:
| test_name | ntup | tsamples | psamples | pvalue | assessment |
|---|---|---|---|---|---|
| diehard_birthdays | 0 | 100 | 100 | 0.98356356 | PASSED |
| diehard_operm5 | 0 | 1000000 | 100 | 0.58750898 | PASSED |
| diehard_rank_32x32 | 0 | 40000 | 100 | 0.49593991 | PASSED |
| diehard_rank_6x8 | 0 | 100000 | 100 | 0.97122000 | PASSED |
| diehard_bitstream | 0 | 2097152 | 100 | 0.87549025 | PASSED |
| diehard_opso | 0 | 2097152 | 100 | 0.69945561 | PASSED |
| diehard_oqso | 0 | 2097152 | 100 | 0.55905649 | PASSED |
| diehard_dna | 0 | 2097152 | 100 | 0.65120873 | PASSED |
| diehard_count_1s_str | 0 | 256000 | 100 | 0.48734833 | PASSED |
| diehard_count_1s_byt | 0 | 256000 | 100 | 0.59092515 | PASSED |
| diehard_parking_lot | 0 | 12000 | 100 | 0.35536156 | PASSED |
| diehard_2dsphere | 2 | 8000 | 100 | 0.74794961 | PASSED |
| diehard_3dsphere | 3 | 4000 | 100 | 0.22163148 | PASSED |
| diehard_squeeze | 0 | 100000 | 100 | 0.75768713 | PASSED |
| diehard_sums | 0 | 100 | 100 | 0.36175030 | PASSED |
| diehard_runs | 0 | 100000 | 100 | 0.77452905 | PASSED |
| diehard_runs | 0 | 100000 | 100 | 0.72743300 | PASSED |
| diehard_craps | 0 | 200000 | 100 | 0.66498955 | PASSED |
| diehard_craps | 0 | 200000 | 100 | 0.64124851 | PASSED |
| marsaglia_tsang_gcd | 0 | 10000000 | 100 | 0.00000079 | FAILED |
| marsaglia_tsang_gcd | 0 | 10000000 | 100 | 0.02876877 | PASSED |
| sts_monobit | 1 | 100000 | 100 | 0.28733001 | PASSED |
| sts_runs | 2 | 100000 | 100 | 0.97313221 | PASSED |
| sts_serial | 1 | 100000 | 100 | 0.79560756 | PASSED |
| sts_serial | 2 | 100000 | 100 | 0.50918839 | PASSED |
| sts_serial | 3 | 100000 | 100 | 0.72861109 | PASSED |
| sts_serial | 3 | 100000 | 100 | 0.76609771 | PASSED |
| sts_serial | 4 | 100000 | 100 | 0.35115125 | PASSED |
| sts_serial | 4 | 100000 | 100 | 0.75720281 | PASSED |
| sts_serial | 5 | 100000 | 100 | 0.34961276 | PASSED |
| sts_serial | 5 | 100000 | 100 | 0.66295337 | PASSED |
| sts_serial | 6 | 100000 | 100 | 0.26082606 | PASSED |
| sts_serial | 6 | 100000 | 100 | 0.44561287 | PASSED |
| sts_serial | 7 | 100000 | 100 | 0.09372991 | PASSED |
| sts_serial | 7 | 100000 | 100 | 0.26405456 | PASSED |
| sts_serial | 8 | 100000 | 100 | 0.24357032 | PASSED |
| sts_serial | 8 | 100000 | 100 | 0.64314616 | PASSED |
| sts_serial | 9 | 100000 | 100 | 0.96798350 | PASSED |
| sts_serial | 9 | 100000 | 100 | 0.29572749 | PASSED |
| sts_serial | 10 | 100000 | 100 | 0.62468883 | PASSED |
| sts_serial | 10 | 100000 | 100 | 0.92104178 | PASSED |
| sts_serial | 11 | 100000 | 100 | 0.96622038 | PASSED |
| sts_serial | 11 | 100000 | 100 | 0.56325088 | PASSED |
| sts_serial | 12 | 100000 | 100 | 0.84488898 | PASSED |
| sts_serial | 12 | 100000 | 100 | 0.89353988 | PASSED |
| sts_serial | 13 | 100000 | 100 | 0.70215000 | PASSED |
| sts_serial | 13 | 100000 | 100 | 0.41082605 | PASSED |
| sts_serial | 14 | 100000 | 100 | 0.66789572 | PASSED |
| sts_serial | 14 | 100000 | 100 | 0.63501686 | PASSED |
| sts_serial | 15 | 100000 | 100 | 0.97273385 | PASSED |
| sts_serial | 15 | 100000 | 100 | 0.41314752 | PASSED |
| sts_serial | 16 | 100000 | 100 | 0.77008188 | PASSED |
| sts_serial | 16 | 100000 | 100 | 0.46351042 | PASSED |
| rgb_bitdist | 1 | 100000 | 100 | 0.55039110 | PASSED |
| rgb_bitdist | 2 | 100000 | 100 | 0.69463258 | PASSED |
| rgb_bitdist | 3 | 100000 | 100 | 0.53884696 | PASSED |
| rgb_bitdist | 4 | 100000 | 100 | 0.96176534 | PASSED |
| rgb_bitdist | 5 | 100000 | 100 | 0.84241668 | PASSED |
| rgb_bitdist | 6 | 100000 | 100 | 0.89273771 | PASSED |
| rgb_bitdist | 7 | 100000 | 100 | 0.27869261 | PASSED |
| rgb_bitdist | 8 | 100000 | 100 | 0.99910785 | WEAK |
| rgb_bitdist | 9 | 100000 | 100 | 0.61862080 | PASSED |
| rgb_bitdist | 10 | 100000 | 100 | 0.49293572 | PASSED |
| rgb_bitdist | 11 | 100000 | 100 | 0.19763570 | PASSED |
| rgb_bitdist | 12 | 100000 | 100 | 0.99748606 | WEAK |
| rgb_minimum_distance | 2 | 10000 | 1000 | 0.27917753 | PASSED |
| rgb_minimum_distance | 3 | 10000 | 1000 | 0.26740171 | PASSED |
| rgb_minimum_distance | 4 | 10000 | 1000 | 0.64313190 | PASSED |
| rgb_minimum_distance | 5 | 10000 | 1000 | 0.03399061 | PASSED |
| rgb_permutations | 2 | 100000 | 100 | 0.06407396 | PASSED |
| rgb_permutations | 3 | 100000 | 100 | 0.23247355 | PASSED |
| rgb_permutations | 4 | 100000 | 100 | 0.84328723 | PASSED |
| rgb_permutations | 5 | 100000 | 100 | 0.96563949 | PASSED |
| rgb_lagged_sum | 0 | 1000000 | 100 | 0.96738945 | PASSED |
| rgb_lagged_sum | 1 | 1000000 | 100 | 0.80570241 | PASSED |
| rgb_lagged_sum | 2 | 1000000 | 100 | 0.73346401 | PASSED |
| rgb_lagged_sum | 3 | 1000000 | 100 | 0.17319405 | PASSED |
| rgb_lagged_sum | 4 | 1000000 | 100 | 0.66984255 | PASSED |
| rgb_lagged_sum | 5 | 1000000 | 100 | 0.93320792 | PASSED |
| rgb_lagged_sum | 6 | 1000000 | 100 | 0.48806544 | PASSED |
| rgb_lagged_sum | 7 | 1000000 | 100 | 0.02161892 | PASSED |
| rgb_lagged_sum | 8 | 1000000 | 100 | 0.56950881 | PASSED |
| rgb_lagged_sum | 9 | 1000000 | 100 | 0.70158921 | PASSED |
| rgb_lagged_sum | 10 | 1000000 | 100 | 0.36567836 | PASSED |
| rgb_lagged_sum | 11 | 1000000 | 100 | 0.05397063 | PASSED |
| rgb_lagged_sum | 12 | 1000000 | 100 | 0.84515823 | PASSED |
| rgb_lagged_sum | 13 | 1000000 | 100 | 0.34851872 | PASSED |
| rgb_lagged_sum | 14 | 1000000 | 100 | 0.00595100 | PASSED |
| rgb_lagged_sum | 15 | 1000000 | 100 | 0.00659663 | PASSED |
| rgb_lagged_sum | 16 | 1000000 | 100 | 0.91978909 | PASSED |
| rgb_lagged_sum | 17 | 1000000 | 100 | 0.60627753 | PASSED |
| rgb_lagged_sum | 18 | 1000000 | 100 | 0.99545301 | WEAK |
| rgb_lagged_sum | 19 | 1000000 | 100 | 0.00415340 | WEAK |
| rgb_lagged_sum | 20 | 1000000 | 100 | 0.59316496 | PASSED |
| rgb_lagged_sum | 21 | 1000000 | 100 | 0.95138572 | PASSED |
| rgb_lagged_sum | 22 | 1000000 | 100 | 0.66672474 | PASSED |
| rgb_lagged_sum | 23 | 1000000 | 100 | 0.00159695 | WEAK |
| rgb_lagged_sum | 24 | 1000000 | 100 | 0.87339649 | PASSED |
| rgb_lagged_sum | 25 | 1000000 | 100 | 0.56168925 | PASSED |
| rgb_lagged_sum | 26 | 1000000 | 100 | 0.85981205 | PASSED |
| rgb_lagged_sum | 27 | 1000000 | 100 | 0.17565003 | PASSED |
| rgb_lagged_sum | 28 | 1000000 | 100 | 0.42078003 | PASSED |
| rgb_lagged_sum | 29 | 1000000 | 100 | 0.01033951 | PASSED |
| rgb_lagged_sum | 30 | 1000000 | 100 | 0.40451497 | PASSED |
| rgb_lagged_sum | 31 | 1000000 | 100 | 0.00000190 | WEAK |
| rgb_lagged_sum | 32 | 1000000 | 100 | 0.22031260 | PASSED |
| rgb_kstest_test | 0 | 10000 | 1000 | 0.35700639 | PASSED |
| dab_bytedistrib | 0 | 51200000 | 1 | 0.00000000 | FAILED |
| dab_dct | 256 | 50000 | 1 | 0.91065627 | PASSED |
| dab_filltree | 32 | 15000000 | 1 | 0.92374295 | PASSED |
| dab_filltree | 32 | 15000000 | 1 | 0.95349424 | PASSED |
| dab_filltree2 | 0 | 5000000 | 1 | 0.76532971 | PASSED |
| dab_filltree2 | 1 | 5000000 | 1 | 0.97301100 | PASSED |
| dab_monobit2 | 12 | 65000000 | 1 | 0.62278368 | PASSED |
An interesting result from dab_bytedistrib. 0.000000, huh? The fact that this gives good results(At least, in other areas) tells me that it’s properly taking advantage of the entropy from the small array; these are the results from an array of just 128 64-bit numbers. If it can do this well with so little entropy compared to the samples the test takes, it should mean it’s pretty solid.
One improvement I made was to ROL based on the previous number(Or 0 if no previous number) rather than by the current one. This seemed to break small cycles a lot better for some reason.