Seeding FB generators

General FreeBASIC programming questions.
jj2007
Posts: 2326
Joined: Oct 23, 2016 15:28
Location: Roma, Italia
Contact:

Re: Seeding FB generators

Post by jj2007 »

deltarho[1859] wrote:@jj2007

I'd like a Ulongint version of HammingSeed. I could go past HammingSeed twice but would rather have a single function. However, I want to avoid reading the timestamp twice in close succession. Is there an asm instruction which would pause the asm for a small amount of time to allow the timestamp to 'spin' a little or should I use a simple loop?
There is no handy instruction (afaik). Looping is easy:

Code: Select all

  xor ecx, ecx
  lbl: loop lbl
With ecx=0, that takes over five seconds on my machine; choose any value you like. For example, mov ecx, 666666 finishes in one millisecond. However, the two timestamps will not be independent from each other. Perhaps you should bswap eax one of them.
deltarho[1859]
Posts: 4292
Joined: Jan 02, 2017 0:34
Location: UK
Contact:

Re: Seeding FB generators

Post by deltarho[1859] »

@jj2007

What I was thinking of doing was a bswap eax on one and a rol eax, 8 followed by a bswap eax on the other so that they both have their sequence broken with no partial commonality going on.
deltarho[1859]
Posts: 4292
Joined: Jan 02, 2017 0:34
Location: UK
Contact:

Re: Seeding FB generators

Post by deltarho[1859] »

Yes, that looks OK. I won't post the code here because it is not relevant to this thread. However, it could be used with something like xoshiro256** which has a state vector of four Ulongints.
dodicat
Posts: 7976
Joined: Jan 10, 2006 20:30
Location: Scotland

Re: Seeding FB generators

Post by dodicat »

Would this do as a 64 bit Hammingseeder with 50% weight?
Since rdtsc is 32 bits, and I can find no 64 bit equivalent I have kept the register eax and used dword, rather than rax and qword.

Code: Select all



Function popcount64(x As Ulongint) As Ulong
      If x=&hffffffffffffffffull Then Return 64
      x -= ((x Shr 1) And &h5555555555555555ull)
      x = (((x Shr 2) And &h3333333333333333ull) + (x And &h3333333333333333ull))
      x = (((x Shr 4) + x) And &hf0f0f0f0f0f0f0full)
      x += (x Shr 8)
      x += (x Shr 16)
      x+= (x Shr 32)
      Return x And &h0000003full
End function

function reverseuLongint(x As Ulongint) As Ulongint
      x = (x And &h00000000ffffffffull) Shl 32 Or (x And &hffffffff00000000ull) Shr 32
      x = (x And &h0000ffff0000ffffull) Shl 16 Or (x And &hffff0000ffff0000ull) Shr 16
      x = (x And &h00ff00ff00ff00ffull) Shl 8  Or (x And &hff00ff00ff00ff00ull) Shr 8
      Return x
End function


function HammingSeed64() As Ulongint
      Dim As Ulong seed,numbits
      Dim As Ulongint  CopySeed
      While numBits <> 32
            Asm
                  rdtsc    ' Get a fast changing number from the processor, only 32 bits
                  mov dword Ptr [Seed], eax
            End Asm
            CopySeed = seed * 4294967295ull'thrust into a 64 bit range
            numbits=popcount64(copyseed)
      Wend
      Return reverseulongint(copyseed) 'use a 64 bit swapper
End function

Var b= hammingseed64
Print "example seed:"
Print Bin(b),popcount64(b),b
Print
Print

Dim As Double t,t1,t2,z
Dim As Double tall
Dim As Ulongint x
Dim As Ulong lim=10000000'0

for k As Long=1 To 5
      z=0
      tall=Timer
      for n As Long=1 To lim
            t1=Timer
            x=hammingseed64()
            t2=Timer
            t=t2-t1
            If z<t Then z=t
      Next n
      Print "max ";z*1000000,"Total time ";Timer-tall;"    seed = ";x;", bits(1) = ";popcount64(x)
Next k
print "Done"
Sleep



 
Results

Code: Select all

example seed:
11011010111011011111101010100111001001010001001000000101010110        32            3943885166384283990


max  177.5999553501606      Total time  0.5283426999812946    seed = 8496952516613030580, bits(1) = 32
max  88.99997919797897      Total time  0.5263170000398532    seed = 527271823179432210, bits(1) = 32
max  56.80008325725794      Total time  0.5263580000028014    seed = 3839949320077296240, bits(1) = 32
max  24.60007090121508      Total time  0.52041310002096    seed = 1262486957552484045, bits(1) = 32
max  37.50005271285772      Total time  0.5205271999584511    seed = 12418198601147724330, bits(1) = 32
Done
 
Last edited by dodicat on Jun 09, 2021 22:10, edited 1 time in total.
deltarho[1859]
Posts: 4292
Joined: Jan 02, 2017 0:34
Location: UK
Contact:

Re: Seeding FB generators

Post by deltarho[1859] »

dodicat wrote:and I can find no 64 bit equivalent
There isn't one - 32-bit is as good as it gets.

I haven't spent any time debugging, but your code is 'bottlenecking' somewhere. I reduced the workload quite a bit, but the console just sits there with a flashing cursor. Your code looks expensive. I can see what you are trying to do, and I would call it entropy injection.

I scrapped my last idea after examining the 64-bit results, as they were not sufficiently different for my liking. Having said that, being different is not a prerequisite. Some PRNG authors will tell us to never use zero as a seed, but I haven't seen anyone say don't use seeds of the same value.

The crazy thing is the best results were got from combining two 32-bit outputs. The function overhead of the second call gave just enough separation between the two rdtsc calls.
dodicat
Posts: 7976
Joined: Jan 10, 2006 20:30
Location: Scotland

Re: Seeding FB generators

Post by dodicat »

I have fixed the code to suit 32 bits and 64 bits.
The two function innards could be inlined into the hammingseed64 for a little boost, but because the popcount64 doesn't require a loop it is quite fast.
deltarho[1859]
Posts: 4292
Joined: Jan 02, 2017 0:34
Location: UK
Contact:

Re: Seeding FB generators

Post by deltarho[1859] »

@dodicat

That's better - thanks.

It's getting a bit late, so I'll give a good workout tomorrow.

Being an analytical PITA I noticed that if we take the top 32 bits of HammingSeed64 and XOR it with the bottom 32 bits we always get 2^32-1, so we haven't injected any entropy at all. I doubt that matters - what matters is a 50% Hamming weight, and we get that.
deltarho[1859]
Posts: 4292
Joined: Jan 02, 2017 0:34
Location: UK
Contact:

Re: Seeding FB generators

Post by deltarho[1859] »

@dodicat

If we take the top 32-bit of your 64-bit output and call it x then the bottom 32-bit is 'Not x'. The two 32-bit sections may have differing Hamming weights. For example, we could have 15 set bits in the top 32-bit and 17 set bits in the bottom 32-bit; giving a total of 32 ie 50%.

I then looked at my HammingSeed, which returns a 32-bit, and with a value of x, say, I determine mkulongint( x, Not x ) where

Code: Select all

Function mkulongint(n1 As Ulong, n2 As Ulong) As Ulongint ' by MrSwiss
  Dim As Ulongint res
  Cast(Ulong Ptr,@res)[0]=n1
  Cast(Ulong Ptr,@res)[1]=n2
  Return res
End Function
Both 32-bit sections will have a Hamming weight of 50%.

The $64,000 question: Who is faster in 32-bit mode?

Looking at the code with all those Shr going on in popcount64 and reverseuLongint I figured my code would have the edge.

Here is the result of one run:

Code: Select all

max  93.58732495456934      Total time  20.55839813436614    seed = 9876365401811589630, bits(1) = 32
max  84.29843001067638      Total time  20.5543753465754    seed = 404132379232582590, bits(1) = 32
max  52.0317698828876       Total time  20.56150362687185    seed = 12798398361755645055, bits(1) = 32
max  72.42540596053004      Total time  20.54087418928975    seed = 17350642864970146365, bits(1) = 32
max  75.49842121079564      Total time  20.55441361962585    seed = 5653663512825308925, bits(1) = 32
 
max  222.9333622381091      Total time  23.55614498490468    seed = 12546855733743885615, bits(1) = 32
max  194.3683018907905      Total time  23.53725068410859    seed = 9419557490678760030, bits(1) = 32
max  181.5174473449588      Total time  23.53084463253617    seed = 9723528281949410955, bits(1) = 32
max  195.5556217581034      Total time  23.55422805133276    seed = 2404895000428026045, bits(1) = 32
max  198.8380681723356      Total time  23.5312987404759    seed = 7079608129532472810, bits(1) = 32
Done
I was wrong! The top results are yours. Image

Your max values are better than half mine. Your popcnt replacement is fast.
The two function innards could be inlined into the hammingseed64 for a little boost,
With an average of about 76 microseconds for your max values we don't need a boost and the code as is will do fine.

The next question is: Have you got a new computer because your 'Total time' figures are leaving mine standing?
Post Reply