On Hamming Weight

[deltarho[1859]]

Just a quick one.

I have been playing around with Hamming Weight of late. Simply, with a Ulong of all reset bits the Hamming Weight is zero. With a Ulong of all set bits the Hamming Weight is 32. With "01101100010011110110101110010011", for example, we have a Hamming Weight of 18, the number of set bits.

The combinations of ones in a Ulong form a binomial distribution so the average Hamming Weight will be 16.

It occurred to me that this would be a good way to check a PRNG's distribution uniformity on the 32-bit outputs.

Running six tests of 10^8 passes per PRNG and taking the average, I get this.

Code: Select all

CryptoRndII 16.00002775
PCG32II     16.00006797
MsWs        16.00016002
Squares     15.99972075
SFC32       15.99967304

Not surprisingly, CryptoRndII won, being a CPRNG. Our old friend PCG32II did exceptionally well. MsWs has nothing to be ashamed about. Squares and SFC32 are behind, but still not bad.

I did a similar exercise with PowerBASIC's RND and it got 15.5. I think PB's RND is a LCG and it may be a variant which only outputs odd numbers. That would explain 15.5, 31/2. With some applications, that may not be an issue. However, its period is only 2^32, it fails PractRand at 4KB and is not particularly fast. Needless to say, I stopped using it a long time ago and why I wrote CryptoRndII.dll and PCG32.dll - not just for PB's members but for me, as well.

CryptoRndII and PC32II are ideal for Monte Carlo work, remembering that CryptoRndII is Windows-based.

GetHammingWeight

Code: Select all

Function GetHammingWeight( ByVal GivenDW As Ulong ) As long
Asm
  mov eax, Dword Ptr GivenDW
  xor ecx, ecx ' Number of ones
0:
  test eax, eax
  jz 1f
  mov edx, eax
  dec edx
  and eax, edx
  inc ecx
  jmp 0b
1:
  mov [Function], ecx
End Asm
End Function

Print GetHammingweight( &B01101100010011110110101110010011) ==> 18

[deltarho[1859]]

Regarding the 64-bit output generators, which perform better in 64-bit mode, I wrote a 64-bit version of GetHammingWeight and did an average on 12 tests to get:

Code: Select all

xoroshiro128** 32.00005897
xoshiro256**   32.00019341
RomuTrio       31.99971673

The xoroshiro128** is outstanding for a PRNG. The xoshiro256** is OK and RomuTrio is not bad.

[srvaldez]

hello deltarho[1859]
did you know that gcc has builtin popcount? https://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html

Code: Select all

extern "c"
	declare function __builtin_popcount (byval x as ulong) as long
	declare function __builtin_popcountll (byval x as ulongint) as long
end extern

Print __builtin_popcount( &B01101100010011110110101110010011) 
Sleep

[deltarho[1859]]

did you know that gcc has builtin popcount?

No, I didn't. Blimey, and a 64-bit version as well.

Thanks for that.

[D.J.Peters]

@srvaldez thank you for sharing I never saw the built ins page before :-)

Joshy