A strong PRNG

[neil]

The newest 3-line PRNG Practrand test results. It passed Practrand perfectly to 32 TeraBytes.

3-Line 64 bit output algorithm.
s1 = (s1 * (s1 + s2)) + (s1 shr 16)
s2 = (s2 xor (s1 + s2)) + (s1 shl 16)
s1 = (s1 * (s1 + s2)) + (s2 shr 16)

rng=RNG_stdin64, seed=unknown
length= 8 terabytes (2^43 bytes), time= 31238 seconds
no anomalies in 434 test result(s)

rng=RNG_stdin64, seed=unknown
length= 16 terabytes (2^44 bytes), time= 61488 seconds
no anomalies in 445 test result(s)

rng=RNG_stdin64, seed=unknown
length= 32 terabytes (2^45 bytes), time= 121611 seconds
no anomalies in 455 test result(s)

[deltarho[1859]]

@neil

I am sorry neil, but I cannot sit back and watch you ruin a perfectly good 64-bit output generator. Bear with me – I am not gaslighting.

Multiplications and bit shifting are expensive operations, especially multiplications.

Your original 3-line had three multiplications. The PractRand results were good, but its speed suffered and was being beaten by my MsWsII(64) and xoroshiro128** implementations.

Using Ulong to give a 32-bit output was a bad move. It created a buffer overrun in the Heap. It was a small overrun but should be avoided. Avoiding it was straightforward. Furthermore, even though the output was 64-bit the buffer was built using 32-bit so stdin32 should have been used and not stdin64.

You have published quite a few variations using two multiplications and one multiplication. The single multiplication is the best one. I shall come onto that later.

Getting 'unusual' evaluations should be expected – it is in the nature of random numbers. I have examined quite a few quantum random number (QRNG) dumps, and they have 'unusual' evaluations. Getting a clean sweep is rare and is more to do with luck than anything else. Using the same seeds all the time should be avoided.

This is what I use.

Code: Select all

Randomize , 5 ' Cryotographic
Function Get64Bit() As UlongInt
  Return (Cast( Ulongint, Rnd*(2^32) ) Shl 32) Or Cast( Ulongint, Rnd*(2^32) )
End Function
DIm AS Ulongint s1 = Get64Bit ,s2 = Get64Bit

With that, I have no idea what seeds I will get.

Now to the single multiplication variation.

Code: Select all

s1 = (s1 * s2) + (s2 shr 15)
s2 = (s2 + s1) + (s1 shl 11)
s1 = (s1 xor s2) + (s2 shr 3)

The bit shifting 15, 11 and 3 is faster than 16, 16, 16.

The speed is now on par with MsWsII(64) and xoroshiro128**. That is remarkable.

Yes, we get 'unusual' evaluations, but on testing a few times there are only a very few of them. The very latest variation is slower, two multiplications, and has a lot more 'unusual' evaluations and 'mildly suspicious' evaluations.

So, your 15, 11, 3 variation is the best so far, and even I would be happy to use it.

Test that to 16TiB and if successful, carve it in stone. It is a 'cracker'.

[deltarho[1859]]

hhr has mentioned an issue with s2 = 0

Many PRNGs have issues with zero seeds.

They can be filtered out with.

Code: Select all

DIm AS Ulongint s1, s2
Do
  s1 = Get64Bit
Loop Until s1 <> 0
Do
  s2 = Get64Bit
Loop Until s2 <> 0

[deltarho[1859]]

@neil

I have some disturbing news.

I ran a PractRand test on the 15, 11, and 3 variation using random seeds and PractRand version 0.95.

There was an 'unusual' at 8KiB and a clean sweep to 1TiB.

This is what I got at 2TiB.

Code: Select all

rng=RNG_stdin64, seed=unknown
length= 2 terabytes (2^41 bytes), time= 8561 seconds
  Test Name                         Raw       Processed     Evaluation
  [Low16/64]FPF-14+6/16:(2,14-0)    R= +10.4  p =  3.2e-9   very suspicious
  [Low16/64]FPF-14+6/16:(3,14-0)    R=  +8.1  p =  3.9e-7   mildly suspicious
  [Low16/64]FPF-14+6/16:all         R=  +6.4  p =  1.9e-5   mildly suspicious
  ...and 406 test result(s) without anomalies

We may then get a failure at 4TiB.

I have read of two PRNGs failing at 2TiB.

The only thing crossing my mind presently is that the algorithm does not have a period of 2^64. I have not been able to establish whether PractRand has a repeat cycle check or not. The consensus is that it does not.

Anyway, it is hanging in there, so I will let it continue.

[neil]

This one passed Practrand perfectly to 32 TeraBytes with no complaints. The test took 33 hrs 47 minutes.

3-Line 64 bit output algorithm.
s1 = (s1 * (s1 + s2)) + (s1 shr 16)
s2 = (s2 xor (s1 + s2)) + (s1 shl 16)
s1 = (s1 * (s1 + s2)) + (s2 shr 16)

rng=RNG_stdin64, seed=unknown
length= 8 terabytes (2^43 bytes), time= 31238 seconds
no anomalies in 434 test result(s)

rng=RNG_stdin64, seed=unknown
length= 16 terabytes (2^44 bytes), time= 61488 seconds
no anomalies in 445 test result(s)

rng=RNG_stdin64, seed=unknown
length= 32 terabytes (2^45 bytes), time= 121611 seconds
no anomalies in 455 test result(s)

[neil]

I will now take another look at this one.

s1 = (s1 * s2) + (s2 shr 15)
s2 = (s2 + s1) + (s1 shl 11)
s1 = (s1 xor s2) + (s2 shr 3)

[deltarho[1859]]

As expected, the 15, 11, and 3 variation failed at 4TiB.

[neil]

@deltarho[1859]
Thank for testing it. This saved me time. I just stopped my Practrand test. I will try another variation of the algorithm starting with the seed numbers. I will also try not using multiplication if its possible.

[deltarho[1859]]

@neil

Bernard Widynski uses one multiplication with his 32-bit Middle-Square Weyl Sequence RNG and two with the 64-bit engine.

Sebastiano Vigna's xoroshiro128** uses one multiplication. He also uses three rotations, and they don't come cheap.

So one, or perhaps two, multiplications are OK – three is getting a bit expensive.

With my graphics test program the 15, 11, 3 variation is about 10% faster than the latest 16, 16, 16 variation. However, with PRNGs 10% faster may not be apparent in a 'real world' application. MHz testing may show a greater difference, but I don't do MHz testing any more as it is not helpful.

Regarding the 15, 11, 3 variation, perhaps the shr 3 is too short. I like that variation because it has a good mix: *, + and xor.

[hhr]

May I point out a possible typo? On the previous page there is a generator with 15, 11, 9.

[deltarho[1859]]

It looks like I made the typo and tested it.

neil introduced the 15, 11, 9 using Ulong.

I tested the 15, 11, 3 using UlongInt.

I then started a PractRand run using 15, 11, 9 using UlongInt and got this.

Code: Select all

rng=RNG_stdin64, seed=unknown
length= 32 gigabytes (2^35 bytes), time= 138 seconds
  Test Name                         Raw       Processed     Evaluation
  [Low1/64]FPF-14+6/16:all          R=  -5.0  p =1-1.7e-4   unusual
  ...and 324 test result(s) without anomalies
 
rng=RNG_stdin64, seed=unknown
length= 64 gigabytes (2^36 bytes), time= 273 seconds
  Test Name                         Raw       Processed     Evaluation
  [Low16/64]FPF-14+6/16:(2,14-0)    R=  +6.7  p =  9.0e-6   unusual
  [Low16/64]FPF-14+6/16:(5,14-0)    R=  +9.3  p =  3.3e-8   suspicious
  ...and 338 test result(s) without anomalies
 
rng=RNG_stdin64, seed=unknown
length= 128 gigabytes (2^37 bytes), time= 539 seconds
  Test Name                         Raw       Processed     Evaluation
  [Low16/64]FPF-14+6/16:(2,14-0)    R= +15.6  p =  4.6e-14    FAIL
  [Low16/64]FPF-14+6/16:(5,14-0)    R= +21.9  p =  7.8e-20    FAIL !
  [Low16/64]FPF-14+6/16:all         R= +10.7  p =  1.6e-9    VERY SUSPICIOUS
  ...and 352 test result(s) without anomalies

So it looks like the *, +, xor approach is not a winner.

Code: Select all

s1 = (s1 * (s1 + s2)) + (s1 shr 16)
s2 = (s2 xor (s1 + s2)) + (s1 shl 16)
s1 = (s1 * (s1 + s2)) + (s2 shr 16)

seems to be a winner.

However, it should be tested using random seeds with s2 = 0 filtered out and not a favoured pair.

The 15, 11, 3 was an interesting test. I have never seen a decent run start to creak at 2TiB and then go down at 4TiB. PractRand's author once wrote that a 1TiB success indicated a good PRNG. It was Sebastiano Vigna who mentioned some PRNGs failing at 2TiB. So, to my mind, a top drawer PRNG should only be declared if it passes PractRand to 16TiB; which most of the 'big names' do.

[neil]

hhr was was correct about the prng zero problem. Here's how I solved it. s1 and s2 will never have a zero value. I tried smaller values and got Evaluation unusual. 5 digit numbers seem to work OK.
There is no xor or multiplication on this updated version. So far it's been a clean Practrand test to 4 TeraBytes. Let's see if it fails after 8 TeraBytes.
Here's the updated code.

Code: Select all

'' 3 line  PRNG 64 bit output by neil
'' prng3 | RNG_test stdin64 -multithreaded

#cmdline "-gen gcc -O 2"

Function ThreeLiner As Ulongint
   Static As Ulongint s1 = 71395159
   Static As Ulongint s2 = 53927315
    s1 = (s1 + s2) + (s2 shr 15)
    s2 = (s2 + s1) + (s1 shl  11) + 59173  '' s2 will never have a zero.
    s1 = (s1 + s2) + (s2 shr 3) + 97357    '' s1 will never have a zero.
    Return s1   
End Function

Dim Shared S As String * 1048576
Dim As Ulongint Ptr SPtr, BasePtr
Dim As Long j

SPtr = Cptr(Ulongint Ptr, Strptr( S ))
BasePtr = SPtr

Do
   For j = 1 To 131072
      *SPtr = ThreeLiner
      SPtr += 1
   Next
   Print s;
   SPtr = BasePtr
Loop

[neil]

The 15, 11, 3 updated version needs to be speed tested.

[deltarho[1859]]

1048576 x 16TiB = 2^64

Over the years, I have done many PractRand tests on quite a few PRNGS. In my experience, the vast majority of those 1048576 will have one or more unusual evaluations, including quantum random numbers.

Clean sweeps will tend to be rare and are not indicative of a supreme generator, but simply indicate pot luck. If we use random seeds, then it follows we should see some unusual evaluations.

Supreme generators will tend to have a larger percentage of clean sweeps, but they will never dominate.

I have found one PRNG which seems to have a larger percentage of clean sweeps than others and that is Intel's RdRand which is not surprising considering where it gets its entropy from. Other candidates are Microsoft's BCryptGenRandom and quantum random numbers.

Twenty-eight years ago, George Marsaglia wrote:

Most of the tests in DIEHARD return a p-value, which should be uniform on [0,1) if the input file contains truly independent random bits. ..... Thus you should not be surprised with occasional p-values near 0 or 1, such as .0012 or .9983. When a bit stream really FAILS BIG, you will get p's of 0 or 1 to six or more places. By all means, do not, as a Statistician might, think that a p < .025 or p> .975 means that the RNG has "failed the test at the .05 level". Such p's happen among the hundreds that DIEHARD produces, even with good RNG's. So keep in mind that " p happens".

If you publish results which are always clean sweeps, those who understand random numbers will treat them with suspicion.

So ignore unusual evaluations: " p happens".

“Mildly suspicious”, “Very suspicious”, or greater indicates an issue, and we should abort a PractRand test; It will probably fail shortly after anyway.

[deltarho[1859]]

The 15, 11, 3 updated version needs to be speed tested.

I dusted down my graphics speed test program and compared MsWsII(64), my fastest 64-bit output PRNG, with your '15, 11, 3'.

There was a noticeable variance with the 32-bit tests, so I took the median of seven tests. Note the use of median rather than averaging – we don't want 'rogue' slow or fast timings being influential.

With 32-bit '15, 11, 3' was about 16% faster than MsWsII(64). That is significant but may not be apparent in our applications.

With 64-bit the variance was small, but I still took the median of seven tests. Speed wise, there was no significant difference, and we would be unable to tell which was used in our applications.