Random numbers

For other topics related to the FreeBASIC project or its community.
deltarho[1859]
Posts: 2003
Joined: Jan 02, 2017 0:34
Location: UK

Random numbers

Postby deltarho[1859] » Apr 14, 2018 10:15

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: 261
Joined: Jul 22, 2006 0:54
Location: Auckland

Re: Random numbers

Postby TeeEmCee » Apr 15, 2018 7:36

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/Comparison_of_hardware_random_number_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: 2003
Joined: Jan 02, 2017 0:34
Location: UK

Re: Random numbers

Postby deltarho[1859] » Apr 15, 2018 7:57

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: 261
Joined: Jul 22, 2006 0:54
Location: Auckland

Re: Random numbers

Postby TeeEmCee » Apr 15, 2018 8:22

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: 2003
Joined: Jan 02, 2017 0:34
Location: UK

Re: Random numbers

Postby deltarho[1859] » Apr 15, 2018 8:55

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: 1251
Joined: Jun 04, 2005 9:51

Re: Random numbers

Postby dafhi » Jun 05, 2018 2:02

@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: 2003
Joined: Jan 02, 2017 0:34
Location: UK

Re: Random numbers

Postby deltarho[1859] » Jun 05, 2018 2:37

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: 1251
Joined: Jun 04, 2005 9:51

Re: Random numbers

Postby dafhi » Jun 05, 2018 3:51

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: 2003
Joined: Jan 02, 2017 0:34
Location: UK

Re: Random numbers

Postby deltarho[1859] » Jun 05, 2018 4:20

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: 1251
Joined: Jun 04, 2005 9:51

Re: Random numbers

Postby dafhi » Jun 05, 2018 4:28

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: 2003
Joined: Jan 02, 2017 0:34
Location: UK

Re: Random numbers

Postby deltarho[1859] » Jun 05, 2018 4:51

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: 1251
Joined: Jun 04, 2005 9:51

Re: Random numbers

Postby dafhi » Jun 05, 2018 5:54

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: 2003
Joined: Jan 02, 2017 0:34
Location: UK

Re: Random numbers

Postby deltarho[1859] » Jun 05, 2018 6:55

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: 1251
Joined: Jun 04, 2005 9:51

Re: Random numbers

Postby dafhi » Jun 05, 2018 7:44

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: 2003
Joined: Jan 02, 2017 0:34
Location: UK

Re: Random numbers

Postby deltarho[1859] » Jun 05, 2018 7:55

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>

Return to “Community Discussion”

Who is online

Users browsing this forum: coderJeff and 24 guests