FreeBASIC's PRNG #2

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

FreeBASIC's PRNG #2

Post by deltarho[1859] »

Testing RNGs with PractRand (14 Aug 2017) looks at 32-bit LCGs, MWC, 64-bit generators including a couple from Vigna & Blackman, Mersenne Twister, and O'Neill's PCG.

The LCG failed straight away, MWC failed at 64MB, Vigna & Blackman's RNGs failed straight away, Mersenne Twister failed at 512GB and the PCG fran through to 16TB.

Clearly, PCG is head and shoulders above the rest from a quality perspective and it is also quite fast. PractRand's author and I got 32-bit Mersenne Twister failing at 256GB. 256GB is a lot of random numbers and considering Mersenne Twister is over 20 years old it is still holding its own today; although a bit slow by modern standards. There is a small bias in Mersenne Twister but PractRand is not picking it up until we get past 128GB. Mersenne Twister does better in other tests but PractRand has developed a reputation for not taking prisoners.

Here is a test, on bits not bytes, of an LCG (Numerical Recipes) using Fourmilab's ENT.

Code: Select all

Entropy = 1.000000 bits per bit.
 
Optimum compression would reduce the size
of this 33554432 bit file by 0 percent.
 
Chi square distribution for 33554432 samples is 0.06, and randomly
would exceed this value 81.04 percent of the times.
 
Arithmetic mean value of data bits is 0.5000 (0.5 = random).
Monte Carlo value for Pi is 3.142842429 (error 0.04 percent).
Serial correlation coefficient is -0.000119 (totally uncorrelated = 0.0).
Nothing apparently untoward there but LCGs have a heavy bias and ENT is not sophisticated enough to spot it.

My problem with PractRand has been that the first hurdle requires multiple MB of data and I have wanted it to start with a much lower hurdle.

I have found a switch we can use after stdin: -tlmin <N>KB where N is the 'height' of the first hurdle. So, we can use something like this: My_RNG.exe | RNG_test.exe stdin -tlmin 1KB.

I tested a few LCGs and they failed at 8KB. FreeBASIC's generator #2 failed at 4KB.

These are very small hurdles but if you have a graphics program requiring up to 2000, or so, random numbers for initialization purposes then even PractRand won't fault you for using FreeBASIC's generator #2. You will not need any of my 'sophisticated' generators and FB's #2 is marginally faster than my fastest.

I should mention that MWC is Marsaglia's initial foray into a new type of PRNG. My CMWC4096 is a Complimentary Multiply With Carry, lag~4096 base 2^32-1 and that went to 2TB with PractRand.

If you need more than 4KB of random numbers of good quality then do not use a LCG because you will not get them.

As a final note, I have to admit that being a purist I still cannot bring myself to using an LCG. I have a light version of PCG32II which does nothing other than knock out [0,1) numbers. <smile>
deltarho[1859]
Posts: 4292
Joined: Jan 02, 2017 0:34
Location: UK
Contact:

Re: FreeBASIC's PRNG #2

Post by deltarho[1859] »

I have just used a Monte Carlo method for determining pi. Each algorithm was given 20 seconds to do their stuff and each executed fives times. The numbers are the iterations completed divided by 10^6.

With this 'real life' test PCG32II just managed to squeeze past FB's #2. It also highlights the fact that whilst one generator may be four or five times faster than another 'on paper' the relative difference may be very much less in practice dependent upon the complexity of the statement using the random numbers.

Code: Select all

5              1.44
RndMT        367.90
xoshiro256    375.13
3            376.29
1            383.67
CryptoRndII  400.19
4            401.14
CMWC4096     407.44
2            408.14
PCG32II      409.60
Last edited by deltarho[1859] on Sep 06, 2018 13:50, edited 2 times in total.
deltarho[1859]
Posts: 4292
Joined: Jan 02, 2017 0:34
Location: UK
Contact:

Re: FreeBASIC's PRNG #2

Post by deltarho[1859] »

I have found another switch to use after stdin.
while adding "-e 0.001" will make it show only highly suspicious results. The default is "-e 0.1"
Marsaglia wrote in his DIEHARDER suite:
Thus you should not be surprised with occasional p-values near 0 or 1, such as .0012 or .9983. When a bit stream really FAILS BIG, you will get p's of 0 or 1 to six or more places. By all means, do not, as a Statistician might, think that a p < .025 or p> .975 means that the RNG has "failed the test at the .05 level". Such p's happen among the hundreds that DIEHARD produces, even with good RNG's. So keep in mind that " p happens".
In the future, I will use '-e 0.001'
deltarho[1859]
Posts: 4292
Joined: Jan 02, 2017 0:34
Location: UK
Contact:

Re: FreeBASIC's PRNG #2

Post by deltarho[1859] »

The table above is for 32-bit. For 64-bit we have:

Code: Select all

5           1.68
1           488.62
RndMT       550.01
3           681.09
CMWC4096    698.59
CryptoRndII 751.88
4           816.60
xoshiro256  849.77
2           866.53
PCG32II     871.97
I cannot recommend xorshiro256 at this time - the quality is very poor.
Last edited by deltarho[1859] on Sep 06, 2018 13:51, edited 2 times in total.
integer
Posts: 408
Joined: Feb 01, 2007 16:54
Location: usa

Re: FreeBASIC's PRNG #2

Post by integer »

Very interesting.
I like the idea of a full 64 bit ulongint, instead of the 53 bit from a double.
deltarho[1859]
Posts: 4292
Joined: Jan 02, 2017 0:34
Location: UK
Contact:

Re: FreeBASIC's PRNG #2

Post by deltarho[1859] »

integer wrote:I like the idea of a full 64 bit ulongint, instead of the 53 bit from a double.
So do I. Where did you get that from?
dafhi
Posts: 1640
Joined: Jun 04, 2005 9:51

Re: FreeBASIC's PRNG #2

Post by dafhi »

integer - thanks for pointing that out. i've been wanting to make a 2d starfield generator based upon a wave function.

think i'll go with int
Last edited by dafhi on Sep 05, 2018 16:57, edited 1 time in total.
deltarho[1859]
Posts: 4292
Joined: Jan 02, 2017 0:34
Location: UK
Contact:

Re: FreeBASIC's PRNG #2

Post by deltarho[1859] »

dafhi wrote:thanks for pointing that out.
Pointing what out?
deltarho[1859]
Posts: 4292
Joined: Jan 02, 2017 0:34
Location: UK
Contact:

Re: FreeBASIC's PRNG #2

Post by deltarho[1859] »

On my travels, I came across Donald Knuth's 64-bit LCG. LCGs usually have a 32-bit state and output 32-bit. The 32-bit state is their inherent weakness. Knuth's algorithm is 64-bit state and 64-bit output.

This is Knuth's 64-bit algorithm.

Code: Select all

rand = (6364136223846793005ull * rand + 1442695040888963407ull) and 18446744073709551615ull ' UlongInt
randD = rand/2^64 ' Double in [0,1)
To get 53-bit granularity with the 32-bit outputs we need to request two random numbers. With the Knuth we don't; as with the xorshiro256 which has a 256-bit state and 64-bit output.

CryptoRnd's full 'double', two random numbers, comes in, speed-wise, at about 64% of SE, one random number. Knuth64 is surprisingly fast, but it is an LCG.

Being an LCG PractRand did not take to it and it failed at 16KB, a lot better than the 32-bit LCGs. To be safe, for good quality, I'd use a limit of 8KB. That should keep most of you happy if you need 53-bit granularity.

Code: Select all

5            1.36
RndMT        367.47
xoshiro256   374.00
3            377.84
1            382.17
Knuth64      393.85
CryptoRnd    399.94
4            400.95
CMWC4096     407.23
PCG32II      407.95
2            410.43
FB's #2 got it's own back on this run and just pipped PCG32II.

The 64-bit figures are:

Code: Select all

5            1.63
1            485.63
RndMT        550.48
3            682.98
CMWC4096     697.96
CryptoRnd    749.67
Knuth64      784.13
4            816.76
xoshiro256   849.42
2            866.46
PCG32II      874.20
and PCG32II is back on top again <smile>
Last edited by deltarho[1859] on Sep 06, 2018 1:59, edited 2 times in total.
deltarho[1859]
Posts: 4292
Joined: Jan 02, 2017 0:34
Location: UK
Contact:

Re: FreeBASIC's PRNG #2

Post by deltarho[1859] »

With a basic loop, I could not time Knuth64 - the compiler rips the loop out with extreme prejudice. A spot of reading suggested dropping 'Asm nop' into the loop. That worked. For 32-bit I got 529MHz (median of 7 runs) which beats PCG32II at about 505MHz (one 32-bit random number used) but, as we have seen, that may not carry through in 'real life'.

BTW, I got a 0.4999842884357874 10^7 average.
deltarho[1859]
Posts: 4292
Joined: Jan 02, 2017 0:34
Location: UK
Contact:

Re: FreeBASIC's PRNG #2

Post by deltarho[1859] »

Want a random 64-bit seed?

Code: Select all

Function Get64Bit() As UlongInt
  Return (Cast( Ulongint, Rnd*(2^32) ) Shl 32) Or Cast( Ulongint, Rnd*(2^32) )
End Function

Randomize , 5
rand = Get64Bit
Here is a test snippet:

Code: Select all

Dim As Ulongint rand
Dim As Ulong i
Dim As Double t, tot, randd

Function Get64Bit() As Ulongint
  Return (Cast( Ulongint, Rnd*(2^32) ) Shl 32) Or Cast( Ulongint, Rnd*(2^32) )
End Function

Randomize , 5
rand = Get64Bit

For i = 1 To 10
  rand = (6364136223846793005ull * rand + 1442695040888963407ull) And 18446744073709551615ull
  Print rand/2^64
Next
Print
For i = 1 To 10^7
  rand = (6364136223846793005ull * rand + 1442695040888963407ull) And 18446744073709551615ull
  randd = rand/2^64
  tot += randd
Next
Print tot/10^7
Print
t = Timer
For i = 1 To 10^7
  rand = (6364136223846793005ull * rand + 1442695040888963407ull) And 18446744073709551615ull
  randd = rand/2^64
  Asm nop ' Get off my loop!
Next
t = Timer - t
Print Int(10/t);" MHz"

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

Re: FreeBASIC's PRNG #2

Post by deltarho[1859] »

It is interesting to note that the multiplier in PCG32II is 6364136223846793005ull and the multiplier in Knuth64 is also 6364136223846793005ull.

We can then regard PCG32II as a Knuth64 with conditioning.
dafhi
Posts: 1640
Joined: Jun 04, 2005 9:51

Re: FreeBASIC's PRNG #2

Post by dafhi »

you can drop the and :D
deltarho[1859]
Posts: 4292
Joined: Jan 02, 2017 0:34
Location: UK
Contact:

Re: FreeBASIC's PRNG #2

Post by deltarho[1859] »

Paul Squires' latest WinFBE suite uses gcc 8.1 as opposed to gcc 5.2 the current version used in FreeBASIC.

Here are the results of using gcc 8.1 in the above tables:

Code: Select all

32-bit
 
5              1.40
1            424.47
3            437.29
CMWC4096     458.57
4            473.00
CryptoRndII  473.12
2            484.13
RndMT        600.70
xoshiro256   724.21
PCG32II      794.23
Knuth64      869.99
 
64-bit
 
5               1.60
1             529.50
RndMT         719.72
CMWC4096      808.68
3             839.87
CryptoRndII   954.92
4             991.85
2            1067.71
xoshiro256   1244.68
PCG32II      1324.75
Knuth64      1370.66
All algorithms are managing to get through more iterations for the time given them to run with varying degrees of improved performance. In particular, PCG32II and Knuth64 are 'pulling away' significantly and more so with 64-bit.

It does not follow that all code will have such a performance boost with gcc 8.1 but it must be worth trying out with some of your work.
deltarho[1859]
Posts: 4292
Joined: Jan 02, 2017 0:34
Location: UK
Contact:

Re: FreeBASIC's PRNG #2

Post by deltarho[1859] »

dafhi wrote:you can drop the and :D
Your second post lacking detail to the extent that I do not know what you are talking about. Perhaps it is just me.
Post Reply