Algorithm 5 provides cryptographic random numbers. For Windows, the CryptoAPI is used via CryptGenRandom. A better quality generator is with 'Cryptography API: Next Generation' introduced in Windows Vista via BCryptGenRandom. Both generators are designed for filling buffers. Algorithm 5 is OK for requesting the odd random number now and again but if we want access to a lot and fast then algorithm 5 is not the way to go.
On my machine Mersenne Twister knocked out a million random numbers in 13.004ms with one test. Algorithm 5 took 2361.078ms with one run. The method employed here uses BCryptGenRandom ( Vista and older remember ) and knocked out a million random numbers in 5.734ms with one test. That is more than twice as fast as Mersenne Twister and we are talking about a CPRNG as opposed to a PRNG.
Anyway, here is the method employed.
We have two equally sized buffers A and B.
'A' is split into two equally sized buffers A0 and A1 and they are filled by two secondary threads of execution. On completion, 'B' is treated the same way and 'A' becomes available for use.
When 'A' is exhausted we switch to 'B', start to fill 'A' and 'B' becomes available for use.
Code: Select all
|_________A________| |_________B_________|
| 0 | 1 | | 0 | 1 |
If 'B', for example, is not filled when 'A' exhausts then we will have to wait and there will be a stutter. The stutter is directly proportional to the size of 'A' or 'B'. We call this stutter the exhaustion stutter. If 'B', for example, is filled when 'A' exhausts then there will be no exhaustion stutter. The original version of this method only used one secondary thread of execution. Using two saw a significant reduction in the exhaustion stutter.
When we switch from one buffer to the other there will be a stutter and this stutter is independent of the size of 'A' or 'B'. We call this stutter the switch stutter.
If we use a sufficiently large buffer and request less then there will no stutter at all. If we then use a smaller buffer and request the same number such that we switch often then subtracting the smaller time from the larger time and divide by the number of switches then we will determine the average combined stutter; that is the exhaustion stutter, if any, and the switch stutter.
That is easy. However, determining either the exhaustion or switch stutter is not. Including analysis code in a neighbourhood of the switch will affect the stutter and we have, effectively, Heisenberg's uncertainty principle applying. <laugh>
I think I will leave that as a reader exercise because I am getting a combined stutter, averaging several tests, of about 50ns. No, you did not misread that - 50 nanoseconds.
An analogy is the fly-back with a cathode ray tube - if it is fast enough we are not conscious of it.
It is worth noting that in the above we are exhausting as fast as possible. In practice, we will be using the random numbers whilst the 'filling' is doing nothing else but so the most likely scenario is the buffer to be used next will be sat there twiddling its thumbs whispering "I am ready when you are, neighbour.".
The following code section is the generator. It is in inc form. I am not up to full speed yet on creating libraries so, be my guest. <smile>
Functions:
CyptoDW - Generates Ulongs.
CryptoS - Single precision [0,1]
CryptoSX - Single precision [-1,1]
CryptoD - Double precision [0,1]
CryptoDX - Double precision [-1,1]
CryotoR - [ Long, Long ]
It is worth noting that Mersenne Twister "provides 32-bit granularity" so it is cast as a double. The 'double' in CryptoD and CryptoDX is a genuine double; it uses two 32 bit random numbers from the generator.
CryptoRndBufferCNG.inc
Code: Select all
#include once "windows.bi"
#include once "win/bcrypt.bi"
#inclib "bcrypt"
Dim Shared As Byte Ptr hRand
Dim Shared As Byte Buffer0(), Buffer1()
Dim Shared As Long BufferSize
Dim Shared As Any Ptr hThread()
Dim Shared As Any Ptr ptrBuffer, ptrBaseBuffer0, ptrBaseBuffer1
Dim Shared As Long SwitchBufferCriteria
Declare Sub SwitchBuffer
Declare Sub FillBuffer( As Any Ptr )
Private Function CryptoDW As ULong
If ptrBuffer >= SwitchBufferCriteria Then
SwitchBuffer
End If
Asm
mov eax, [ptrBuffer]
mov eax, [eax]
mov [Function], eax
End Asm
ptrBuffer += 4
End Function
Private Function CryptoS As Single ' [0,1)
If ptrBuffer >= SwitchBufferCriteria Then
SwitchBuffer
End If
' ASM by Wilbert @ PureBasic forums
Asm
mov eax, [ptrBuffer]
mov eax, [eax]
movd xmm0, eax
psrlq xmm0, 9
mov eax, 1
cvtsi2ss xmm1, eax
por xmm0, xmm1
subss xmm0, xmm1
movd [Function], xmm0
End Asm
ptrBuffer += 4
End Function
Private Function CryptoSX As Single ' [-1,1]
If ptrBuffer >= SwitchBufferCriteria Then
SwitchBuffer
End If
' ASM adapted from CryptoS by author
Asm
mov eax, [ptrBuffer]
mov eax, [eax]
movd xmm0, eax
psrlq xmm0, 9
mov edx, 2
cvtsi2ss xmm1, edx
por xmm0, xmm1
subss xmm0, xmm1
mov edx, 1
cvtsi2ss xmm1, edx
subss xmm0, xmm1
movd [Function], xmm0
End Asm
ptrBuffer += 4
End Function
Private Function CryptoD As Double ' [0,1)
If ptrBuffer >= SwitchBufferCriteria Then
SwitchBuffer
End If
' ASM by Wilbert at PureBasic forums
Asm
mov eax, [ptrBuffer]
movd xmm0, [eax]
movd xmm1, [eax + 4]
punpckldq xmm0, xmm1
psrlq xmm0, 12
mov eax, 1
cvtsi2sd xmm1, eax
por xmm0, xmm1
subsd xmm0, xmm1
movq [Function], xmm0
End Asm
ptrBuffer += 8
End Function
Private Function CryptoDX As Double ' [-1,1]
If ptrBuffer >= SwitchBufferCriteria Then
SwitchBuffer
End If
' ASM adapted from CryptoD by author
Asm
mov eax, [ptrBuffer]
movd xmm0, [eax]
movd xmm1, [eax + 4]
punpckldq xmm0, xmm1
psrlq xmm0, 12
mov eax, 2
cvtsi2sd xmm1, eax
por xmm0, xmm1
subsd xmm0, xmm1
mov eax, 1
cvtsi2sd xmm1, eax
subsd xmm0, xmm1
movq [Function], xmm0
End Asm
ptrBuffer += 8
End Function
Private Function CryptoR( ByVal One As Long, ByVal Two As Long ) As Long
If ptrBuffer >= SwitchBufferCriteria Then
SwitchBuffer
End If
' ASM by John Gleason @ PowerBASIC forums
Asm
mov edx, [ptrBuffer]
mov edx, [edx]
mov ecx, [One]
mov eax, [Two]
cmp ecx, eax
jl Now1LT2
xchg eax, ecx
Now1LT2:
Sub eax, ecx
inc eax
jz doTheRnd
mul edx
Add edx, ecx
doTheRnd:
mov [Function], edx
End Asm
ptrBuffer += 4
End Function
Private Sub InitializeCryptoBuffers( ByVal Buffer As Long )
BCryptOpenAlgorithmProvider( varptr(hRand), BCRYPT_RNG_ALGORITHM, 0, 0)
ReDim As Any Ptr hThread(0 To 1)
If Buffer < 1024 Then
BufferSize = 1024
Else
BufferSize = Buffer - Buffer Mod 8
End If
ReDim Buffer0( 1 To BufferSize) As Byte
ptrBaseBuffer0 = VarPtr( Buffer0(0) )
ptrBuffer = ptrBaseBuffer0
SwitchBufferCriteria = Cast(Long, ptrBuffer) + BufferSize
hThread(0) = ThreadCreate( @FillBuffer, ptrBaseBuffer0 )
hThread(1) = ThreadCreate( @FillBuffer, ptrBaseBuffer0 + BufferSize\2 )
ThreadWait( hThread(0) )
ThreadWait( hThread(1) )
ReDim Buffer1( 1 To BufferSize) As Byte
ptrBaseBuffer1 = VarPtr( Buffer1(0) )
hThread(0) = ThreadCreate( @FillBuffer, ptrBaseBuffer1 )
hThread(1) = ThreadCreate( @FillBuffer, ptrBaseBuffer1 + BufferSize\2 )
End Sub
Private Sub CleanUpCryptoRndBufferCNG
BCryptCloseAlgorithmProvider( hRand, 0 )
End Sub
Private Sub FillBuffer( ByVal BaseBuffer As Any Ptr )
BCryptGenRandom( hRand, BaseBuffer, BufferSize\2, 0)
End Sub
Private Sub SwitchBuffer
ThreadWait( hThread(0) )
ThreadWait( hThread(1) )
Swap ptrBaseBuffer0, ptrBaseBuffer1
ptrBuffer = ptrBaseBuffer0
SwitchBufferCriteria = Cast(Long, ptrBuffer) + BufferSize
hThread(0) = ThreadCreate( @FillBuffer, ptrBaseBuffer1 )
hThread(1) = ThreadCreate( @FillBuffer, ptrBaseBuffer1 + BufferSize\2 )
End Sub
The first one simply takes a black screen and zaps it with random white pixels, pausing to show the progression to a white screen. If you can see any black pixels on completion then take you monitor back, you paid good money for it. <laugh>. Actually, there probably are a few black pixels - we are talking random numbers here so some pixels may escape attention.
Plot ( Compile as GUI )
Code: Select all
' Compile as GUI
#Include Once "CryptoRndBufferCNG.inc"
Dim as Long i, j
ScreenRes 640, 640, 8
InitializeCryptoBuffers( 128*1024 )
Randomize
Sleep (1000,1)
j = 1
For i = 1 to 10*640*640
PSet (CryptoR(11,631), CryptoR(11,631)), 15
'PSet (11 + Rnd*621, 11 + Rnd*621), 15 ' Mersenne Twister
If i Mod 640*640 = 0 Then
Locate 1,1
Print j
j += 1
Sleep (750,1)
End If
Next
Locate 1,1
Print "Done"
Sleep
The next test uses Fourmilab's ent.exe. The code dumps 25MB of CryptoDW giving a file of 100MB random Ulongs.
Dump ( Compile as Console )
Code: Select all
' Compile as Console
#Include Once "CryptoRndBufferCNG.inc"
#Include "file.bi"
Dim as long i
InitializeCryptoBuffers( 128*1024 )
If FileExists( "100MB.txt" ) Then Kill "100MB.txt"
Open "100MB.txt" For Binary as #1
For i = 1 to 25*1024*1024
Put #1, , CryptoDW
Next
Close #1
Shell( "ent.exe 100MB.txt")
Sleep
------------------------------------------------------------------------
Entropy = 7.999998 bits per byte.
Optimum compression would reduce the size
of this 104857600 byte file by 0 percent.
Chi square distribution for 104857600 samples is 255.54, and randomly
would exceed this value 47.88 percent of the times.
Arithmetic mean value of data bytes is 127.5064 (127.5 = random).
Monte Carlo value for Pi is 3.141566969 (error 0.00 percent).
Serial correlation coefficient is 0.000028 (totally uncorrelated = 0.0).
------------------------------------------------------------------------
No grounds for concern there.
Finally, code to test how long it takes to fill a chosen buffer, how long it takes to 'crunch' a requested number and an estimate of the rate of generation.
TestCrypto ( Compile as Console )
Code: Select all
' Compile as Console
#Include Once "MacroTimersQPC.inc"
#Include Once "CryptoRndBufferCNG.inc"
Dim as Long lBufferSize, lNumBuffers, lRequestNumber, i
Dim As Double Tot
Dim As Single Dummy
lBufferSize = 512*1024
lNumBuffers = 20
lRequestNumber = lBufferSize*lNumBuffers\4 ' 4 For Single precision and Range, 8 for double precision
Print "Requested " + str(lRequestNumber)
If lBufferSize < 1024 Then
lBufferSize = 1024
Else
lBufferSize = lBufferSize - lBufferSize Mod 8
End If
Print "BufferSize";lBufferSize
StartTimer(0)
InitializeCryptoBuffers( lBuffersize )
StopTimer(0)
Print sTimeTaken(0,3,0) + " Time to fill"
StartTimer(0)
For i = 1 to lRequestNumber
CryptoS
Next
StopTimer(0)
Dummy = Val(sTimeTaken(0,3,0))
Print str(Dummy) + "ms Time to crunch"
Print str(Int(lRequestNumber/(1000*Dummy))) + " Million per second"
CleanUpCryptoRndBufferCNG
Sleep
Here is the output of using a buffer of 512KB and a request of 20 buffers giving 2,621,440 random single precision numbers.
-----------------------
Requested 2621440
BufferSize 524288
.684ms Time to fill
10.265ms Time to crunch
255 Million per second
-----------------------
What bothers me is the rate of generation at 255 million per second.
I did not expect that. That is three times faster than Mersenne Twister.
A challenge: Break it!
Have fun.
David Roberts
PS Just for the record I am using Windows 10 Pro, Intel i7-3770K CPU @ 3.50GHz, 3.90GHz with turbo.