FreeBASIC's PRNG #2

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

Re: FreeBASIC's PRNG #2

Post by deltarho[1859] »

paul doe wrote:Not sure if I understand what you mean.
Ah, we use that phrase in the UK but it appears to have originated in America.

Egg on one’s face

256GB without any anomalies.
dafhi
Posts: 1640
Joined: Jun 04, 2005 9:51

Re: FreeBASIC's PRNG #2

Post by dafhi »

I think he means my psychic attacks. They're not 100% intentional :P I'll try to tone it down.

[edit] oh i guess not - well I'd like to avoid avoid serious mistakes on my own part :D
Last edited by dafhi on Sep 14, 2018 16:35, edited 1 time in total.
paul doe
Moderator
Posts: 1730
Joined: Jul 25, 2017 17:22
Location: Argentina

Re: FreeBASIC's PRNG #2

Post by paul doe »

deltarho[1859] wrote:Ah, we use that phrase in the UK but it appears to have originated in America.
Ah, I see. Well, I think I'll fold'em now. Best of luck =D
paul doe
Moderator
Posts: 1730
Joined: Jul 25, 2017 17:22
Location: Argentina

Re: FreeBASIC's PRNG #2

Post by paul doe »

dafhi wrote:I think he means my psychic attacks. They're not 100% intentional :P I'll try to tone it down
Using Quark's words (perhaps you remember him):
Quark wrote: dafhi,

You are deeply strange. I'm thinking Jackson Pollock on meth, in a formal mood, doing not Legos, but Lagos.

I'm impressed, but about what I have no idea. Thanks for the code.
Hahahaha what an amusing fellow, indeed =D
deltarho[1859]
Posts: 4292
Joined: Jan 02, 2017 0:34
Location: UK
Contact:

Re: FreeBASIC's PRNG #2

Post by deltarho[1859] »

Widynski wrote:X and w need not be set to zero on initialization.
OK, this is the idea. It is ridiculously simple.

I sorted seed.h and found the largest one to be 0xfedc65a1ce2d9587.

and rewrote Bernard Widynski's algorithm to:

-----------------------------------------------------------------------------------
x *= x; x += (w += &hfedc65a1ce2d9587); return x = (x>>32) | (x<<32);

where x initially can be any value from 0 to 2^64-1. This gives 2^64 entry points to the 2^64 sequence. w initially can be any value from 0 to 2^64-1. This gives 2^64 possible sequences/streams; unlike most generators which only have one possible sequence/stream. The 0xfedc65a1ce2d9587 is a magic number. There are many possible magic numbers but they cannot be programmatically determined to guarantee that they will work.
-----------------------------------------------------------------------------------

The Weyl sequence is now our 'sequence' and the original sequence is no longer allowed to vary and cause the grief that we have had. We never needed three parameters.

I then ripped out any reference to the sequence in Paul's code.

The function MsWs.one was changed to:

Code: Select all

function MsWs.one() as ulong
  m_x *= m_x : m_weilSeq += &Hfedc65a1ce2d9587 : m_x += m_weilSeq
  m_x = ( m_x shr 32 ) or ( m_x shl 32 )
 
  return( m_x )
end function 
I use this:

Code: Select all

Function Get64Bit() As UlongInt
  return (Cast( Ulongint, Rnd*(2^32) ) Shl 32) Or Cast( Ulongint, Rnd*(2^32) )
End Function
and have only tried a few of these so far

Code: Select all

Randomize , 5
var randomNumber = MsWs( Get64Bit, Get64Bit )
I allowed one to go to 512GB with PractRand.

Both 'var randomNumber = MsWs()' and 'var randomNumber = MsWs( Get64Bit)' have worked.

I intend to continue testing but, logically, I cannot see how the above can fail.

I said that It was ridiculously simple.

I will post the revised code in due course. A lot of Paul's comments need editing now.
Last edited by deltarho[1859] on Sep 14, 2018 19:26, 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] »

Just out of interest.

Using 'var randomNumber = MsWs(Get64Bit, Get64Bit)' I got a [0,1) average of 0.4999782251326222

With 10^8 'x = randomNumber.one/2^32' I got a speed of 604MHz (32-bit Doubles) - very nearly 7 times faster than FB's Mersenne Twister.

I am running another PractRand using MsWs(Get64Bit, Get64Bit). Just two lowest ranking anomalies so far at 128GB.
dafhi
Posts: 1640
Joined: Jun 04, 2005 9:51

Re: FreeBASIC's PRNG #2

Post by dafhi »

that's some serious nice work. I get confused on details easily but it appears then that entry points of x and weyl can be user-defined. trying to imagine if that's 2^128 possibilities. *slaps self*

looks like you got a typo

Code: Select all

  m_x *= m_x : m_weilSeq += &Hfedc65a1ce2d9587 : m_x += m_weilSeq-
deltarho[1859]
Posts: 4292
Joined: Jan 02, 2017 0:34
Location: UK
Contact:

Re: FreeBASIC's PRNG #2

Post by deltarho[1859] »

dafhi wrote:trying to imagine if that's 2^128 possibilities
Although we are working on 'uint64_t x' we are only using the middle 32 bits so the output is 32-bit. The period is 2^64 per sequence/stream and we have 2^64 sequences/streams giving a total of 2^128.-
looks like you got a typo
Thank you. Corrected.

256GB <smile>
dafhi
Posts: 1640
Joined: Jun 04, 2005 9:51

Re: FreeBASIC's PRNG #2

Post by dafhi »

deltarho[1859] wrote:.. using the middle 32 bits ..
actually it's the bottom 32 bits :P

the shl 32 gymnastics is a state rotation

[edit] i take it back. did some studying, saw what is meant by middle bits
Last edited by dafhi on Nov 18, 2018 23:18, edited 1 time in total.
paul doe
Moderator
Posts: 1730
Joined: Jul 25, 2017 17:22
Location: Argentina

Re: FreeBASIC's PRNG #2

Post by paul doe »

deltarho[1859] wrote:
Widynski wrote:X and w need not be set to zero on initialization.
OK, this is the idea. It is ridiculously simple.

I sorted seed.h and found the largest one to be 0xfedc65a1ce2d9587.

and rewrote Bernard Widynski's algorithm to:

-----------------------------------------------------------------------------------
x *= x; x += (w += &hfedc65a1ce2d9587); return x = (x>>32) | (x<<32);

where x initially can be any value from 0 to 2^64-1. This gives 2^64 entry points to the 2^64 sequence. w initially can be any value from 0 to 2^64-1. This gives 2^64 possible sequences/streams; unlike most generators which only have one possible sequence/stream. The 0xfedc65a1ce2d9587 is a magic number. There are many possible magic numbers but they cannot be programmatically determined to guarantee that they will work.
-----------------------------------------------------------------------------------

The Weyl sequence is now our 'sequence' and the original sequence is no longer allowed to vary and cause the grief that we have had. We never needed three parameters.
Excellent. Simple, and even has less state to worry about.
deltarho[1859] wrote:I use this:

Code: Select all

Function Get64Bit() As UlongInt
  return (Cast( Ulongint, Rnd*(2^32) ) Shl 32) Or Cast( Ulongint, Rnd*(2^32) )
End Function
and have only tried a few of these so far

Code: Select all

Randomize , 5
var randomNumber = MsWs( Get64Bit, Get64Bit )
So, it needs two seeds? Or we can simply randomly initialize the Weyl sequence so we can specify one parameter (x) as the seed for the entire state? We can also allow to specify the Weyl sequence and leave x at 0 (or randomized, again). Whichever suits you fancy.
deltarho[1859] wrote:I allowed one to go to 512GB with PractRand.

Both 'var randomNumber = MsWs()' and 'var randomNumber = MsWs( Get64Bit)' have worked.

I intend to continue testing but, logically, I cannot see how the above can fail.

I said that It was ridiculously simple.

I will post the revised code in due course. A lot of Paul's comments need editing now.
Yes, but sometimes, the simplest answers are the most elusive. Why the comments would need editing? Leave them as they are, to document the thought process and how the solution was derived. If you mean the code, also leave it. Changing it will make the following discussion pointless. I can post both the 32 and 64-bit revised versions if you like for further testing.

Well done! =D
paul doe
Moderator
Posts: 1730
Joined: Jul 25, 2017 17:22
Location: Argentina

Re: FreeBASIC's PRNG #2

Post by paul doe »

deltarho[1859] wrote:Just out of interest.

Using 'var randomNumber = MsWs(Get64Bit, Get64Bit)' I got a [0,1) average of 0.4999782251326222

With 10^8 'x = randomNumber.one/2^32' I got a speed of 604MHz (32-bit Doubles) - very nearly 7 times faster than FB's Mersenne Twister.

I am running another PractRand using MsWs(Get64Bit, Get64Bit). Just two lowest ranking anomalies so far at 128GB.
That's very cool, David. If everything turns out ok, I think you should contact Bernard and take due credit for this improvement. You deserve it =D
deltarho[1859]
Posts: 4292
Joined: Jan 02, 2017 0:34
Location: UK
Contact:

Re: FreeBASIC's PRNG #2

Post by deltarho[1859] »

paul doe wrote:So, it needs two seeds?
Yes.

I have kept to your Contructor design.
1) MsWs() => both seeds as zero.
2) MsWs( <parameter> ) => Seed as <parameter>, Sequence as zero.
3) MsWs( <parameter1>, <parameter2> ) => Seed as <parameter1>, Sequence as <Parameter2>

Users who are used to FB's generators and want to keep it that simple will opt for 2). Savvy users who want to get into sequencing will opt for 3).
Why the comments would need editing?
Many of the comments refer to the sequence which my version does not use.

Actually, it would suit me not to post my version - less work for me. Folks have your code above and what I have done so it is easy for them to write their own.
I think you should contact Bernard and take due credit for this improvement. You deserve it =D
Yours truly earlier wrote:If ever it [PCG32II] got in FB there would be no need to mention that I had anything to do with it - I am not into that. O'Neill should be credited, of course.
Some folk may think that rather odd but it is how I am. BasicCoder2 and I have something in common (fellow INTP): We like breaking things down to understand how they work. BasicCoder2 is a practical guy and I am a theory guy. Once I have understood something and, perhaps, found a better way to do the same job I then move on. I couldn't care less about credit.

The next step is to wrap MsWs as I did with PCG to make it as easy to use.

512GB <smile>
deltarho[1859]
Posts: 4292
Joined: Jan 02, 2017 0:34
Location: UK
Contact:

Re: FreeBASIC's PRNG #2

Post by deltarho[1859] »

MsWs( GetBit64, GetBit64 ) hard-wired 'sequence' => 1TB PractRand, two lowest ranking anomalies.
paul doe
Moderator
Posts: 1730
Joined: Jul 25, 2017 17:22
Location: Argentina

Re: FreeBASIC's PRNG #2

Post by paul doe »

deltarho[1859] wrote:Many of the comments refer to the sequence which my version does not use.

Actually, it would suit me not to post my version - less work for me. Folks have your code above and what I have done so it is easy for them to write their own.
Very well. I shall post a final, directly usable version as soon as I finish it.
deltarho[1859] wrote:
Yours truly earlier wrote:If ever it [PCG32II] got in FB there would be no need to mention that I had anything to do with it - I am not into that. O'Neill should be credited, of course.
Some folk may think that rather odd but it is how I am. BasicCoder2 and I have something in common (fellow INTP): We like breaking things down to understand how they work. BasicCoder2 is a practical guy and I am a theory guy. Once I have understood something and, perhaps, found a better way to do the same job I then move on. I couldn't care less about credit.
Not a problem to me. I'll take the credit then <bwahahahahaha> Well, not really =D
deltarho[1859] wrote:MsWs( GetBit64, GetBit64 ) hard-wired 'sequence' => 1TB PractRand, two lowest ranking anomalies.
Nice! Uncork the champagne =D
deltarho[1859]
Posts: 4292
Joined: Jan 02, 2017 0:34
Location: UK
Contact:

Re: FreeBASIC's PRNG #2

Post by deltarho[1859] »

A final word on something which has not been mentioned. Bot PCG32II and MsWs have something in common: They are both thread safe.
Post Reply