Fast random integers

[Provoni]

Original method by me. Try this when you need a very fast random integer generator. Quite customizable too.

Updated

Code: Select all

'Provoni's FRI (Fast Random Integers) 10172018
'---------------------------------------------
'- Fast and unpredictable random integer generator
'- Preferably without the overhead of the function call

screenres 640,480,32

dim as longint i
dim shared as longint frii
dim shared as longint state=1
dim shared as longint maxrl=1000000
dim shared as longint maxro=100 'random integers from 0 to 99
dim shared as byte rl(maxrl)
dim shared as byte ro(maxro)

declare sub init_fri()
declare function fri()as byte

init_fri() 'initialize

for i=1 to 100 'print 100 fri's
	print fri();
next i

beep
sleep

sub init_fri()
	dim as longint i,a,b
	for i=0 to maxro-1
		ro(i)=i
	next i
	for i=1 to maxro
		state=(22695477*state+1)and 2147483647
		a=int(state/2147483648*maxro)
		state=(22695477*state+1)and 2147483647
		b=int(state/2147483648*maxro)
		swap ro(a),ro(b)
	next i
	for i=1 to maxrl
		state=(22695477*state+1)and 2147483647
		rl(i)=int(state/2147483648*maxro)
	next i
end sub

function fri()as byte
	frii+=1
	if frii>maxrl then
		frii=1
		dim as longint i,a,b
		for i=1 to maxro
			state=(22695477*state+1)and 2147483647
			a=int(state/2147483648*maxro)
			state=(22695477*state+1)and 2147483647
			b=int(state/2147483648*maxro)
			swap ro(a),ro(b)
		next i
	end if
	return ro(rl(frii))
end function

[nimdays]

Thanks for sharing

[Provoni]

Suppose that you have a stream of random numbers (0,1,1,1,0,1,0,0,..). If the numbers are really random then the next number in the stream can be predicted with no more or less than 50% accuracy on average.

So with that idea in mind I wrote a really fancy predictor that learns over time on a stream of integers between 0 and 19 and tested FreeBASIC's random number generators as well as some others. The results still have me startled as none of the generators passed the test. Even more remarkable is that my own generator is most unpredictable. FB random option 4 which is the original QBasic 24-bit LCG was getting close to being 98% predictable!

Here is a ranking where closer to zero is better.

Code: Select all

Fast Random Ints:   -2302960 (FRI)
Ivy Bridge RdRand:  -15537013 (Hardware DRNG)
FB random option 3: -15541526 (Mersenne Twister)
FB random option 5: -15595331 (Cryptographically random numbers)
FB random option 2:  150116705 (Fast implementation)
FB random option 1:  182426832 (C runtime library's rand())
FB random option 4:  9171340342 (Qbasic)

[dodicat]

Suppose you select a random number from the range 0 to 10
Do this 20000000 and keep the counts in an array(0 to 10)
array(0), array(1) ... should all be the same.
Of course they are not in practice.
Here are some observations about the array() from randomize 1 to randomize 4 (randomize 5 is too slow)
Also from fri() , set at 11 (which I hope is correct for [0,10]
The standard deviations should be small, the chi squared distance should be small and the range within a() should be small.
Again randomize ,4 seems the best.

Code: Select all

Type range
    As Double _max,_min,sd
    As Long _maxi,_mini
End Type

 function mean(a() as double,R as range) as double
    R=type(-1e10,1e10,0,0,0)
    dim as long lb=lbound(a),ub=ubound(a)
    dim as double acc,m
    for n as long=lb to ub
        acc+=a(n)
        if R._max<a(n) then R._max=a(n):R._maxi=n
        if R._min>a(n) then R._min=a(n):R._mini=n
    next
    m=acc/(ub-lb+1)
    acc=0
    for n as long=lb to ub
        acc+=(a(n)-m)*(a(n)-m)
    next
    R.sd =sqr(acc/(ub-lb))
    return m
end function

function chisquared(a() as double,R as range,byref m as double) as double
     m=mean(a(),R)
    dim as double acc
    for n as long=lbound(a) to ubound(a)
        acc+=(a(n)-m)^2/m
    next
    return acc
end function
   '=================   provoni ============
dim as longint i
dim shared as longint frii
dim shared as longint state=1
dim shared as longint maxrl=100000
dim shared as longint maxro=11 'random integers from 0 to 10
dim shared as byte rl(maxrl)
dim shared as byte ro(maxro)


'=========  FRI ==========
declare sub init_fri()
declare function fri()as byte

init_fri() 'initialize



sub init_fri()
   dim as longint i,a,b
   for i=0 to maxro-1
      ro(i)=i
   next i
   for i=1 to maxro
      state=(22695477*state+1)and 2147483647
      a=int(state/2147483648*maxro)
      state=(22695477*state+1)and 2147483647
      b=int(state/2147483648*maxro)
      swap ro(a),ro(b)
   next i
   for i=1 to maxrl
      state=(22695477*state+1)and 2147483647
      rl(i)=int(state/2147483648*maxro)
   next i
end sub

function fri()as byte
   frii+=1
   if frii>maxrl then
      frii=1
      dim as longint i,a,b
      for i=1 to maxro
         state=(22695477*state+1)and 2147483647
         a=int(state/2147483648*maxro)
         state=(22695477*state+1)and 2147483647
         b=int(state/2147483648*maxro)
         swap ro(a),ro(b)
      next i
   end if
   return ro(rl(frii))
end function
'===============  end provoni ==========

#define Intrange(f,l,fn) Int(fn*((l+1)-(f))+(f))

#macro looper(funct)
t1=Timer
For n As Ulong=1 To limit
    Dim As Ulong u= IntRange(0,10,funct)
    a(u)+=1
Next
t2=Timer
#endmacro

#macro flooper(funct)
t1=Timer
For n As Ulong=1 To limit
    Dim As Ulong u= funct
    a(u)+=1
Next
t2=Timer
#endmacro


Dim As Ulong limit=20000000

Dim As Double t1,t2
Dim As String msg

For z As Long=1 To 5
    Dim As Double a(0 to 10)
    Select Case z
    Case 1:Randomize 1,1
    looper(Rnd)
    msg="randomize 1,1"
Case 2:Randomize 1,2
    looper(Rnd)
    msg="randomize 1,2"
Case 3:Randomize 1,3
    looper(Rnd)
    msg="randomize 1,3"
Case 4:Randomize 1,4
    looper(Rnd)
    msg="randomize 1,4"
 Case 5:
   flooper((fri))
   msg="randomize by fri"
End Select

For n As Ulong=0 to 10
    Print a(n)
Next
Print
Print
Print "time "; t2-t1; "  for algorithm "+msg
Print
Dim As range R
dim as double m
var c=chisquared(a(),R,m)
Print "S. deviation and chisquared length ";R.sd,c
Print "Range min and max         ";R._min,R._max;"    difference  ";R._max-R._min
Print "_________________________________"
Next z
Sleep

Sleep 

[Provoni]

Suppose you select a random number from the range 0 to 10
Do this 20000000 and keep the counts in an array(0 to 10)
array(0), array(1) ... should all be the same.
Of course they are not in practice.
Here are some observations about the array() from randomize 1 to randomize 4 (randomize 5 is too slow)
Also from fri() , set at 11 (which I hope is correct for [0,10]
The standard deviations should be small, the chi squared distance should be small and the range within a() should be small.
Again randomize ,4 seems the best.

Flawed test since then a sequential non-random stream of numbers such as (0,1,2,3,4,5,6,7,8,9,10,0,1,2,3,4,5,6,7,8,9,10,0,1,2,3,4,5,6,7,8,9,10,...) would be the best. Fri() at 11 is correct. Randomize 4 is the worst since its short period just repeats the same things over and over again and therefore fills all buckets evenly more or less as its output is highly sequential. The test I ran in my previous post can predict the output of randomize 4 with up to 99% accuracy.

[deltarho[1859]]

Original method by me.

Not quite - see Parameters in common use - second entry. However, your implementation is, admittedly, a variation.

The original description of the opening post's generator was "'- Fast low quality random integer generator". It was subject to what has been described as "a really fancy predictor" the results of which has elevated the description to "'- Fast and unpredictable random integer generator". That is quite an elevation for a single algorithm test. The code for "a really fancy predictor" should have been published.

It will take more than "a really fancy predictor" to do that. 'Unpredictable' is normally reserved for cryptographically secure pseudorandom number generators (CSPRNG)

With regard to "a really fancy predictor" it may be worthwhile to read up on Autocorrelation. Autocorrelation (Serial correlation) is used by John Walker's ENT and is the only aspect of the tests which are related to randomness - all the others are related to uniformiity.

It should be noted that all the metrics used in dodicat's code examine uniformity and not randomness. The difference is looked at in the thread PRNGs randomness versus uniformity.

As Provoni noted FB #4 has a comparatively short period, 2^24 = 16777216, so to keep a level playing field we should choose a 'limit' of 16777216 as opposed to 20000000. If we then consider a range of 0 to 15 as opposed to a range of 0 to 10 we see FB #4 producing perfect uniformity ie a(i) = 1048576 for i = 0 to 15. This gives a standard deviation and chi-square of zero.

Again randomize ,4 seems the best.

We cannot better perfection. <smile> However, that is from a uniformity perspective. From a randomness perspective, FB #4 is poor compared with the other generators considered.

I was interested in what one of my generators would do in dodicat's code so I chose PCG32II. Sometimes it's uniformity was second only to FRI and FB #4 and sometimes it was the worst in the bunch. The reason for this is that PCG32II has a very high level of randomness. As the number of tests increases so would it's uniformity. In fact, 'true' random numbers would tend to perfect uniformity as the number of tests tends to infinity. The contrary is not true. A high level of uniformity does not imply randomness as Provoni's (0,1,2,3,4,5,6,7,8,9,10,0,1,2,3,4,.....) points out. PCG32II was the second fastest after FRI. PCG32II's predictability, according to its author, is 'challenging' but Melissa O'Neill points out that PCG32II is not a CSPRNG. CryptoR(0,15), from CryptoRndII, was faster than FRI in both 32-bit and 64-bit tests. CryptoRndII uses a CSPRNG which would normally suggest unpredictability but my implementation kills that relegating it to a fast PRNG.

So, FRI is a good stab at being a PRNG but there are faster generators and some of them give good quality randomness as well.

[deltarho[1859]]

Just to show you what an extraordinary generator FB #4 is try this code.

Code: Select all

Screen 20, 16
Color Rgb(0, 0, 255), Rgb(255, 255, 0)
Cls
Sleep
Randomize , 3
For i As Ulong = 1 To 8*1024*768
  Pset (Int(Rnd*1024), Int(Rnd*768))
Next
Sleep

As is the code uses the Mersenne Twister.

At the yellow screen hit any key. We then have quite a few yellow pixels left.

Now change to 'Randomize , 4' and repeat.

You may see one yellow pixel left but the chances are you will see none.

This is not indicative of randomness but is indicative of uniformity.

[Provoni]

My method:

Say the program needs random integers between 0 and 25.

1. Pre-generate a large array (array 1) of random integers between 0 and 25.
2. Pre-generate another array (array 2) with 26 elements that has the integers from 0 to 25 placed randomly.
3. To get a random integer increment the position counter of array 1 and access array 1 through array 2 such as: random integer = array 2(array 1(counter)). When the position counter of array 1 is at the end of the array randomize the positions of the elements of the much smaller array 2.

- This method needs an existing random generator to work.
- Array 2 needs a sufficient amount of elements for the method to work well.
- Is fast since a random integer is only: random integer = array 2(array 1(counter)).

--------------------------------------------------------------

Thank you for all the information deltarho[1859].

I just assumed that my generator was low quality. Perhaps it still is in some ways, it should be, it is too much of a free meal. I need more time with my code.

[deltarho[1859]]

Yep, buffering can really make things shift.

My CryptoRndII uses buffering but in a slightly different way to your idea. Have a look at the opening thread of A fast CPRNG. In 32-bit mode, it is knocking out Doubles ( with a granularity of 32 bits ) at a rate in excess of 525MHz. It uses Windows BCryptGenRandom, the 'posh' version of CryptGenRandom which FB #5 uses and we know how pedestrian FB #5 is.

Actually, the original version uses ThreadCreate which is expensive. CryptoRndII uses Thread Pooling. So, I moved up from diesel to aviation fuel. <smile>

I need more time with my code.

There was a time when I reckoned that I was in the starting block to write a generator. However, the more 'papers' that I read the more I realized that I was not at the starting block but in the stands looking down. That was a few years ago. I now know that I am not even in the stadium. I shouldn't have read the papers but I enjoyed reading them. We cannot win sometimes. I have 'dabbled' more with home-brewed encryption and that is great fun but AES has nothing to worry about. <laugh> I may go back to that because FreeBASIC has some very powerful keywords that PowerBASIC, whence I came, does not have.

[Provoni]

Trying to use CryptoRndll but it throws 2 errors while compiling:

Code: Select all

CryptoRndBufferCNG.inc(171) error 20: Type mismatch, before ')' in 'SwitchBufferCriteria = Cast(Long, ptrBuffer) + BufferSize'
CryptoRndBufferCNG.inc(196) error 20: Type mismatch, before ')' in 'SwitchBufferCriteria = Cast(Long, ptrBuffer) + BufferSize'

Yes, it is quite daunting to delve into random numbers. I'm not much of a paper reader and just try to figure stuff out by myself.

[Provoni]

Suppose that you have a stream of random numbers (0,1,1,1,0,1,0,0,..). If the numbers are really random then the next number in the stream can be predicted with no more or less than 50% accuracy on average.

So with that idea in mind I wrote a really fancy predictor that learns over time on a stream of integers between 0 and 19 and tested FreeBASIC's random number generators as well as some others. The results still have me startled as none of the generators passed the test. Even more remarkable is that my own generator is most unpredictable. FB random option 4 which is the original QBasic 24-bit LCG was getting close to being 98% predictable!

Here is a ranking where closer to zero is better.

Code: Select all

Fast Random Ints:   -2302960 (FRI)
Ivy Bridge RdRand:  -15537013 (Hardware DRNG)
FB random option 3: -15541526 (Mersenne Twister)
FB random option 5: -15595331 (Cryptographically random numbers)
FB random option 2:  150116705 (Fast implementation)
FB random option 1:  182426832 (C runtime library's rand())
FB random option 4:  9171340342 (Qbasic)

There was an error in my code and with a rerun the FRI, RdRand, Mersenne Twister and Cryptographically random numbers have passed the test.

[deltarho[1859]]

Trying to use CryptoRndll but it throws 2 errors while compiling:

I had not been with FreeBASIC long, one month, and not into 64-bit. This works.

Code: Select all

#ifdef __FB_64BIT__
  SwitchBufferCriteria = Cast(Longint, ptrBuffer) + BufferSize
#Else
  SwitchBufferCriteria = Cast(Long, ptrBuffer) + BufferSize
#endif

However, I notice that you are using CryptoRndBufferCNG.inc. That was the original version using ThreadCreate. CryptoRNDII uses Thread Pooling. It is a long thread and I made changes for the reader to implement. I don't write posts like that anymore - folks need to get at the full code without wading through pages of stuff. I have just added the latest version to the end of the thread.

Go here for the latest version. It may be worthwhile to go back to it to see if it can be improved upon.

With "#define algo 2 ' For Intel RdRand" I am getting, for CryptoS, 61MHz for 32-bit and 113MHz for 64-bit.

[MrSwiss]

Above is one of the exceptions, where data-type 'integer' fits the bill:

Code: Select all

' here: the correct use of type 'integer': 4 byte (FBC32), 8 byte (FBC64)
SwitchBufferCriteria = Cast(Integer, ptrBuffer) + BufferSize

' can be written shorter ... using CInt(), instead of Cast()
SwitchBufferCriteria = CInt(ptrBuffer) + BufferSize

No need, to use pre-processor code ...

[deltarho[1859]]

Above is one of the exceptions, where data-type 'integer' fits the bill:

Yes, it is ideal.

CryptoRndBufferCNG.inc is 32-bit only. The above is a Copy/Paste from CryptoRNDII.bas which is 32-bit or 64-bit. I did spot that we could use 'integer' and that prompted me to write "It may be worthwhile to go back to it to see if it can be improved upon.".

I may do that as it would be an interesting exercise in of itself but then there is always the argument "If it ain't broke don't fix it" especially since there is a fair amount of pre-processor code when 'algo 2' is used where we use Intel RdRand 32-bit ( mov eax ) or Intel RdRand 64-bit ( mov rax ).

[Provoni]

Thank you deltarho[1857], it works now.

I would also like to test PCG32II but have no clue how to use it. Could you give a small example please? And possibly also a small example of how you determine the Mhz of a RNG?