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

Postby deltarho[1859] » Nov 21, 2020 14:38

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. Image

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

Postby deltarho[1859] » Nov 21, 2020 17:51

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

Postby deltarho[1859] » Nov 22, 2020 18:10

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    64
FB #2          385   932
PCG32II        574  1116
MsWs           563  1116
CryptoRndII    477   649
CMWC4096       465   579
xoroshiro128** 523  1097
xoshiro256**   501  1070
drSquares      592  1152
drSquaresII    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

Postby deltarho[1859] » Nov 23, 2020 13:06

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. Image

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
#endmacro

type 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 ulongint
end type

Function RandomKey() as Ushort
Dim 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 16383
End Function

Private 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()
  Next
End Sub

private function Squares.rand() as ulong
  Dim As Ulongint x, y, z
  Engine
  return (x * x + z) shr 32
end function

private function Squares.randse() as double ' 32-bit granularity
  Dim As Ulongint x, y, z
  Engine
  return ((x * x + z) shr 32)/2^32
end function

Private 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 res
End Function

Private 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^64
End Function

Function Squares.range(First As Long, Last As Long) As Long
  return clng(this.rand Mod (Last-First+1)) + First ' Mod method by dodicat
End Function

function Squares.range( First as double, Last as double ) as double
  Return this.rand/2^32 * ( Last - First ) + First
end function

Private Function Squares.Getctr() As Ulongint
   Return This.ctr
End Function

Private Sub Squares.Setctr( Counter As Ulongint )
  This.ctr = Counter
End Sub

Private Function Squares.Getkeynumber() As Ushort
  Return This.keynumber
End Function

Private Sub Squares.Setkeynumber( keyno As UShort )
  This.keynumber = keyno
  this.key = __SQRNG_KEY__( keyno )
End Sub

Private Function Squares.Getkey() As Ulongint
   Return This.key
End Function

Private Sub Squares.GetSnapshot()
  This.ctrSnapshot = This.ctr
  This.keySnapshot = This.key
End Sub

Private Sub Squares.SetSnapshot()
  This.ctr = This.ctrSnapshot
  This.key = This.keySnapshot
End Sub

Constructor Squares
  This.MyRandomize
  This.GetSnapShot
End Constructor

Dim 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

Postby deltarho[1859] » Nov 23, 2020 13:23

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

Re: My take on Squares PRNG

Postby deltarho[1859] » Nov 23, 2020 14:28

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.

This contradicts Widynski's findings.

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

Postby deltarho[1859] » Nov 23, 2020 18:00

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

Postby deltarho[1859] » Nov 23, 2020 20:12

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

Code: Select all

Four round squaring
private 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 4
end 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. Image
srvaldez
Posts: 2550
Joined: Sep 25, 2005 21:54

Re: My take on Squares PRNG

Postby srvaldez » Nov 23, 2020 23:11

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

may I ask where you can download that gcc version ?
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

Postby deltarho[1859] » Nov 24, 2020 0:17

srvaldez wrote:may I ask where you can download that gcc version ?

??? 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. Image
paul doe
Posts: 1334
Joined: Jul 25, 2017 17:22
Location: Argentina

Re: My take on Squares PRNG

Postby paul doe » Nov 24, 2020 1:23

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. Image

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

Postby deltarho[1859] » Nov 24, 2020 2:13

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. Image

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

Postby deltarho[1859] » Nov 24, 2020 12:05

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

Postby deltarho[1859] » Nov 24, 2020 17:05

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

Postby deltarho[1859] » Nov 24, 2020 23:31

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.

Return to “General”

Who is online

Users browsing this forum: No registered users and 11 guests