A strong PRNG

[deltarho[1859]]

Thanks, adeyblue. This is where SSE comes into its own.

Yes, it will be faster, but hard to tell how much faster.

The code is also specific to neil's 2 x 64-bit state vector. Having said that, it will work equally well with xoroshiro128**. xoshiro256** uses a 4 x 64-bit state vector, so we will have a bit of recoding to do.

I see that you use random seeds via 'Randomize, 5' which I have been shouting about for a while now.

I also notice that you use 'Rnd * (2^32)' twice to populate a UlongInt. We can use 'Rnd * (2^64)' just once.

[neil]

@hhr
So far, with my tests, your changes have helped speed it up. I am doing a 1 TeraByte test with your changes and will compare it with a 1 TeraByte test with my original algorithm. I think yours will be faster. I just started your test. I will post the Practrand results when they are finished.

[neil]

@hhr
Your changes to the algorithm was 117 seconds faster then mine to a TeraByte.
There has not been any problems with s1 or s2 with a zero's.
Practrand is going on a 32 TeraByte test on another PC with no problems.

Maybe you could optimize some more. The faster the better.

Here's your test to a TeraByte.
Practrand test results

hhr's with changes 117 seconds faster
rng=RNG_stdin64, seed=unknown
length= 1 terabyte (2^40 bytes), time= 3185 seconds
no anomalies in 397 test result(s)

neils original 117 seconds slower
rng=RNG_stdin64, seed=unknown
length= 1 terabyte (2^40 bytes), time= 3302 seconds
no anomalies in 397 test result(s)

hhr's version is faster

Code: Select all

Function ThreeLiner As Ulongint
   Static As Ulongint s1 = 8492356923
   Static As Ulongint s2 = 8974240601

'' hhr's changes helped speed it up
   s1 = ((s1 shl 1) + s2) + (s1 shr 16)
   s2 = (s1 + (s2 shl 1)) + (s1 shl 16)
   s1 = ((s1 shl 1) + s2) + (s2 shr 16)

  Return s1
End Function

[deltarho[1859]]

I doubted that hhr's version would make much difference in the real-world outside PractRand.

The following is not a MHz tester. It uses a method put forward by srvaldez some time ago. It times totalling [0, 1) and prints the time and the total. We need to print the total to stop gcc interfering with the loop.

Normally I would use random seeds, but fixed seeds were used to maintain a level playing field.

Code: Select all

Function ThreeLiner() as Double
  Static As Ulongint s1 = 8492356923
  Static As Ulongint s2 = 8974240601

' 1
  s1 = (s1 * (s1 + s2)) + (s1 shr 16)
  s2 = (s2 xor (s1 + s2)) + (s1 shl 16)
  s1 = (s1 * (s1 + s2)) + (s2 shr 16)
  
' 2
'  s1 = (s1 + (s1 + s2)) + (s1 shr 16)
'  s2 = (s2 + (s1 + s2)) + (s1 shl 16)
'  s1 = (s1 + (s1 + s2)) + (s2 shr 16)

' 3
'  s1 = ((s1 shl 1) + s2) + (s1 shr 16)
'  s2 = (s1 + (s2 shl 1)) + (s1 shl 16)
'  s1 = ((s1 shl 1) + s2) + (s2 shr 16)
  Return s1/2^64
End Function

Dim As Double t, tot
t = Timer
For i As Ulong = 1 to 10^8
  tot += ThreeLiner
Next
t = Timer - t
Print 100/t;" ";tot

Sleep

This what I get:

Code: Select all

    32b    64b
1  64.84  103.48
2 106.52  163.41
3 106.59  163.56

2 ad 3 are faster than 1 in 32-bit and 64-bit.

However, there is hardly any difference between 2 and 3.

So PractRand is not the tool to use for testing the speed of PRNGs.

[neil]

This just passed Practrand to 32 TeraBytes.

Neils 3-Line 007 PRNG
s1 = (s1 + (s1 + s2)) + (s1 shr 16)
s2 = (s2 + (s1 + s2)) + (s1 shl 16)
s1 = (s1 + (s1 + s2)) + (s2 shr 16)

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

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

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

[deltarho[1859]]

To put things in perspective, if 'tot += ThreeLiner' is replaced with 'tot += Rnd' using MsWsII.bas and Rnd redefined, I get 362.93.

That is why I prefer my graphics speed test program because it brings everyone down to earth. Although the above is not a MHz tester, it is still a laboratory tester and tells us nothing about how a PRNG behaves in the wild.

[deltarho[1859]]

Neils 3-Line 007 PRNG

I wondered whether you had a sense of humour.

32TiB

Bear with me as I wipe the egg off my face.

I am confident that if Melissa O'Neill or Sebastiano Vigna saw your '+' algorithm, they would say the same as me: “PractRand will slaughter that.”

Whilst the beginning of the three statements is important, the 'magic' may be in the three shifts (s1 shr 16), (s1 shl 16), and (s2 shr 16).

I am not sure how to do this, but a thorough analysis is needed to see exactly what is going on.

Meanwhile, I need to lie down in a darkened room.

[deltarho[1859]]

In the above we saw that neil's '+' code got a value of 106.52 compared with MsWsII(64)'s 362.93.

With the graphic's speed test code, there is very little difference between the two.

The test statement is dominated by pset which renders a PRNG's speed as very nearly irrelevant. This will be true of any application which is similar to the graphic's speed program.

What we need is another test program which gives random numbers more 'say' in the execution time of a statement.

To that end I looked at:

Code: Select all

Dim As UlongInt Count
Dim As Double x, y, z, t
t = Timer
Do
  x = Rnd
  y = Rnd
  z = x*x + y*y
  Count += 1
Loop Until Timer > t + 1
Print Count

What that does is count the number of times 'z = x*x + y*y' is executed in one second.

This is what I got:

Code: Select all

                  32b       64b
xoroshiro128**  25577698  56245698
MsWsII(64)      21985266  51548640
Neil's 007      20081315  32232613
xoshiro256**    17737808  54343922

With 32-bit 128** is the clear winner, 16% ahead of MsWsII(64). Neil's 007 does quite well, just 9% behind MsWsII(64). 256** is struggling, but it uses a state vector twice the size of the others and has a period of 2^256.

With 64-bit 128** is the winner again and 256** starts to shine. MsWsII(64) is pushed into third place, and Neil's 007 slips well behind.

It is worth noting that MsWsII(64) uses two MsWsII(32) outputs, but still gets second place in 32-bit mode. It suffers in 64-bit mode.

I should think that most applications fall between the graphics test and the numerical test.

In my MsWsII package I am tempted to replace the 64-bit engine with xoroshiro128** but I need to give that some thought because Melissa O'Neil was a little critical of xoshiro256**. Not entirely surprising because O'Neill and Sebastiano Vigna have not been on the best of terms for a few years.

So with applications similar to the graphics test code, it doesn't really matter which PRNG we choose. With applications similar to the numerical test code neil's code is a competitor to MsWsII(64) in 32-bit mode but is poor in 64-bit mode.

Regarding 32-bit output PRNGs MsWsII(32) rules and why I selected it to have the greatest functionality of all my PRNG implementations replacing my previous favourite PCG32II and knocked out a Help file.

[neil]

deltarho[1859]
Didn't you add extra code to mine something about s2 = 0. If you did remove it and rerun the test.
You don't need it passed Practrand to 32 TeraBytes without it. This will increase the speed.
Also was your test up to Britain's standards?
https://www.ibtimes.com/worlds-most-acc ... ain-305818

[deltarho[1859]]

@neil

The random seeds are determined before the Do/Loop and have no effect on the speed of PractRand.

Also was your test up to Britain's standards?

Of course.

[neil]

deltarho[1859]
Keep testing my 007 PRNG it passed Practrand to 64 TeraBytes. I am going to see if it makes it to 128 TeraBytes. I will post the test results in a couple of days.

[neil]

deltarho[1859]
Has your Practrand test of my 007 PRNG passed Practrand to 32 TeraBytes yet? If not don't stop the test let it go to at least 64 TeraBytes it will pass.

Would you post your PRNG with your FreeBasic Practrand test program. I would like to test your PRNG also.

[deltarho[1859]]

@neil

Getting to 128TiB will give you substantial bragging rights, but very little else.

From a scientific perspective, I would rather see 8x16TiB passed than just one 128TiB pass.

Better still would be 32x4TiB. Since 4TiB is 512Gi 64-bit outputs, that should satisfy most people.

Of course, random seeds should be used.

Here is my random seed 'piping' program.

Code: Select all

Randomize , 5 ' Cryotographic
Dim As UlongInt s1, s2
Do
  s1 = Cast(UlongInt, Rnd*(2^64))
Loop Until s1 <> 0
Do
  s2 = Cast(UlongInt, Rnd*(2^64))
Loop Until s2 <> 0
Dim Shared S As String * 2097152
Dim As Ulongint Ptr SPtr, BasePtr
SPtr = Cptr(Ulongint Ptr, StrPtr(S))
BasePtr = SPtr
Do
  For i As Ulong = 1 to 262144
    ' 007 PRNG algorithm 
    s1 = (s1 + (s1 + s2)) + (s1 shr 16)
    s2 = (s2 + (s1 + s2)) + (s1 shl 16)
    s1 = (s1 + (s1 + s2)) + (s2 shr 16)
    *SPtr = s1
    SPtr += 1
  Next
  Print s;
  SPtr = BasePtr
Loop

I still have reservations about the '+' method. Nobody, as far as I know, has published a '+' method and there must be a reason for that. I have a feeling that the '+' method is repeating cycles more often than 2^64 and PractRand is not spotting it.

Bernard Widynski provides a mathematical proof that his Middle-Square Weyl Sequence RNG has a period of 2^64. We could do with a proof that your '+' method has a period of 2^64. At the moment I am unable to do that.

I have written a small piece of code, less than 50 lines, giving your method the deltarho touch which outputs [0,1), with 53-bit granularity, a discrete range and a continuous range. They are the most commonly used functions of PRNGs. The code is also thread safe.

I will post that if you have no objection.

Added: Before I forget, you mentioned some time ago that the large string buffer was dodicat's idea. It wasn't – I wrote it and dodicat used it.

[neil]

deltarho[1859]
Thanks for you work on the large string algorithm very nice.
If you publish your 50 lines. I will test my PRNG with your 50 lines later. I would like to see your 50 lines of test code with your PRNG. I would like to test your PRNG.

[neil]

deltarho[1859]
Actually to be fair I would like to see your PRNG output 64 bits like mine and not fail Practrand.