MsWsII PRNG plus Help file

General FreeBASIC programming questions.
dodicat
Posts: 7978
Joined: Jan 10, 2006 20:30
Location: Scotland

Re: MsWsII PRNG plus Help file

Post by dodicat »

I noticed that you scrapped using the variable temp in duo
you have
' u.Output64 = Temp Xor This.Seed2
u.Output64 Xor= This.Seed2

I have tried to speed up duo using the temp (or not using the temp)

private sub MsWsParams.GetDuo2(byref one as double,byref two as double)
const as double k=1/2^32
Dim As Uint64 Temp
Engine2
dim as ulongint n =Temp Xor This.Seed2
' n Xor= This.Seed2
one=k*cast(ulong ptr,@n)[0]
two=k*cast(ulong ptr,@n)[1]
end sub

But very little gain, using temp or using Xor= This.Seed2
deltarho[1859]
Posts: 4292
Joined: Jan 02, 2017 0:34
Location: UK
Contact:

Re: MsWsII PRNG plus Help file

Post by deltarho[1859] »

Thanks, dodicat.

A few posts back, I mentioned Widynski's Table 1.

Code: Select all

Table 1: Time to generate and
sum one billion random numbers
 
  RNG   Precision  Time
msws64     32      0.87
xoroshiro  53      1.09
msws32     32      1.18
xorwow     32      1.26
msws64     53      1.29
The 0.87 figure was got by timing half a billion pairs which led him to write 'msws64 may
be the fastest RNG for producing floating-point numbers' because 0.87 is better than 'msws32 32 1.18'.

I get the feeling that this aspect was an afterthought, and he did not consider it in practice. He seems to be equating half a billion pairs with one billion singletons.

For me, the question is what do we do with the half billion pairs r1 and r2 just above his table. We cannot discard one of them as we now have half a billion singletons which cannot be compared with one billion singletons got from msws32. We now have 2 x 0.87 which is greater than 1.18.

We have to cache one of the pairs, and the extra code for that will increase the 0.87. That 0.87 is then misleading.

I looked at cacheing with a procedure that I called GetMono but found that the throughput fell from 789MHz to 388MHz, so I did not introduce it.

I do not have any issues with the rest of his paper, but I reckon he is jumping to conclusions with the getting of two 32's from one 64 method without examining it in practice.

I am reminded of the transition from USB 2 to USB 3. On paper, 3 looked like being ten times faster than 2. On manufacture, we got 4 times – still impressive, but not as impressive as ten times.

By the way 'const as double k=1/2^32' is needed for gas but with gcc optimized with -O1 and above the division is replaced with a multiplication by the compiler, so we can use '/2^32' in our code.
deltarho[1859]
Posts: 4292
Joined: Jan 02, 2017 0:34
Location: UK
Contact:

Re: MsWsII PRNG plus Help file

Post by deltarho[1859] »

I have found a problem with the Gauss procedure.

If we request an odd number of values, then the cached value of u2 will be unused. Restoring to a snapshot or the initial state will see the unused cached value returned; which is not what we want. In fact, the following sequence will be as if we took a snapshot at the unused cached value.

The cache status was recorded in a Static value in the procedure. This was removed. The cache status is now recorded in 'Type MsWsParams' as 'Cache As Boolean' and that is updated in the procedure.

If we do either SetEngine1Snapshot or RestoreEngine1InitialState the first statement is now 'This.Cache = False'. On returning to Gauss the code is forced to get two new values whether the cached value had been used or not.

This works. The correct sequence is now restored, whether the previous requests were even or odd.

There are four areas that require a change. I won't ask you to do that. OP has been edited, so copy the whole source code.
deltarho[1859]
Posts: 4292
Joined: Jan 02, 2017 0:34
Location: UK
Contact:

Re: MsWsII PRNG plus Help file

Post by deltarho[1859] »

Not quite there. :)

I didn't do all possible tests.

We could have nothing cached, take a snapshot, request an even number, and then restore or request an odd number and then restore. Alternatively, we could have a cached value, take a snapshot, request an even number, and then restore or request an odd number and then restore. So four possibilities – I only tested two. What I had to do if there was a cached value was to burn a Gauss before taking a snapshot. We don't have a similar issue restoring the initial state.

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

Re: MsWsII PRNG plus Help file

Post by deltarho[1859] »

From FB's Help: “However, it is generally not worth calling Randomize twice with unpredictable seeds anyway, because the second sequence will be no more random than the first, or even possibly worse by inducing sequence overlapping.”

“it is generally not wort hcalling Randomize twice”

I wonder if someone has good reason to call Randomize more than once.

We haven't got that with MsWsII. The Contructor will choose three unique 's' values from "Mysvalues.bi" and they will persist for the duration of our application. Not now, we have a new procedure called, imaginatively, Reboot. :)

Reboot will completely reset the generator. Three new 's' values will be selected that have not been used before, so there is no chance of a sequence overlap.

How long will that take, I hear you ask. On my machine it takes between one and two milliseconds. It varies because the seeding time varies.

We can Reboot up to 5460 times before we run out of 's' values. If anyone contemplates that, they can expect a visit from a couple of guys to fit them out with a straight jacket.

So, who will use Reboot? I have no idea, but the option is there if needed.

Some will no doubt reckon that Reboot is feature creep. I won't argue with that and reckon this is a good time to call it a day on this project.

OP edited.

I will update the Help file in a few days.

Here is an example:

Code: Select all

#include "MsWsII.bas"
 
For i As Uint32 = 1 To 4
  ? Rnd
next
 
?
Dim As Double t
t = Timer
msws.Reboot
?  "Reboot:";Int((Timer - t)*10000)/10;"ms"
?
For i As Uint32 = 1 To 4
  ? Rnd
next
msws.RestoreEngine1InitialState
?
? "Restore initial state"
?
For i As Uint32 = 1 To 4
  ? Rnd
Next
 
Sleep

and I got:

Code: Select all

 0.01287209684960544
 0.7558938444126397
 0.1229411512613297
 0.7868493371643126
 
Reboot: 1.3ms
 
 0.06937205046415329
 0.2783500282093883
 0.9040805033873767
 0.6084899259731174
 
Restore initial state
 
 0.06937205046415329
 0.2783500282093883
 0.9040805033873767
 0.6084899259731174
deltarho[1859]
Posts: 4292
Joined: Jan 02, 2017 0:34
Location: UK
Contact:

Re: MsWsII PRNG plus Help file

Post by deltarho[1859] »

MsWsII.bas has had a major overhaul.

In previous versions, the Constructor effectively set up a generator by choosing 's' values, initializing and making a note of the initial state.

What we now have is:

Code: Select all

Constructor MsWsParams( SkipSetup As Boolean = False )
  If SkipSetup = False Then Setup
End Constructor
 
Sub MsWsParams.Setup
Dim As Uint32 ubnd
...
...
...
End Sub
where the procedure Setup's task is the same as the previous Constructor's task was.

If the new Constructor's parameter is False then Setup will set up a generator in the same way as the old Constructor did. If we don't specify, a parameter then False will be used as a default. However, if the new Constructor's parameter is True then Setup is not executed. The new version of MsWsII.bas is then backwards compatible with older versions. So, any application using the older MsWsII.bas does not require any editing when the new version is used.

Why on earth should Setup not be executed? All the generator's metrics would be zero.

The FreeBASIC generators and all of my PRNG's implementations have one thing in common: With a random entry point into a generator sequence it is possible to move toward a sequence or fall into a sequence that has been used by a previous application session. In other words, there is a possibility of a sequence overlap.

There are two aspects of MsWsII which mitigate that possibiity: the first being allowed different sequences to choose from, as opposed to just one, and secondly a period of 2^64. PCG32II is better in this respect by having 2^63 different sequences to select from. With a generator period of 2^32 the likelihood of a sequence overlap increases.

It should be said that the probability of a sequence overlap with MsWsII is small unless previous application sessions have used a large number of random number requests, but it is not impossible.

Someone may say: "That is all very well but I want a guarantee that no matter how many times an application is used I will never see a sequence that has been used previously. As MsWsII stood, that guarantee was not possible.

One way to provide such a guarantee is to make a copy of the generator's metrics to what I call a metrics file just before an application closes. I use the term metrics rather than state because more than the state vector is saved. On an application's re-opening, we simply load the metrics file. With this approach, all previous sequences are 'behind', so to speak, our loaded metrics sequence 'entry point' and therefore cannot be repeated; unless we go beyond the generator's period and with a period of 2^64 that will not happen. This is where the Constructor's parameter of True comes in. In this case, Setup is not executed otherwise if allowed to, the time and work involved would be wasted as the metrics determined would be overwritten when the metrics file is loaded.

To this end, two new procedures have been introduced: SaveMetrics( fiename As String ) and LoadMetrics( filename As String ).

This is what we use, in pseudocode, at the head of our application:

Code: Select all

Dim As Boolean SkipSetup
If FileExists( <metrics file> ) Then SkipSetup = True Else SkipSetup = False
Dim Shared As MsWsParams gen1 = SkipSetup
If SkipSetup Then gen1.LoadMetrics( <metrics file> )
For the application's footer, we would use:

Code: Select all

gen1.SaveMetrics( <metrics file> )

where gen1 is the name of the generator that we want to have the guarantee. We may have more than one generator and require more than one to have a guarantee, so need to code appropriately. To keep life simple, I would call the metrics file above, gen1SavedMetrics.dat. If we want to guarantee msws, the default generator created at the foot of MsWsII.bas, then the code at the foot of MsWsII.bas should be removed.

The first time that an application runs a metrics file will not be found, so SkipSetup will be False and Setup will execute unencumbered. The second and subsequent application runs will find a metrics file, so SkipSetup will not be executed.

When SkipSetup is False, it takes longer to set up the generator compared with loading the metrics file. However, all the timings are so small it is doubtful that anyone would notice a difference. On my machine with SkipSetup as False the time taken to set up the generator is about 17 milliseconds. The loading and saving are in the microsecond domain.

You may think that with all the work that I have done with PRNGs that I am a power user with many generators being created, but I am not. Most of the time I use just one generator, so don't need any more than the default 'msws' created at the foot of MsWsII.bas. Not having a guarantee to avoid sequence overlapping is not something that concerns me.

Having said that, a guarantee is appealing, as whether sequence overlapping may be an issue is rendered academic.

If the foot of MsWsII.bas is removed and I use this:

Code: Select all

' **********
' Header
#include once "file.bi"
#Include Once "MsWsII.bas"
Dim As Boolean SkipSetup
If FileExists( "mswsSavedMetrics.dat" ) Then SkipSetup = True Else SkipSetup = False
Dim Shared As MsWsParams msws = SkipSetup
If SkipSetup Then msws.LoadMetrics( "mswsSavedState.dat" )
#undef Rnd
#define Rnd msws.randse
#define RndD msws.randd
#define Range_ msws.range
' **********
 
' Application code
For i As Uint32 = 1 to 10
  ? Rnd
Next
 
' **********
' Footer
msws.SaveMetrics( "mswsSavedMetrics.dat" )
' **********
 
Sleep
I now get a PRNG behaving as if a cryptographic PRNG (CPRNG) where sequence overlapping cannot occur.

If a particular generator is used without a guarantee and we subsequently change our mind we may have left it too late as a saved 'entry point' may be 'behind' a sequence used in a previous application session and we will be defeated. So, we should code for a guaranteed environment before running an application for the first time.

If a particular generator has a guarantee, and we then stop saving the metrics, then the entry point into a sequence will be the same for each application session. You may think that would be handy for testing two different algorithms – close the application after testing the first algorithm, and then run again using the second algorithm. There is no need to do that as we can test two algorithms in the same run. All we have to do is to return to the initial state and then test the second algorithm. Alternatively, we can take a snapshot before the first test and return to that before the second test. This approach has been available since the first MsWsII.bas.

It is worth mentioning again that the new MsWsII.bas does not require any changes to existing applications and new applications may be coded in the same way as the previous MsWsII.bas so it is worthwhile to replace the previous MsWsII.bas as one day you may want a guarantee. I have decided to use the above as I cannot resist having an application which may be closed/opened many times but always have the generator moving forward.

MsWsII.bas V1.5 in opening post.

New Help file to follow.
deltarho[1859]
Posts: 4292
Joined: Jan 02, 2017 0:34
Location: UK
Contact:

Re: MsWsII PRNG plus Help file

Post by deltarho[1859] »

Proof of concept for Save/Load.

We create two generators: msws1 and msws2.

Both are given some work to do, and then the metrics for both are saved.

Unusually, we print four floats for each.

We then load the metrics, which were saved before printing the floats, and then print four floats for each.

The second block should be a repeat of the first block.

Fortunately, for me, they are. :)

Code: Select all

'#console on
#Include "MsWsII.bas"
Dim As MsWsParams msws1, msws2
' Do some work
For i As Uint32 = 1 To 1000
  msws1.randse
Next : ?
For i As Uint32 = 1 To 1000
  msws2.randse
Next
' Save the generators' metrics
msws1.SaveMetrics( "msws1SavedMetrics.dat" )
msws2.SaveMetrics( "msws2SavedMetrics.dat" )
' For testing purposes print 4 random floats
For i As uint32 = 1 To 4
? msws1.randse
Next : ?
For i As uint32 = 1 To 4
? msws2.randse
Next : ?
' Load metrics
msws1.LoadMetrics( "msws1SavedMetrics.dat" ) ' The metrics before the 4 above were printed
msws2.LoadMetrics( "msws2SavedMetrics.dat" ) ' The metrics before the 4 above were printed
' We should get a repeat of those printed above
? "*******************" : ?
For i As uint32 = 1 To 4
? msws1.randse
Next :?
For i As uint32 = 1 To 4
? msws2.randse
Next
Sleep
Typical output:

Code: Select all

 0.940147859044373
 0.5192935804370791
 0.3419644772075117
 0.9417342054657638

 0.1065423283725977
 0.8482171911746264
 0.01351326238363981
 0.02601559227332473

*******************

 0.940147859044373
 0.5192935804370791
 0.3419644772075117
 0.9417342054657638

 0.1065423283725977
 0.8482171911746264
 0.01351326238363981
 0.02601559227332473
dodicat
Posts: 7978
Joined: Jan 10, 2006 20:30
Location: Scotland

Re: MsWsII PRNG plus Help file

Post by dodicat »

These work also

Code: Select all

Private Sub MsWsParams.SaveMetrics2( filename As String )
Dim As Long f = FreeFile
  If FileExists( filename ) Then Kill ( filename )
  Open filename For Binary As #f
    Put #f, , this
  Close #f
End Sub

Private Sub MsWsParams.LoadMetrics2( filename As String )
Dim As Long f = FreeFile
  Open filename For Binary As #f
    Get #f, , this
  Close #f
End Sub
 
deltarho[1859]
Posts: 4292
Joined: Jan 02, 2017 0:34
Location: UK
Contact:

Re: MsWsII PRNG plus Help file

Post by deltarho[1859] »

The reason that I didn't use 'this' is because I didn't know we could.

The beauty of this approach is that we can add/remove data elements to/from a Type without having to do the same with Save/Load procedures.

Thanks, dodicat. :wink:

MsWsII.bas V1.6 in opening post.

PS Where is this technique mentioned in the manual – I cannot find it.
fxm
Moderator
Posts: 12085
Joined: Apr 22, 2009 12:46
Location: Paris suburbs, FRANCE

Re: MsWsII PRNG plus Help file

Post by fxm »

Extracted from documentation:
Put #filenum As Long, [position As LongInt], data As Any [, amount As UInteger]
  • data
    • Is the buffer where data is written from. It can be a numeric variable, a string, an array or a user-defined type. The operation will try to transfer to disk the complete variable, unless amount is given.
Get #filenum As Long, [position As LongInt], ByRef data As Any [, [amount As UInteger] [, ByRef bytesread As UInteger] ]
  • data
    • The buffer where data is written. It can be a numeric variable, a string, an array, a user defined type or a dereferenced pointer. The read operation will try to fill completely the variable, unless the EOF is reached.
deltarho[1859]
Posts: 4292
Joined: Jan 02, 2017 0:34
Location: UK
Contact:

Re: MsWsII PRNG plus Help file

Post by deltarho[1859] »

@fxm

I read those but, to my mind, requires quite a leap to realize that 'Put #f, , this', for example, is within those definitions.

The above should be specifically mentioned in the Put(File I/O), Get(File I/O), and the 'This' topics in the manual.

I would not be surprised to learn that many members were not aware of the above and have been members much longer than me.
fxm
Moderator
Posts: 12085
Joined: Apr 22, 2009 12:46
Location: Paris suburbs, FRANCE

Re: MsWsII PRNG plus Help file

Post by fxm »

'This' is a UDT instance reference. Using it is therefore equivalent to using the instance declaration name itself.
I will point out this in documentation, at least on the 'Put' and 'Get' pages.
deltarho[1859]
Posts: 4292
Joined: Jan 02, 2017 0:34
Location: UK
Contact:

Re: MsWsII PRNG plus Help file

Post by deltarho[1859] »

fxm wrote:'This' is a UDT instance reference. Using it is therefore equivalent to using the instance declaration name itself.
That is clearer than the manual, :)
fxm
Moderator
Posts: 12085
Joined: Apr 22, 2009 12:46
Location: Paris suburbs, FRANCE

Re: MsWsII PRNG plus Help file

Post by fxm »

fxm wrote: May 24, 2022 5:00 'This' is a UDT instance reference. Using it is therefore equivalent to using the instance declaration name itself.
I will point out this in documentation, at least on the 'Put' and 'Get' pages.
Done:
- KeyPgThis → fxm [using 'This' in non-static member functions is equivalent to using the instance declaration name itself]
- KeyPgPutfileio → fxm ['This' can also be used as argument for writing all non-static data of an UDT instance]
- KeyPgGetfileio → fxm ['This' can also be used as argument for filling all non-static data of an UDT instance]
deltarho[1859]
Posts: 4292
Joined: Jan 02, 2017 0:34
Location: UK
Contact:

Re: MsWsII PRNG plus Help file

Post by deltarho[1859] »

@fxm

You did not use this phrase: 'This' can also be used as argument for writing all non-static data of an UDT instance.

but used '(including referenced by This)'.

The second one still needs a leap – not helpful.

The first one is better, but I think you meant to write 'static data'.
Post Reply