Random numbers

General discussion for topics related to the FreeBASIC project or its community.
deltarho[1859]
Posts: 4292
Joined: Jan 02, 2017 0:34
Location: UK
Contact:

Random numbers

Post by deltarho[1859] »

NIST’s New Quantum Method Generates Really Random Numbers

I am now waiting for a device to push into one of my USB ports. <smile>
TeeEmCee
Posts: 375
Joined: Jul 22, 2006 0:54
Location: Auckland

Re: Random numbers

Post by TeeEmCee »

Quantum random number generator hardware for PCs/servers, as USB or PCI/PCIE plugins, have been commerically available for a long time, eg the Quantis first released in 2001. See https://en.wikipedia.org/wiki/Compariso ... generators. I have some interest in this because it's a main research area of my former supervisor, who has done empirical testing of quantum random generators. They often produce lower quality results than PRNGs because exactly removing all hardware biases is a challenging open research problem.
deltarho[1859]
Posts: 4292
Joined: Jan 02, 2017 0:34
Location: UK
Contact:

Re: Random numbers

Post by deltarho[1859] »

TeeEmCee wrote:Quantum random number generator hardware for PCs/servers, as USB or PCI/PCIE plugins, have been commerically available for a long time
I know, but not like NIST's new toy. Since you have an interest then you will see, by reading my link, this new approach is a little different to previous QRNGs.
TeeEmCee
Posts: 375
Joined: Jul 22, 2006 0:54
Location: Auckland

Re: Random numbers

Post by TeeEmCee »

Yes, it provides theoretical guarantees that existing hardware don't have, and it's quite interesting.
Even it doesn't provide a perfectly uniform output (IIRC, creating a randomness extracter which is perfectly uniform is impossible). In practice I believe that and all other problems are trivially solved by mixing in the output of a uniform PRNG. Work on QRNGs generally seem to be far divorced from requirements of practical applications!
deltarho[1859]
Posts: 4292
Joined: Jan 02, 2017 0:34
Location: UK
Contact:

Re: Random numbers

Post by deltarho[1859] »

I use Microsoft's BCryptGenRandom quite a lot but have, where speed is not an issue in the slightest, checked to see if Intel's RdRand is onboard and, if so, used BCryptGenRandom XOR RdRand.
dafhi
Posts: 1641
Joined: Jun 04, 2005 9:51

Re: Random numbers

Post by dafhi »

@deltarho - do u have a PCG i could tinker with?

i'm a c noob - this isn't working

Code: Select all

'' https://en.wikipedia.org/wiki/Permuted_congruential_generator

dim shared as ulongint     state      = &h4d595df4d0f33173		' Or something seed-dependent

'static uint64_t const multiplier = 6364136223846793005
'static uint64_t const increment  = 1442695040888963407	' Or an arbitrary odd constant
dim shared as ulongint multiplier = 6364136223846793005
dim shared as ulongint increment  = 1442695040888963407	' Or an arbitrary odd constant

function rotr32(x as ulong, r as double) as ulong
'static function rotr32(uint32_t x, unsigned r) as ulong
	return (x shr r) or (x shl (-r and 31))
end function

function pcg32() as ulong

	dim as ulongint x = state
	dim as ulongint count = (x shr 59)';		// 59 = 64 - 5

	state = x * multiplier + increment
	x ^= x shr 18';								// 18 = (64 - 27)/2
	return rotr32(cuint(x shr 27), count)';	// 27 = 32 - 5
end function

sub pcg32_init(seed as ulongint)
	state = seed + increment
	'(void)pcg_xsh_rr();
  pcg32
end sub

pcg32_init 1
? pcg32
deltarho[1859]
Posts: 4292
Joined: Jan 02, 2017 0:34
Location: UK
Contact:

Re: Random numbers

Post by deltarho[1859] »

I could give you a link to my PCG32II but I'm not sure if that is exactly what I am using now. The reason for the 'II' is a change to PCG32 to implement a vast improvement by a suggestion from St_W.

Here is what I am using now. I don't even qualify to be a c noob so don't ask any C questions. <smile>

Although we are using 32 bit internally randse returns Double so that all 32 bits are exposed. 'se' stands for single extended.

I am using Private so that if the following is included as a bas then any functions not used will not get 'brought in' and compiled.

Code: Select all

' Generator PCG32II
' *Really* minimal PCG32 code / (c) 2014 M.E. O'Neill / pcg-random.org
' Licensed under Apache License 2.0 (NO WARRANTY, etc. see website)
' pcg32.rand is an adaptation of a FreeBASIC translation by Matthew Fearnley
' (aka FreeBASIC's counting_pine) 2017-06-04
' Object duplication method by FreeBASIC's St_W

Type pcg32
  Public:
  declare Constructor
  Declare Sub MyRandomize( seed As Ulongint = 0, seq As Ulongint = 0 )
  Declare Function rand() As Ulong
	Declare Function randse() As Double
  Declare Function range( Byval One As Long, Byval Two As Long ) As Long
	Declare Function GetSeed() As Ulongint
	Declare Function GetSeq() As Ulongint
  declare Function Gauss() as double
  state As Ulongint
  seq   As Ulongint
	seed  As Ulongint
End Type

Private Function Get64Bit() As UlongInt
return (Cast( Ulongint, Rnd*(2^32) ) Shl 32) Or Cast( Ulongint, Rnd*(2^32) )
End Function

Private Function pcg32.rand() As Ulong
  Dim As Ulongint oldstate = this.state
  this.state = oldstate * 6364136223846793005ULL + (this.seq Or 1)
  Dim As Ulong xorshifted = ((oldstate Shr 18u) xor oldstate) Shr 27u
  Dim As Ulong rot = oldstate Shr 59u
  Return (xorshifted Shr rot) Or (xorshifted Shl ((-rot) And 31))
End Function

Private Sub pcg32.MyRandomize( seed As Ulongint = 0, seq As Ulongint = 0 )
  Dim i As Integer
  
  Randomize , 5
  If seed = 0 Then
    If seq = 0 Then
      this.state = Get64Bit
      this.seq = Get64Bit
    Else
      this.state = Get64Bit
      this.seq = seq
    End If
  Else
    If seq = 0 Then
      this.state = seed
      this.seq = Get64Bit
    Else
      this.state = seed
      this.seq = seq
    End If
  End If
  This.Seed = This.state ' Save initial state
  ' Warm up generator - essential
  For i As Integer = 1 To 200
    this.rand()
  Next i
End Sub

Private Function pcg32.randse() As Double
  Dim TempVar As Ulong
  Dim As Ulongint oldstate = this.state
  this.state = oldstate * 6364136223846793005ULL + (this.seq Or 1)
  Dim As Ulong xorshifted = ((oldstate Shr 18u) xor oldstate) Shr 27u
  Dim As Ulong rot = oldstate Shr 59u
  TempVar =  (xorshifted Shr rot) Or (xorshifted Shl ((-rot) And 31))
 	Return TempVar/4294967296.0
End Function

Private Function pcg32.range( Byval One As Long, Byval Two As Long ) As Long
  Dim TempVar As Ulong
  Dim As Ulongint oldstate = this.state
  ' Advance internal state
  this.state = oldstate * 6364136223846793005ULL + (this.seq Or 1)
  ' rotate32((state ^ (state >> 18)) >> 27, state >> 59)
  Dim As Ulong xorshifted = ((oldstate Shr 18u) xor oldstate) Shr 27u
  Dim As Ulong rot = oldstate Shr 59u
  Tempvar =  (xorshifted Shr rot) Or (xorshifted Shl ((-rot) And 31))
	Asm
		mov edx, dword Ptr [TempVar]
    mov ecx, [One]
    mov eax, [Two]
    cmp ecx, eax
    jl 0f
    xchg eax, ecx
    0:
    Sub eax, ecx
    inc eax
    jz 1f
    mul edx
    Add edx, ecx
    1:
    mov [Function], edx
  End Asm
End Function

Private Function pcg32.GetSeed() As Ulongint
	Return This.Seed
End Function

Private Function pcg32.GetSeq() As Ulongint
	Return This.Seq
End Function

constructor pcg32
  This.MyRandomize
end constructor

Private Function pcg32.Gauss As double
Static As Long u2_cached
Static As double u1, u2, x1, x2, w
 
  If u2_cached = -1 Then
    u2_cached = 0
    Function = u2
  Else
    Do
      x1 = This.randse
      x2 = This.randse
      w = x1 * x1 + x2 * x2
    Loop While w >= 1
    w = Sqr( -2 * Log(w)/w )
    u1 = x1 * w
    u2 = x2 * w
    u2_cached = -1
    Function = u1
  End If
 
End Function
dafhi
Posts: 1641
Joined: Jun 04, 2005 9:51

Re: Random numbers

Post by dafhi »

Seeing 'gauss' I'm reminded of a distribution function post of yours along with a comment about what graphics peeps might do with it. I think paul doe and dodicat may have replied. Anyway, I'm working on a few different projects. Thanks for the code!
deltarho[1859]
Posts: 4292
Joined: Jan 02, 2017 0:34
Location: UK
Contact:

Re: Random numbers

Post by deltarho[1859] »

dafhi wrote:Thanks for the code!
My pleasure.

At one time I thought Sebastian Vigna's xorshift* and xoroshiro would be the last word but as you may know they go belly up at 64GB with Practrand. PCG32, on the other hand, sails through to 1TB with a few small murmurs. The murmurs got would also occur with quantum random numbers. I take the view that "If it ain't got no murmurs it ain't random". <smile>

With gcc 8.1.0 and FB1.06 in 64 bit mode PCG32II is knocking out numbers at 974MHz which is about 11 times faster than FB's Mersenne Twister. I'd love to squeeze another 26MB out of it. Perhaps I will with my next PC but the one that I have is not ready for the knackers yard just yet.
dafhi
Posts: 1641
Joined: Jun 04, 2005 9:51

Re: Random numbers

Post by dafhi »

deltarho[1859] wrote:xorshift* and xoroshiro would be the last word but as you may know they go belly up at 64GB with Practrand. PCG32, on the other hand, sails through to 1TB with a few small murmurs. The murmurs got would also occur with quantum random numbers. I take the view that "If it ain't got no murmurs it ain't random". <smile>
Actually, I wouldn't know. I am far less academic than most. Who doesn't love RNGs though?
Not quite sure what murmurs refers to, but what I gather is that PCG is the bomb
deltarho[1859]
Posts: 4292
Joined: Jan 02, 2017 0:34
Location: UK
Contact:

Re: Random numbers

Post by deltarho[1859] »

dafhi wrote:Who doesn't love RNGs though?
Most people I reckon. It is too close to cryptography and as soon as cryptography is mentioned the vast majority of people start nodding off. I don't blame them - to enjoy that subject it is imperative that folk have more than a few loose screws. I sometimes think that I have more loose screws than tight ones. I am not alone in thinking that. <laugh>
dafhi
Posts: 1641
Joined: Jun 04, 2005 9:51

Re: Random numbers

Post by dafhi »

The only reason I'm not into crypto is I associate it with the bogus notion of security. Also, I develop a blank stare rather quickly when lines of code start piling up. Ironic ..
deltarho[1859]
Posts: 4292
Joined: Jan 02, 2017 0:34
Location: UK
Contact:

Re: Random numbers

Post by deltarho[1859] »

dafhi wrote:Ironic ..
It seems to me that an element of human physiology is that we tend to be drawn to that which we are allergic to. Someone with a sugar intolerance is likely to have a sweet tooth. Programmers get a lot of grief from programming and yet we keep coming back for more.

However, at the very top of the list is that most men are allergic to women. By the same token most women are allergic to men. Now why this is part of the grand design is beyond me. God: Blast it, I didn't mean to do that. Oh, what the hell - I have done it now. Should be interesting though. <smile>
dafhi
Posts: 1641
Joined: Jun 04, 2005 9:51

Re: Random numbers

Post by dafhi »

super fun read! haha .. yeah programming always reels me back. Sometimes I'll hit a bug and be like .. ah you know how it goes.
waves of time wash over .. heh, you've got me in a contemplative mood
deltarho[1859]
Posts: 4292
Joined: Jan 02, 2017 0:34
Location: UK
Contact:

Re: Random numbers

Post by deltarho[1859] »

dafhi wrote:heh, you've got me in a contemplative mood
I am permanently in one and I have noticed that in may be catching. <laugh>
Post Reply