My take on Squares PRNG

General FreeBASIC programming questions.
deltarho[1859]
Posts: 2698
Joined: Jan 02, 2017 0:34
Location: UK

Re: My take on Squares PRNG

I have spent a bit of time looking at your code, Paul, and visualized a piece of string divided up into blocks of sequences corresponding to a key number. Each block has 2^64 locations. Using two values for ctr and key you then apply the function rndxy. rndxy could be written using drSqaures' Setctr and Setkeynumber. ctr is not incremented, rndxy is used again with a different pair.

So, your take on Squares differs to mine which is a typical PRNG where we request a random number, and then another and so on. In my case, ctr must be incremented to achieve that. However, we can implement your take with the functions available in drSquares. Someone else may have a different take and chances are that drSquares can accommodate them as well. In a sense then drSquares could be regarded as a lego of functions. We can build a classical PRNG or something completely different.

Fascinating.

Added: Of course, the question is whether you and I have done a sufficiently good job for someone looking at this thread to come up a very different take.
deltarho[1859]
Posts: 2698
Joined: Jan 02, 2017 0:34
Location: UK

Re: My take on Squares PRNG

Oh dear, I am starting to suffer from 'cannot see the wood for the trees syndrome'.

I am using 16384, 2^14, sequences so my piece of string is 2^64 * 2^14 = 2^78. What is the advantage of that compared with a generator with a longer period, 2^128 say? What benefit are we getting from using a counter when all it is doing is offsetting into a sequence?

Did I write "It would be difficult, if not impossible, to emulate your rndxy function using PCG32II for example." Would it? We can use the graphic in the opening post for PCG32II with sequence in the z-plane. Instead of a counter going around the circumference in an orderly fashion we have a ball bearing flying around inside the cylinder, in the x-y plane, using the state in random directions, but what does that matter?

With PCG32II I use a random seed and a random sequence. Having chosen a sequence I tend not to change it again. I could and get a piece of string 2^127 long - 2^64 * 2^63, where 2^63 is from 2^63 odd numbered sequences.

With PCG32II suppose we are at the +25% mark on the cylinder's circumference. At some point I will be at the +75% mark but I have no idea when. It could be in a million random number requests or 2^50 requests - who knows. With Squares, I can jump straight from the +25% position to the +75% position just like, as mentioned, a BASIC Goto. That is where a counter-based RNG comes into its own.
deltarho[1859]
Posts: 2698
Joined: Jan 02, 2017 0:34
Location: UK

Re: My take on Squares PRNG

What I hadn't looked at is my 20 second test on a bunch of generators.
gcc 8.3, -fpu sse -gen gcc -Wc -O3

Code: Select all

`               32    64FB #2          385   932PCG32II        574  1116MsWs           563  1116CryptoRndII    477   649CMWC4096       465   579xoroshiro128** 523  1097xoshiro256**   501  1070drSquares      592  1152drSquaresII    576  1117`

We have a different story with drSquares compared with the yellow/blue pixel test program where drSquares did quite poorly. xoroshiro128** has done much better with this test as well.

xoroshiro128** and xoshiro256** are worthy of note having periods of 2^128 and 2^256 respectively and 53-bit granularity.

On this basis the Squares method is a serious competitor to PCG32II. As is often the case PCG32II and MsWs are 'neck and neck'. If anyone is using PCG32II there are no grounds to change that. However, if anyone has a need for massive amounts of random numbers, and by that I mean more than 2^32, then I would suggest xoroshiro128**.

NOTE: I have not seen this for a while. I got a failed compilation on 64-bit for drSquaresII and had to drop to gcc 7.5.
deltarho[1859]
Posts: 2698
Joined: Jan 02, 2017 0:34
Location: UK

Re: My take on Squares PRNG

drSquares is based upon the original version of Squares which has three rounds. Widynski wrote: "With an extra round of squaring it may be more likely to pass some (as of yet unknown) statistical test. This version is slower than the three round version, but still faster than Philox." He gives timings for both and the four round version is about 28% slower than the three round version.

What I have learned this last few years is that other people's timings do not give us a clue as to what FB's C-emitter plus gcc will behave like. With the yellow/blue pixel test and the 20 second test the difference between the Squares three round version and the four round version is negligible.

What I now need to do is subject the four round version to a PractRand analysis. If that is successful then PCG32II may well be looking at a replacement.

Here is the four round version of Squares which I have called drSquares4.bas.

drSquares4.bas

Code: Select all

`'#Console On#include "keys.bi"#macro Engine  x = this.key * (this.ctr+1)  y = x  z = y + this.key  x = x * x + y  x = ( x shr 32 ) or ( x shl 32 )  x = x * x + z  x = ( x shr 32 ) or ( x shl 32 )  x = x * x + y  x = ( x shr 32 ) or ( x shl 32 )  this.ctr += 1#endmacrotype Squares  Public:  declare Constructor  Declare Sub MyRandomize( Byval counter As Ulongint = 0, Byval keyno As Ulongint = 0 )  declare function rand() as ulong  declare function randse() as double  Declare Function randd() As Double  Declare Function range Overload ( First As Long, Last As Long ) As Long  Declare Function range Overload ( First As Double, Last As Double ) As Double  Declare Function Getctr() as ulongint  Declare Sub Setctr( Counter As Ulongint )  Declare Function Getkeynumber As Ushort  Declare Sub Setkeynumber( keyno As Ushort )  Declare Function Getkey() As Ulongint  Declare Sub GetSnapshot()  Declare Sub SetSnapshot()  Private:  ctr as ulongint  keynumber As Ushort  key as ulongint  ' The following are used by GetSnapshot/SetSnapshot  ctrSnapshot As ULongInt  keySnapshot As ulongintend typeFunction RandomKey() as UshortDim dummy As Ushort  Asm    rdtsc ' Get a fast changing number from the processor    mov word Ptr [dummy], ax  End Asm  Return dummy\4 ' 0 to 16383End FunctionPrivate Sub Squares.MyRandomize( byval counter As Ulongint = 0, byval keyno As Ulongint = 0 )  Dim As Ushort dummy  If counter = 0 Then    Randomize , 5 ' Cryptographic    this.ctr = ( Cast( Ulongint, Rnd*(2^32) ) Shl 32) Or Cast( Ulongint, Rnd*(2^32) ) Else    this.ctr = counter  End If  If keyno = 0 Then    dummy = RandomKey ' 0 to 16383    this.key = __SQRNG_KEY__( dummy )    this.keynumber = dummy  Else    this.key = __SQRNG_KEY__( keyno )    this.keynumber = keyno  End If  ' Warm up generator - may not be needed but playing it safe  For i As Ulong = 1 To 500    this.rand()  NextEnd Subprivate function Squares.rand() as ulong  Dim As Ulongint x, y, z  Engine  return (x * x + z) shr 32end functionprivate function Squares.randse() as double ' 32-bit granularity  Dim As Ulongint x, y, z  Engine  return ((x * x + z) shr 32)/2^32end functionPrivate Function mkulongint(n1 as ulong,n2 as ulong) as ulongint ' Courtesy MrSwiss  Dim As Ulongint res  Cast(Ulong Ptr,@res)[0]=n1  Cast(Ulong ptr,@res)[1]=n2  Return resEnd FunctionPrivate Function Squares.randd() As Double ' 53-bit granularity  Dim As Ulongint x, y, z  Dim As Ulong TempVar1, TempVar2  Engine  TempVar1 = (x * x + z) shr 32  Engine  TempVar2 = (x * x + z) shr 32  x = mkulongint( TempVar1, TempVar2 )return x/2^64End FunctionFunction Squares.range(First As Long, Last As Long) As Long  return clng(this.rand Mod (Last-First+1)) + First ' Mod method by dodicatEnd Functionfunction Squares.range( First as double, Last as double ) as double  Return this.rand/2^32 * ( Last - First ) + First end functionPrivate Function Squares.Getctr() As Ulongint   Return This.ctrEnd FunctionPrivate Sub Squares.Setctr( Counter As Ulongint )  This.ctr = CounterEnd SubPrivate Function Squares.Getkeynumber() As Ushort  Return This.keynumberEnd FunctionPrivate Sub Squares.Setkeynumber( keyno As UShort )  This.keynumber = keyno  this.key = __SQRNG_KEY__( keyno )End SubPrivate Function Squares.Getkey() As Ulongint   Return This.keyEnd FunctionPrivate Sub Squares.GetSnapshot()  This.ctrSnapshot = This.ctr  This.keySnapshot = This.keyEnd SubPrivate Sub Squares.SetSnapshot()  This.ctr = This.ctrSnapshot  This.key = This.keySnapshotEnd SubConstructor Squares  This.MyRandomize  This.GetSnapShotEnd ConstructorDim Shared As Squares Sq#undef Rnd#define Rnd Sq.randse`
deltarho[1859]
Posts: 2698
Joined: Jan 02, 2017 0:34
Location: UK

Re: My take on Squares PRNG

The four round version failed PractRand at 1GB. An investigation is now under way.
deltarho[1859]
Posts: 2698
Joined: Jan 02, 2017 0:34
Location: UK

Re: My take on Squares PRNG

I double-checked the version four source code and all seemed well.

I tried the stalwart gcc 5.2 with -O2 and still got a failure.

I dumped 100MB and tested with Fourmilab's ENT. The distribution uniformity was excellent and the serial correlation coefficient was OK.

I ran PractRand again starting at 1KB. There was five unusual evaluations up to 256MB. That is too many for 256MB. The 512MB got a very suspicious evaluation at 512MB followed by a failure at 1GB.

The three rounds version is a gem.
deltarho[1859]
Posts: 2698
Joined: Jan 02, 2017 0:34
Location: UK

Re: My take on Squares PRNG

I tried gas but to no avail.

Reading the PractRand documentation on the actual test that was failing it seems that too many zero bits are creeping into the lower 16 bits for too many outputs. For what it is worth I reckon that the last 'x = ( x shr 32 ) or ( x shl 32 )' has lead to 'over cooking'. In other words the extra round has done the damage but then what do I know. Distribution uniformity may not be affected much but randomness would be and that is what PractRand looks at.
deltarho[1859]
Posts: 2698
Joined: Jan 02, 2017 0:34
Location: UK

Re: My take on Squares PRNG

In 'A short appraisal of Squares PRNG' paul doe published this:

Code: Select all

`Four round squaringprivate function squares4( ctr as ulongint, key as ulongint ) as ulong  static as ulongint x, y, z   x = ctr * key : y = x : z = y + key   x = x * x + y : x = ( x shr 32 ) or ( x shl 32 ) '' Round 1  x = x * x + y : x = ( x shr 32 ) or ( x shl 32 ) '' Round 2  x = x * x + y : x = ( x shr 32 ) or ( x shl 32 ) '' Round 3   return( ( x * x + z ) shr 32 ) '' Round 4end function`

That is not what I have been testing which is from here, at the bottom of the page.

However, Paul's function also fails PractRand with the same test: Evaluation suspicious at 256MB; Evaluation very suspicious at 512MB; Evaluation FAIL at 1GB.

Of the four rounds version Widynski wrote: "It was subjected to the same statistical tests as the three round version."

Good job that I don't believe everything that I read.
srvaldez
Posts: 2550
Joined: Sep 25, 2005 21:54

Re: My take on Squares PRNG

deltarho[1859] wrote:I tried the stalwart gcc 5.2 with -O2 and still got a failure.

also, what's your opinion on this https://www.grc.com/otg/uheprng.htm
deltarho[1859]
Posts: 2698
Joined: Jan 02, 2017 0:34
Location: UK

Re: My take on Squares PRNG

??? Version 1.07.1 released

also, what's your opinion on this https://www.grc.com/otg/uheprng.htm

"1536 bits of internal “state” memory" OUCH!

The result is that the “period” of this generator will be the “Germain prime” 1,768,863 x 2^1535 - 1, which is approximately 2.132 x 10^468
WHAT?

Tested using Fourmilab's ENT. Am I the only one on this planet who reckons that ENT is superb for checking distribution uniformity but is next to useless for checking randomness? Chi squared is one of the metrics used. Many people reckon that chi squared is good for checking randomness. If we dropped the test data on the floor and sorted it, descending or ascending, the chi squared value would be the same. Chi squared is the square of observed minus expected relative to expected. It does not concern itself with how the data comes in. In other words it does not concern itself with randomness.

"diehard" and "dieharder" have been in the test suite's museum for quite a few years now. Folks now use BigCrush and/or PractRand.

Uses George Marsaglia's Multiply-with-carry. OLDE WORLDE and bettered with Complimentary Multiply-with-carry which itself is now outdated.

Web page last updated 2011.

So, will I check it out further? Nope.
paul doe
Posts: 1334
Joined: Jul 25, 2017 17:22
Location: Argentina

Re: My take on Squares PRNG

deltarho[1859] wrote:...
The result is that the “period” of this generator will be the “Germain prime” 1,768,863 x 2^1535 - 1, which is approximately 2.132 x 10^468
WHAT?
...

It harkens back to a time where 'length' was a thing. Of course, science has now advanced and the overall consensus is that 'girth' is generally preferred over 'length'.

Just saying.
...
So, will I check it out further? Nope.

Which is kind of a relief, since I was about to port the JavaScript code (which is notoriously difficult to port to statically typed languages) =D
deltarho[1859]
Posts: 2698
Joined: Jan 02, 2017 0:34
Location: UK

Re: My take on Squares PRNG

paul doe wrote:'girth' is generally preferred over 'length'.

The opposite is true for passwords. Once the obsession was with 'girth' - complexity. The problem with complexity is we cannot get more than 8 bits in a byte and to get anywhere near that we'd need to use high ANSI and many companies will not accept high ANSI. A well-known UK company supposedly renowned for its in house security rejected my alpha-numeric password because it was not complex enough. It had 22 random characters giving it an entropy of 131 bits which is uncrackable even today. The NIST recommended minimum at the moment is 112 bits. I gave this company a short complex password, and they accepted it. It had an entropy of about 74 bits which was less the 80 bit minimum recommended by the NIST at the time. Their chief security officer was Bruce Schneier. Yes, it was BT.

Needless to say I subsequently changed the password.
deltarho[1859]
Posts: 2698
Joined: Jan 02, 2017 0:34
Location: UK

Re: My take on Squares PRNG

Squares version history

[v1] Tue, 14 Apr 2020 02:58:14 UTC (8 KB)
[v2] Mon, 4 May 2020 02:39:05 UTC (8 KB)
[v3] Mon, 23 Nov 2020 02:51:36 UTC (8 KB)

Note v3 was yesterday but the link is still showing v2. It is six months since v2.
deltarho[1859]
Posts: 2698
Joined: Jan 02, 2017 0:34
Location: UK

Re: My take on Squares PRNG

Found v3.

The three rounds algorithm has been dropped and Widynski is 'pushing' the four round algorithm. He doesn't even mention that this an update to the three round algorithm - unusual behaviour. I emailed him about four hours ago asking where I could find v3 and the following has appeared since.

Added: He does mention the three rounds algorithm.
Lastly, I would like to thank Justin Lebar who detected a statistical failure with the three-round version of the RNG. The author is aware of no statistical failures with the four-round version presented in this paper.

Squares: A Fast Counter-Based RNG

@paul doe

Would you do a PractRand test becuase I am getting a failure at 1GB?
deltarho[1859]
Posts: 2698
Joined: Jan 02, 2017 0:34
Location: UK

Re: My take on Squares PRNG

I took the key I use for MsWs as a final try. No luck.

I would like to know what the "statistical failure" was with regard the three round version after "Additionally, we subjected squares to the PractRand test. 300 PractRand tests with random keys were run to 256 gigabytes, with no failures." and I pushed it to 2TB.

That plus the four round version failing at 1GB renders Squares with FreeBASIC dead in the water.

So, for me, it is back to PCG32II which was published in 2014, has not altered since and has received no unfavourable comments.

Of course, Paul may come back with a success but I doubt that.