Range only PRNG discussion

[srvaldez]

I looked at the SFC32_RangedRnd_NoASM function posted at the PowerBasic forum https://forum.powerbasic.com/forum/user ... nt-for-rnd and gave it a try to translate to FB
deltarho[1859] have a look and see what you think

Code: Select all

Function sfc32_rangedrnd_noasm(Byval dwlowerbound As Ulong, Byval dwrange As Ulong, Byref dw_a As Ulong, Byref dw_b As Ulong, Byref dw_c As Ulong, Byref dw_counter As Ulong) As Long
    'sfc32 (small fast counting) prng by chris doty-humphrey, creator of practrand.  (pcg-random.org/posts/bob-jenkins-small-prng-passes-practrand.html (bottom of post)
    '  > pracrand.sourceforge.net > download practrand > practrand-pre0.95 > src > rngs > sfc.)
    'macroenableet

    dw_counter+=1
    Static dw_tmp As Ulong
    dw_tmp = dw_a + dw_b + dw_counter
    Static dwshifted As Ulong
    'dwshifted = dw_b
    dwshifted = dw_b Shr 9
    dw_a = dw_b Xor dwshifted
    dwshifted = dw_c
    dwshifted Shl= 3
    dw_b = dw_c + dwshifted
    dwshifted = dw_c
    Asm
        rol [dwshifted], 21
    End Asm
    dw_c = dwshifted + dw_tmp
    Function = Clng(Csng(dw_c) * (Csng(dwrange - 1) / 4294967296!)) + dwlowerbound

    'macroerrortrap
End Function  'sfc32_rangedrnd_noasm()

#Define numresamplingtrials 20

Sub fbmain ()
    'initialize sfc32.
    Dim As Ulong dw_a, dw_b, dw_c, dw_counter
    dw_a = 0
    dw_counter = 1
    dw_b = &h1115eed0
    dw_c = &h1115eed1                     '\/ == lowerbound, upperbound - lowerbounc + 1
    Dim As Long funcresult
    Do
        sfc32_rangedrnd_noasm(1, 300, dw_a, dw_b, dw_c, dw_counter)
    Loop Until dw_counter = 13  '"warm up" as per original source code.

    'use sfc32 many times...
    Dim As Long trialnum, myprn
    For trialnum = 1 To numresamplingtrials
        myprn = sfc32_rangedrnd_noasm(1, 300, dw_a, dw_b, dw_c, dw_counter)
        Print myprn
    Next trialnum
    Print "press return to exit"
    Sleep
End Sub

fbmain

@deltarho[1859]
I could not see any room for improvement in your excellent code, however I think it would be interesting to have a version with as little asm as possible, not only to compare performance but also to be able to compile to 64-bit

[deltarho[1859]]

You should include some usage code because that is not working as intended. I haven't got time to debug it but your logic with regard dw_counter looks suspicious.

You should never post numerical code without a usage example otherwise most people will not bother to try it.

Something simple like the function in a short loop will do.

Added: I think that you may have forgotten that PB defaults to ByRef whereas FB defaults to ByVal.

[srvaldez]

thank you deltarho[1859]
all valid points, will see if I can correct them
< first post edited/corrected >

[deltarho[1859]]

@srvaldez

I thought I was going to beat you. You had an edge - debug. I was starting from scratch.

We have a different coding style.

Note the #define - who needs stinkin' ASM.

In practice I would populate the state vector with cryptographic numbers.

Code: Select all

#define rotl(x,k) ( (x Shl k) Or (x Shr(32-k)) ) ' Note the extra parentheses

Type SFC32
  dw_a AS Ulong = 123
  dw_b AS Ulong = 456
  dw_c AS Ulong = 789
  dw_counter AS Ulong
End Type
 
Dim Range0 As SFC32
 
Function SFCRangeN ( ByRef RangeN As SFC32,  ByVal First As Long, ByVal Last As long ) As Long
Dim As Ulong dw_tmp
RangeN.dw_counter += 1
dw_tmp = RangeN.dw_a + RangeN.dw_b + RangeN.dw_counter
RangeN.dw_a = RangeN.dw_b Xor ( RangeN.dw_b shr 9 )
RangeN.dw_b = RangeN.dw_c + ( RangeN.dw_c shl 3 )
RangeN.dw_c = rotl(RangeN.dw_c, 21) + dw_tmp
FUNCTION = CLNG(CSNG(RangeN.dw_c) * (CSNG(Last - First) / 4294967296!)) + First
End Function
 
Dim As Ulong i
Dim As UlongInt k
Dim As Double tot, t
 
For i = 1 to 10
  Print SFCRangeN( Range0, 0, 255)
Next
Print
For i = 1 to 10^8
  k += SFCRangeN( Range0, 0, 255)
Next
Print k/10^8 ' Theoretical value = 127.5
Print
For i = 1 to 10^8
  tot += SFCRangeN( Range0, -10, 10)
Next
Print tot/10^8 ' Theoretical value = 0
Print
t = Timer
For i = 1 to 10^8
  k = SFCRangeN( Range0, 0, 255)
Next
t = Timer - t
Print Int(100/t);"MHz"
 
Sleep

Typical output.

Code: Select all

 98
 72
 168
 57
 228
 22
 79
 119
 167
 233
 
 127.5058166
 
-9.629999999999999e-006
 
 384MHz

384MHz. WHAT?

64-bit => ???

Something weird is going on with 64-bit.

[deltarho[1859]]

I changed the return to

Code: Select all

Function = RangeN.dw_c/2^32*( Last - First ) + First

As was is a right dog's dinner.

I'm using 2^32 earlier otherwise we can have a problem with RangeN.dw_c*( Last - First )

gcc will replace /2^32 with a multiplication.

384MHz to 412MHz.

Still cannot see what is going on with 64-bit yet.

It is running a lot slower and then gives a ridiculously high MHz.

gas comes in at 96MHz.

[srvaldez]

I get #Inf MHz in 64-bit :-)

[deltarho[1859]]

Your code is coming in at 245MHz (32 bit) and 251MHz (64 bit).

-O0 25MHz
-O1 34MHz
-O2 35MHz
-O3 ???

I tried a few toolchains.

Either fbc is screwing up or gcc is. Considering I went from gcc 5.2 to gcc 12.0 I'm afraid my money is on fbc screwing up.

I am getting the same output, number crunching-wise, with 32 bit and 64 bit, but the 64 bit is definitely dragging its heels and quite noticeably.

[deltarho[1859]]

With

Code: Select all

For i = 1 to 10^8
  k = SFCRangeN( Range0, 0, 255)
Next

64 bit gcc -O3 is ripping out 'k = SFCRangeN( Range0, 0, 255)' and we end up timing an empty loop; assuming that the loop itself has not been ripped out.

I say it again we need the means to stop optimization of selected portions of code.

[srvaldez]

hi deltarho[1859]
to avoid gcc from eliminating the timing loop

Code: Select all

k=0
t = Timer
For i = 1 to 10^8
  k += SFCRangeN( Range0, 0, 255)
Next
t = Timer - t
Print k,Int(100/t);"MHz"

I know that it's not ideal but the impact of += is not much and at least we get a meaningful result
I get about 270 MHz in 32-bit and about 740 MHz in 64-bit using gcc-12
[edit]
using gcc-9.3SJLJ I get 525 MHz in 32-bit and 725 in 64-bit

[deltarho[1859]]

Hi srvaldez

I am doing just that and mentioned the approach in the 'Range only PRNG' thread.

Interestingly, the bounded integer figures on my machine collapse with 64-bit.

Of course there is another factor in this game and that is CPU architecture and whether I have had breakfast today. I went To McDonalds this morning, and they had no coffee. What the hell is the world coming to?

BTW the 'Range only PRNG' thread has a new SFC32.bi - no asm in sight!