FreeBASIC's PRNG #2

[deltarho[1859]]

X and w need not be set to zero on initialization.

In which case we have 2^63 streams/sequences to choose from.

Whichever we chose the random numbers generated will always be the same for the chosen stream.

In the random number generator market very few, if any, will buy into that.

I should have known that it was too good to be true.

The new king is dead - come back PCG32II - all is forgiven. <smile>

[paul doe]

X and w need not be set to zero on initialization.

In which case we have 2^63 streams/sequences to choose from.

Whichever we chose the random numbers generated will always be the same for the chosen stream.

In the random number generator market very few, if any, will buy into that.

I don't think I follow your reasoning. He clearly states that x and w need not be set to zero on init. Doesn't this mean that, seeding them with different values (and assuming the same valid initial stream), the outputs will be different?

[deltarho[1859]]

He clearly states that x and w need not be set to zero on init.

I misread Widynski's quote. I don't misread anything. "NURSE!"

I had a problem with some electronics yesterday and could not believe what I had done. I 'phoned a friend to give him a laugh. He said, "Were you having a senior moment, David?" I said, "Can you speak up - my hearing isn't as good as it used to be." <smile>

I suggest using the seed.h file from the download to initialize the s parameter. seed.h s values are chosen with different nibbles. This assures that the data is good on the very first iteration.

OK. So let us steer clear of generating our own sequence value.

I am now running 'Var randomNumber = MsWs( 123456, 42, Cast( Ulongint, &H8b5ad4cef9c2703b ) )', the sequence being used is the first one from seed.h, in PractRand and have just gone past 64GB with only a lowest ranking anomaly at 64GB. I shall let PractRand keep at it.

[dafhi]

I have to hand it to MsWs and PCG. They behave like they are built by professors. I quite like MsWs

[deltarho[1859]]

Just went past 128GB.

We could have a DATA block of 256, say, sequences from seed.h and have the third parameter of MsWs taking values from 1 to 256. That should keep most people happy. A value of zero could be used to choose a random value from the DATA block.

[deltarho[1859]]

@dafhi

The author of PCG is a Professor of Computer Science. I don't know about Bernard Widynski - he seems to be linked to Cornell University.

[dafhi]

Well, okay I knew PCG hailed from academia. They both align with 2^state bit boundary. I've seen both MsWs and PCG "warm up" at their own respective intervals though. Time to make a graphical output

[deltarho[1859]]

Time to make a graphical output

Pass. <smile>

[deltarho[1859]]

Talking of 'warm up'. One of Vigna's papers looked at this. A lot of generators have a slight bias early on. 'Burning' the initial 100 returns did the trick for the worst case. I 'burn' 200 in PCG32II. With MsWs we could burn 400 and that would only take, on my machine, one micro-second.

Just went past 256GB.

[dafhi]

Melgo is super-interesting. It needs lots of warming up

viewtopic.php?f=8&t=27007

[deltarho[1859]]

512GB

I'm outa here - it is getting late.

[paul doe]

I suggest using the seed.h file from the download to initialize the s parameter. seed.h s values are chosen with different nibbles. This assures that the data is good on the very first iteration.

OK. So let us steer clear of generating our own sequence value.

I don't think this was really the problem. The problem was that the initial sequence (albeit valid, according to the requirements) was too crappy to be of any practical use, and even less, pass through PractRand unscathed. The first test you conducted, which reached 2 TB without major issues, used a randomly generated stream, so why does it fail now? I mean, I know the stream you passed to it was PFA, but fully expanded it is &h0000000800000001, which looks a bit short of different nibbles to me =D

The isValidSequence() method will only tell you if the stream is valid, not it's quality. So, I'm suspecting that the tests that failed were due to a low quality stream, if I'm interpreting the cited paragraph from Bernard correctly.

So, to be on the safe side, I was thinking of only allowing the user to specify the initial 'x' value (which will then become the seed of the MSWS), and just use a good, valid random number to initialize both the stream and the Weyl sequence of the generator:

Code: Select all

var randomNumber = MSWS( _
  someSeed, _
  MSWS.validRandomSequence(), _
  MSWS.validRandomSequence() )

Test this setup, and let's see if it fails. If my impression is correct, then I shall modify the code to not allow the user to specify neither the Weyl sequence nor the stream itself...

[deltarho[1859]]

1Tb

So, 'Var randomNumber = MsWs( 123456, 42, Cast( Ulongint, &H8b5ad4cef9c2703b ) )' gets to a PractRand 1TB test with only a lowest ranking anomaly at 64GB.

Earlier I thought we had a problem with the Weyl sequence because both

Code: Select all

var randomNumber = MsWs(987654, 0, 8ull shl 32 or 1)
var randomNumber = MsWs(987654, 1, 8ull shl 32 or 1)

failed PractRand with MsWs.isValidSequence( 8ull shl 32 or 1 ) giving True.

From above 'Var randomNumber = MsWs( 123456, 42, Cast( Ulongint, &H8b5ad4cef9c2703b ) )' works to 1TB so I tried 'Var randomNumber = MsWs( 123456, 42, 8ull shl 32 or 1 )'. The only difference is the sequence which MsWs.isValidSequence tells me is OK.

That failed. I tried Cast( Ulongint, 8ull shl 32 or 1 ) and that failed. So, there is more to this sequence lark than meets the eye.

I don't think that we have a problem with the Weyl sequence so I reckon that we don't need to use MSWS.validRandomSequence() for it.

However, we do have a problem with the sequence/stream. I am not in favour of using MSWS.validRandomSequence() for this because '8ull shl 32 or 1' fails but passes MsWs.isValidSequence.

Widynski wrote "The constant s should be non-zero in the upper 32 bits and 1 in the least significant bit."

Your code, Paul, is doing just that. '8ull shl 32 or 1' does just that but fails.

This tells me that there is more to the constant s than Widynski realizes.

seed.h has 25000 values. I very much doubt that Widynski has tested that lot. They may all satisfy MsWs.isValidSequence but how many will fail because "there is more to this sequence lark than meets the eye."

I picked three at random and they worked. When I say worked I mean they got past the first PractRand hurdle - the failures were immediate. I cannot go through 25000 looking for a dead duck; assuming that there is one.

I have just tried 14,828,140,070,311,027,921 (CDC822D4C29FE4D1) which is not in seed.h. I have just gone past 128GB without a single anomaly. So, where did I get that number from? It is a bog standard 64-bit prime number. However, it satisfies Widynski's criteria so I am not proving anything.

Interestingly, '8ull shl 32 or 1' (34359738369) is not a prime number.

Perhaps Widynski's criteria are not strong enough. Perhaps the criteria plus 's' being a prime number is the answer.

However, 4294967423 (000000010000007F) is working. It satisfies Widynski's criteria but is not a prime number.

Houston, we have a problem. <smile>

[jj2007]

All the asm is doing is to map a 64-bit number into a Double [0,1).

Here is some code which uses two functions to do just that:
BASIC: TwoUlongsToDouble
ASM: TwoUlongsToDoubleASM

The asm is that used in CRyptoRndII.

I managed to shorten and speed it up a bit:

Code: Select all

*** Comparing SIMD vs FPU-based methods for mapping a QWORD (0...-1) to a double (0.0 ... 1.0) ***
Testing on Intel(R) Core(TM) i5-2450M CPU @ 2.50GHz
45      bytes for q2dx
41      bytes for q2d
original              SIMD                  FPU
digits ..........     1.2345678901234567    1.2345678901234567890
0                     0.0                   0.0
9223372036854775807   0.4999999999999998    0.4999999999999999999
-9223372036854775808  0.5000000000000000    0.5000000000000000000
-1                    0.9999999999999998    1.000000000000000000

PCG-32 random results:
-8910786331291756801  0.5169453050529669    0.5169453050529669718
6730337785313497944   0.3648523424199086    0.3648523424199086505
-5974524377861002328  0.6761203844977746    0.6761203844977747243

etc ... full test is here. Note that the SIMD-based procedure will never produce 1.0, due to the limitations of a double. The FPU method is a tick slower but offers full precision.

[srvaldez]

hello deltarho[1859]
have you had a look at A Birthday Test: Quickly Failing Some Popular PRNGs?
also like to ask, how do you use PractRand?
I had a look at How to Test with PractRand, is that how you run your tests?