PCG32II Help file

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

PCG32II Help file

Post by deltarho[1859] »

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: 2326
Joined: Oct 23, 2016 15:28
Location: Roma, Italia
Contact:

Re: PCG32II Help file

Post by jj2007 »

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: 4292
Joined: Jan 02, 2017 0:34
Location: UK
Contact:

Re: PCG32II Help file

Post by deltarho[1859] »

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: 4292
Joined: Jan 02, 2017 0:34
Location: UK
Contact:

Re: PCG32II Help file

Post by deltarho[1859] »

@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: 2326
Joined: Oct 23, 2016 15:28
Location: Roma, Italia
Contact:

Re: PCG32II Help file

Post by jj2007 »

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

Post by sean_vn »

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: 4292
Joined: Jan 02, 2017 0:34
Location: UK
Contact:

Re: PCG32II Help file

Post by deltarho[1859] »

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: 4292
Joined: Jan 02, 2017 0:34
Location: UK
Contact:

Re: PCG32II Help file

Post by deltarho[1859] »

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: 4292
Joined: Jan 02, 2017 0:34
Location: UK
Contact:

Re: PCG32II Help file

Post by deltarho[1859] »

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: 2326
Joined: Oct 23, 2016 15:28
Location: Roma, Italia
Contact:

Re: PCG32II Help file

Post by jj2007 »

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

Re: PCG32II Help file

Post by deltarho[1859] »

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: 4292
Joined: Jan 02, 2017 0:34
Location: UK
Contact:

Re: PCG32II Help file

Post by deltarho[1859] »

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.
Provoni
Posts: 513
Joined: Jan 05, 2014 12:33
Location: Belgium

Re: PCG32II Help file

Post by Provoni »

Hey deltarho[1859],

I am experimenting with your PCG32II and have a problem.

From the help file I simply added this to my program:

Code: Select all

#include "PCG32II.bas"
Dim pcg as pcg32
And then call:

Code: Select all

random_number=pcg.Range(1,s)
Where s is no larger than 2000. This code is called from tens of threads (very heavily multi-threaded).

The problem is that my program slows down allot (more than twice as slow) while using PCG32II instead of something like:

Code: Select all

state=48271*state and 2147483647
random_number=1+s*state shr 31
Do you have any ideas on how to offset the speed loss of using PCG32II.

Thanks
deltarho[1859]
Posts: 4292
Joined: Jan 02, 2017 0:34
Location: UK
Contact:

Re: PCG32II Help file

Post by deltarho[1859] »

Provoni wrote:Do you have any ideas on how to offset the speed loss of using PCG32II.
Not at the moment.

We can, of course, beat any good quality generator speed wise if we sacrifice quality.
deltarho[1859]
Posts: 4292
Joined: Jan 02, 2017 0:34
Location: UK
Contact:

Re: PCG32II Help file

Post by deltarho[1859] »

@Provoni

When using range do you need an integral number in the range or a floating-point number. In my case pcg.Range(1,n) is coming in at 366MHz whereas pcg.Range(1.0, n) is coming in at 594MHz, in 32 bit mode. In 64-bit mode I am getting 391MHz and 486MHz, some code is slower in 64-bit mode.
Post Reply