fliptag 3.1 - A Pseudo Random Number Generator (Verified)

[minxomat]

PRNG

Here's a small PRNG called fliptag. It uses mostly linear math and its state can be completely kept within only 6 "registers" and the implementation is only 27 lines of code long.

Verification

I ran ent, DIEHARD and the NIST.GOV test suite against it (though I only did all the tests for one fixed seed). I re-ran ent with this, because this implementation has a system-time dependent seed.

fliptag has 4 seed parameters, of which 3 are optional. The first one is the genesis seed and determines the starting state. Because this seed is very sensitive to small decimal changes, the current system tickcount (modified) is used in addition to the current system time. (AutoIts MT uses time(NULL))

Here are some sample ent results from the AutoIt test suite, which generates a 1,5 MB file from random bytes:

 

Conclusion

1. Entropy

A truly random sequence has an entropy value of 8.0. This is however not achievable by any software PRNG. Both PRNG are on par and have a very respectable entropy value.

2. Compression

A dense file (with high entropy) cannot be compressed. Both PRNG achieve perfect scores.

3. Chi²

The chi-square test is the most commonly used test for the randomness of data, and is extremely sensitive to errors in pseudorandom sequence generators. The chi-square distribution is calculated for the stream of bytes in the file and expressed as an absolute number and a percentage which indicates how frequently a truly random sequence would exceed the value calculated. We interpret the percentage as the degree to which the sequence tested is suspected of being non-random. If the percentage is greater than 99% or less than 1%, the sequence is almost certainly not random. If the percentage is between 99% and 95% or between 1% and 5%, the sequence is suspect. Percentages between 90% and 95% and 5% and 10% indicate the sequence is “almost suspect”.

Both PRNGs achieve very good results. For comparison, Unix' rand() achieves a catastrophic 0.01, a Park & Miller PRNG will achieve roughly 97.5, while a truly - physical - random sequence will result in a Chi² score of about 40.9. 

4. Arithmetic mean value

Truly random sequences have an arithmetic mean value of exactly 127.5 (0xFF * 0.5). Both PRNG achieve near-perfect scores.

5. Monte Carlo Pi

Each successive sequence of six bytes is used as 24 bit X and Y co-ordinates within a square. If the distance of the randomly-generated point is less than the radius of a circle inscribed within the square, the six-byte sequence is considered a “hit”. The percentage of hits can be used to calculate the value of Pi. For very large streams (this approximation converges very slowly), the value will approach the correct value of Pi if the sequence is close to random. 

Considering that even radioactive decay (true physical randomness) will not achieve better results than both PRNGs. So the scores are almost perfect.

6. Serial Correlation

This quantity measures the extent to which each byte in the file depends upon the previous byte. For random sequences, this value (which can be positive or negative) will, of course, be close to zero. A non-random byte stream such as a C program will yield a serial correlation coefficient on the order of 0.5. Wildly predictable data such as uncompressed bitmaps will exhibit serial correlation coefficients approaching 1.

Both PRNGs achieve very good results.

 

Download

fliptag-3.1.zip

 

Edited May 16, 2015 by minx

[coffeeturtle]

"Get a random number between {0..255} inclusive."

Awesome work! Thank you for sharing, minx.

How can we increase the scope beyond 255, maybe 2,000, for example?

Thank you.

[minxomat]

"Get a random number between {0..255} inclusive."

Awesome work! Thank you for sharing, minx.

How can we increase the scope beyond 255, maybe 2,000, for example?

Thank you.

​Well fliptag returns bytes. Basically you want to construct a value which can be expressed as [0,1) Then just multiply with your left and right limits  . For example, if the value turns out to be 0 <= n < 1, which is the most common output, the calculation could be done like:

$result = Floor(YOURFUNCTION() * (1 + $high - $low)) + $low

 

[minxomat]

Here's an example. The resolution was increased to 1.525902189669642e-5 to allow random floats .

; Replica of AutoIts Random()
ConsoleWrite("-> " & _fliptag_random(1, 10, 1) & @LF)
ConsoleWrite("-> " & _fliptag_random(1, 10, 0) & @LF)

Func _fliptag_random($Min = 0, $Max = 1, $Flag = 0)
   Local $fFloat = (_fliptag_flip() + BitAND(($_flip[1] + $_flip[2]), 0x00FFFF)) / 0x00FFFF
   Return $Flag ? Floor($fFloat * (1 + $Max - $Min)) + $Min : $fFloat * (1 + $Max - $Min) + $Min
EndFunc

 

Edited May 16, 2015 by minx