PCG32II Help file

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

PCG32II Help file

Postby deltarho[1859] » Sep 24, 2018 7:44

In the 'FreeBASIC's PRNG #2' thread I wrote
You know what, jj2007, in view of the fact that PCG32II knocks spots off anything that I have and there is a lot more to it than meets the eye perhaps I should write a Help file for it. Anyone visiting the 'main' PCG thread for the first time will find it heavy going; not heavy technically but it really is a long read and new ideas keep popping up throughout.

jj2007's response was
Indeed, that would be a good idea. In the meantime, .....

<Laugh.>

Anyway, here it is. It took me a while - quite frankly I'd rather go to the dentist than write a Help file. I have tried to avoid any 'howlers' inviting you to mention them so that I don't have to open my help authoring software again. <smile.

Attached is a zipped folder which includes PCG32II.chm and the latest version of PCG32II.bas for including in your BASIC source code.

PCG32II.bas has had some additions.

RandD returns a Double which has a granularity of 53-bit got by using two 32-bit outputs. This complements the existing RandSE which has a granularity of 32-bit.

GetState has been added to GetSeed and GetSequnce. GetState simply returns the last 64-bit state value.

GetSnapShot and SetSnapShot get and set the state vector; state and sequence.

The Get64Bit function used by MyRandomize has a Windows version, conditionally compiled, to provide a 'stronger' random 64 bit value.

PCG32II.zip
jj2007
Posts: 1161
Joined: Oct 23, 2016 15:28
Location: Roma, Italia
Contact:

Re: PCG32II Help file

Postby jj2007 » Sep 24, 2018 10:26

Thanks, great work. It took me a little while to understand the logic of "Comparison with other PRNGs", maybe you could start with the explanation:

Code: Select all

Each generator was given 20 seconds for execution; the values are the random numbers generated divided by 10^6.
FB 1 to 5 are the FreeBASIC stock generators:

FB 5 1.10
FB 1 425.51
FB 3 441.08
CMWC4096 462.67 ' George Marsaglia's Complementary-multiply-with-carry, base 2^32-1, lag~4096 by author
CryptoRndII 470.51 ' Using buffered Microsoft's BcryptGenRandom with thread pooling by author
FB 4 473.92
FB 2 486.92
RndMT 605.18 ' FreeBASIC's Mersenne Twister with asm engine and 640 32-bit seeds by author
MsWs 779.59 ' Middle Square Weyl Sequence RNG by Bernard Widynski
Num Recipes 850.54 ' 32-bit LCG from the book Numerical Recipes
Knuth64 872.79 ' 64-bit LCG by Donald Knuth
PCG32II 874.28 ' Melissa O'Neill's pcg32_random_r by author
Infinity 875.80 ' Courtesy of Singularity Inc.
deltarho[1859]
Posts: 1765
Joined: Jan 02, 2017 0:34
Location: UK

Re: PCG32II Help file

Postby deltarho[1859] » Sep 24, 2018 10:42

jj2007 wrote:maybe you could start with the explanation:

Sorry, but I don't know where to start. I am looking at it now and it seems clear to me.

It could be a classic example of being so familiar with something missing aspects get automatically painted in but someone viewing for the first time are not able to do that. So, it is a case for me to try and spot what is missing.

Is anyone else having a problem with that topic?
deltarho[1859]
Posts: 1765
Joined: Jan 02, 2017 0:34
Location: UK

Re: PCG32II Help file

Postby deltarho[1859] » Sep 24, 2018 13:49

@jj2007

Is the following any clearer?

Code: Select all

Here are the contents of a task loop taken from a test bench program.
 
x = <random number>
y = <random number>
x = Sqr( x*x + y*y )
 
Each generator was given 20 seconds to repeatedly execute the above and the number of loops completed was noted. The values are the number of loops executed divided by 10^6.
 
1 to 5 are the FreeBASIC stock generators.
 
So, FreeBASIC generator #5, being a slow generator, only managed to complete 1.1 million loops in 20 seconds. PCG32II, on the other hand, completed 874.28 million loops in 20 seconds.
 
Infinity has the task loop using x and y as constants. This is tantamount to a generator running at infinite speed.
 
5              1.10
1            425.51
3            441.08
CMWC4096     462.67 ' George Marsaglia's Complementary-multiply-with-carry, base 2^32-1, lag~4096 by author
CryptoRndII  470.51 ' Using buffered Microsoft's BcryptGenRandom with thread pooling by author
4            473.92
2            486.92
RndMT        605.18 ' FreeBASIC's Mersenne Twister with asm engine and 640 32-bit seeds by author
MsWs         779.59 ' Middle Square Weyl Sequence RNG by Bernard Widynski
Num Recipes  850.54 ' 32-bit LCG from the book Numerical Recipes
Knuth64      872.79 ' 64-bit LCG by Donald Knuth
PCG32II      874.28 ' Melissa O'Neill's pcg32_random_r by author
Infinity     875.80 ' Courtesy of Singularity Inc.

exe compiled with gcc 8.1, fbc 1.06 ( 22 Sept 2018 )
jj2007
Posts: 1161
Joined: Oct 23, 2016 15:28
Location: Roma, Italia
Contact:

Re: PCG32II Help file

Postby jj2007 » Sep 24, 2018 14:33

Yes, much clearer. Don't worry, eventually I understood also the original text ;-)

Btw I am still struggling to find an implementation of the Numerical Recipes ran() algo. The simple formula

Code: Select all

state=2862933555777941757*state+3037000493
yields e.g.

Code: Select all

-1253254567
-239350324
774553919
1788458162
-1492604891
-478700648
535203595
1549107838
-1731955215
-718050972
295853271
1309757514
-1971305539
-957401296
56502947
1070407190
2084311433
-1196751620
-182847377
831056866
1844961109
-1436101944
-422197701
591706542
1605610785
-1675452268
-661548025
352356218
1366260461
-1914802592
-900898349
113005894
1126910137
2140814380
-1140248673
-126344430
887559813
1901464056

Which looks nice and random but fails PractRand after one kByte <lol>
sean_vn
Posts: 283
Joined: Aug 06, 2012 8:26

Re: PCG32II Help file

Postby sean_vn » Sep 24, 2018 14:34

I am trying the xoshiro256 type algorithms with a different mixing/tempering function to the original.
You can change the timestamp function for non linux amd64. I'm not looking for the algorithm to pass
the usual RNG tests (though it may or may nearly), just to have a large state space and avoid correlation that might affect evolution algorithms.

Code: Select all

namespace rnd256

    dim as ulongint s0,s1,s2,s3
     
   ' Hash function Stafford Mix 13
   function hash64(h as ulongint) as ulongint
      h = ( h xor ( h shr 30 ) ) * &hBF58476D1CE4E5B9
      h = ( h xor ( h shr 27 ) ) * &h94D049BB133111EB
      return h xor ( h shr 31 )
   end function

   ' Read the time stamp counter (x86-64) in a messed up way
   function timestamp naked() as ulongint
      asm
        rdtsc
        add rdx,rax
        bswapq rdx
        or rax,rdx
        ret
      end asm
   end function
   
   function rand() as ulongint
      dim as ulongint result=hash64(s1) ' tempering function
      dim as ulongint t=s1 shl 17
      s2 xor=s0
      s3 xor=s1
      s1 xor=s2
      s0 xor=s3
      s2 xor=t
      s3=(s3 shl 45) or (s3 shr 19)
      return result
   end function
   
   sub init() constructor
     s0=hash64(timestamp())
     s1=hash64(timestamp())
     s2=hash64(timestamp())
     s3=hash64(timestamp())
   end sub
end namespace

deltarho[1859]
Posts: 1765
Joined: Jan 02, 2017 0:34
Location: UK

Re: PCG32II Help file

Postby deltarho[1859] » Sep 24, 2018 15:21

Thanks, jj.

Version 1.01 of chm file uploaded. <smile> I also added a few lines to that topic with regard to the randomness of the test generators.
jj2007 wrote:Which looks nice and random but fails PractRand after one kByte <lol>

So does FB #1 on Windows. The C runtime library's rand() has had many complaints over the years.

@sean_vn

Thanks for that. I looked at the original xoshiro256 figuring that a period of 2^256 would make a nice addition to my collection but it failed PractRand very early on and was worse than the earlier 128 algorithms and they were bad enough. A lot of software using Vigna's work should have a look at Melissa O'Neill's PCG family.
deltarho[1859]
Posts: 1765
Joined: Jan 02, 2017 0:34
Location: UK

Re: PCG32II Help file

Postby deltarho[1859] » Feb 15, 2019 10:44

Needed a floating point range recently and noticed that I had neglected to include one.

Replaced the original Function range with

Code: Select all

Declare Function range Overload( Byval One As Long, Byval Two As Long ) As Long
Declare Function range Overload ( Byval One As Double, Byval Two As Double ) As Double

The 'Double' version does effectively the same job as rnd_range in FB's help file except instead of 32 bits to [0,1) and then 'back out again' to the requested range we go from 32 bits straight to the requested range.

I won't mention how slow FB's rnd_range is as I think I got the timing wrong but PCG32II's floating point range is coming in at 579MHz, in 32bit, which is getting very close to frightening the horses. <smile>. It is not far behind randse which comes in at 595MHz.

The link in the opening post gets us the new bas file and a slightly edited chm file.
deltarho[1859]
Posts: 1765
Joined: Jan 02, 2017 0:34
Location: UK

Re: PCG32II Help file

Postby deltarho[1859] » Feb 16, 2019 0:27

I did a spot of tidying up whilst I was at it and randse and the float range went 'pear-shaped' in 64 bit. Tidying up removed and all is well again.

I now need to fathom out what happened. The tidying up was not problematic in 32 bit. That piece of info should help. I will report back when I have an answer. I probably made a really dumb move but others may fall into the same trap, unless nobody is as dumb as me.
jj2007
Posts: 1161
Joined: Oct 23, 2016 15:28
Location: Roma, Italia
Contact:

Re: PCG32II Help file

Postby jj2007 » Feb 16, 2019 3:03

deltarho[1859] wrote:nobody is as dumb as me.
So you think you are unique?? No way...
deltarho[1859]
Posts: 1765
Joined: Jan 02, 2017 0:34
Location: UK

Re: PCG32II Help file

Postby deltarho[1859] » Feb 16, 2019 7:34

jj2007 wrote:So you think you are unique?? No way...

<smile>

I wasn't being dumb - I was being ignorant.

I assumed that the following code snippets did the same thing and the second was a tidy up of the first.

Code: Select all

Dim TempVar As Ulong
' blah
' blah
TempVar = (xorshifted Shr rot) Or (xorshifted Shl ((-rot) And 31))
Return TempVar/4294967296.0

Code: Select all

Return (xorshifted Shr rot) Or (xorshifted Shl ((-rot) And 31))/4294967296.0

However, the expression (xorshifted Shr rot) Or (xorshifted Shl ((-rot) And 31)) could exceed 4294967296 and will be clipped when TempVar is used. Aggressive tidying up resulted in that terrible expression 'Throwing the baby out with the bathwater'.

An analogy would be when we use UInteger and should have used Ulong.

I didn't write the code, ported from C, and was not aware that the expression needed to be clipped.

TempVar could have been avoided by applying CUlng to the expression.
deltarho[1859]
Posts: 1765
Joined: Jan 02, 2017 0:34
Location: UK

Re: PCG32II Help file

Postby deltarho[1859] » Mar 02, 2019 5:18

Very minor update.

If we do not use GetSnapShot before using a SetSnapShot then we will not get a sequence repeat. Fairly obvious really but although we can invoke GetSnapShot at any point in our code it will probably be used before we start to request any random numbers so that we can return to the code's outset with a SetSnapShot.

So, GetSnapShot has now been included in the Constructor as follows.

Code: Select all

Constructor pcg32
  This.MyRandomize
  This.GetSnapShot
End constructor

You may recall that using MyRandomize without parameters will create a random seed and a random sequence. GetSnapShot is called after MyRandomize to ensure that the state vector is that pertaining after the generator's warm-up; the last task of MyRandomize.

We could then have something like this where we are comparing two algorithms.

Code: Select all

#include "PCG32II.bas"
Dim As pcg32 pcg
' Test some code which uses random numbers
pcg.SetSnapShot
' Test some other code using the same random numbers.

Each time we run that code we will be using different random numbers.

Zip in opening post has been updated - revised bas and revised chm.

Return to “General”

Who is online

Users browsing this forum: No registered users and 3 guests