Single and Range wrappers for minimal PCG PRNG

General FreeBASIC programming questions.
deltarho[1859]
Posts: 4292
Joined: Jan 02, 2017 0:34
Location: UK
Contact:

Re: Single and Range wrappers for minimal PCG PRNG

Post by deltarho[1859] »

I was trying an experiment yesterday - basically I was trying to upset PCG32II. It had shown itself to be stable in any environment I put it in, obviously a good characteristic.

When timing any algorithm we should never rely on a single test - I normally use ten. We also need to employ a 'breathing space' between tests otherwise we only get information on a long test. The breathing space should be random so that we do not synchronise with any else going on in the system. The following uses 'Sleep Rnd * 500 + 500'. From the CPU's perspective that is a long interval.

This is a typical output (using -gen gcc -asm intel -Wc -O3)

Code: Select all

 512
 471
 433
 472
 473
 470
 472
 452
 453
 472
 
Average: 467
Don't know why but the first run is always slightly faster.

I always use pcg.MyRandomize to ensure a 'warm up'.

However, if we comment pcg.MyRandomize this output is typical.

Code: Select all

 324
 307
 307
 298
 299
 305
 307
 306
 298
 307
 
Average: 306
We are, of course, still 'ripping along' at a fair old pace compared with the FreeBASIC generators but a fall of about 35% was not expected. The PractRand one terabyte test used .MyRandomize.

.MyRandomize simply populates the state vector and then executes a warm-up. I did not think that a warm-up would give us the better speed. However, it still needed to be eliminated so I introduced a separate warm-up and saw a repeat of the second run.

Populating the state vector should not give us the better speed either but, perhaps, the default values of zero may be the reason for a slower speed. I then hard wired non-zero values into the pcg32 Type. That, as expected, had no effect.

I then left pcg.MyRandomize commented and introduced pcg.rands; commented in the following code.

This saw a repeat of the first run.

So, just introducing a single sample request was enough to give us the better speed. This did not make sense as the following loop requests 100 million samples.

I am, of course, in run-time thinking. What about compile-time thinking.

Is the compiler learning something when it considers pcg.rands and uses that in the following loop. Perhaps it cannot learn, whatever that is, in the loop itself because it is busy doing other things.

I do not get this behaviour with optimization levels -O1 an -O2, just -O3. I also do not get this behaviour in 64 bit mode. In a nutshell then I only get this behaviour with -O3 and 32 bit mode.

I am not overly concerned about this because I would always use .MyRandomize either in random mode or fixed mode.

If I had been testing without using .MyRandomize and someone suggested I make a single sample request before the loop and an increase of 50% throughput would be on the cards I would have responded with "Are you pulling my leg?"

Any thoughts?

Code: Select all

#Include "PCG32II.bas"
 
Dim As ULong i, j
 
Dim As Double t, tot
Dim As Double a(1 To 10)
Dim pcg As pcg32
 
Randomize
 
pcg.MyRandomize
 
'pcg.rands
 
For j = 1 To 10
  t = Timer
  For i = 1 To 10^8
    pcg.rands
  Next
  t = Timer - t
  Print CInt(100/t)
  a(j) = t
  Sleep Rnd * 500 + 500
Next
 
For j = 1 To 10
  tot += a(j)
Next
tot = tot/10
Print
Print "Average:";CInt(100/tot)
 
Sleep
deltarho[1859]
Posts: 4292
Joined: Jan 02, 2017 0:34
Location: UK
Contact:

Re: Single and Range wrappers for minimal PCG PRNG

Post by deltarho[1859] »

Fixed seeding

As is it is not very imaginative.
For example:

Code: Select all

.MyRandomize( 123456, 100)
Here is a method where we let PCG32II randomly choose the seed/initial state and sequence index. but still been able to repeat a sequence.

Replace 'Type pcg32' with:

Code: Select all

Type pcg32
  Public:
  Declare Sub MyRandomize( seed As Ulongint = 0, seq As Ulongint = 0 )
  Declare Function rand() As Ulong
  Declare Function rands() As Single
  Declare Function range( Byval One As Long, Byval Two As Long ) As Long
  Declare Function GetSeed() As Ulongint
  Declare Function GetSeq() As UlongInt
  Private:
  state As ULongInt
  seq   As Ulongint
  seed  As UlongInt
End Type
Add statement to pcg32.MyRandomize:

Code: Select all

This.seed = This.state   ' <-- Add this statement before warm-up
For i As Integer = 1 To 200
  this.rand()
Next i
and add the following two functions:

Code: Select all

Function pcg32.GetSeed() As Ulongint
  Return This.seed
End Function
 
Function pcg32.GetSeq() As Ulongint
  Return This.seq
End Function
Example usage:

Code: Select all

#Include "PCG32II.bas"
 
Dim As ULong i, __
Dim pcg As pcg32
 
Width 40, 32
 
' Random seed/initial state & random sequence index
pcg.MyRandomize
 
For i = 1 To 4
  Print pcg.rands
Next
Print
 
pcg.MyRandomize(pcg.GetSeed, pcg.GetSeq)
For i = 1 To 4
  Print pcg.rands
Next
Print "~~~~~~~~~~"
 
' Random seed/initial state & fixed sequence index
pcg.MyRandomize( __, 123456)
For i = 1 To 4
  Print pcg.rands
Next
Print
 
pcg.MyRandomize(pcg.GetSeed , 123456)
For i = 1 To 4
  Print pcg.rands
Next
Print "~~~~~~~~~~"
 
' Fixed seed/initial state & random sequence index
pcg.MyRandomize(987654321, __)
For i = 1 To 4
  Print pcg.rands
Next
Print
 
pcg.MyRandomize(987654321, pcg.GetSeq)
For i = 1 To 4
  Print pcg.rands
Next
 
Sleep
Typical output:

Code: Select all

 0.01548479
 0.2334835
 0.5991447
 0.1650053

 0.01548479
 0.2334835
 0.5991447
 0.1650053
~~~~~~~~~~
 0.1779528
 0.2600138
 0.3149782
 0.5873141

 0.1779528
 0.2600138
 0.3149782
 0.5873141
~~~~~~~~~~
 0.3688892
 0.867936
 0.9151313
 0.01454218

 0.3688892
 0.867936
 0.9151313
 0.01454218
deltarho[1859]
Posts: 4292
Joined: Jan 02, 2017 0:34
Location: UK
Contact:

Re: Single and Range wrappers for minimal PCG PRNG

Post by deltarho[1859] »

Double Precision

I am not sure if there is much call for this but here is a way to generate double precision random numbers. The method employed is got from pcg-random.org suggested as a means to provide a 64 bit generator. We create two instances of pcg32 with a common seed/initial state but use unique sequence indices. The two sequences are guaranteed not to overlap which ensures that we maintain a 64 bit period when we interleave the two instances.

Obviously, the throughput will be less than pcg32 and got 297MHz on one run compared to pcg32's 470MHz, or thereabouts, using '-gen gcc -asm intel -Wc -O3'. This is another example where compiled BASIC was faster than the asm routine for double precision; which came in at 137MHz. 297MHz is very much faster than any of the FreeBASIC generators and they are all 32 bit generators, outputting double precision - "but not double precision as we know it, Jim" <smile>. With 64 bit mode one run came in at 955MHz.

Included also is a function to simply generate 64 bit random numbers.

The code has not been incorporated into PCG32II.bas - just add to your code if you require 64 bits.

Code plus testbed:

Code: Select all

#include "PCG32II.bas"

Randomize , 5

Function Get64Bit() As UlongInt
Return (Cast( Ulongint, Rnd*(2^16) ) Shl 48) Or (Cast( Ulongint, Rnd*(2^16) ) Shl 32) Or _
       (Cast( Ulongint, Rnd*(2^16) ) Shl 16) Or Rnd*(2^16)
End Function

Dim Shared As pcg32 pcgU, pcgL
Dim As Ulongint seed, seq1, seq2

Width , 32

' Get a random seed
Do
	seed = Get64Bit
Loop Until seed <> 0
' Get random seq1 and seq2
Do
	seq1 = Get64Bit\2
Loop Until seq1 <> 0
Do
	seq2 = Get64Bit\2
Loop Until seq2 <> 0 AndAlso seq2 <> seq1

pcgU.MyRandomize( seed, seq1)
pcgL.MyRandomize( seed, seq2)

Function pcg32randd() As Double
Dim TempVarU As Ulongint = pcgU.rand
Dim TempVarL As Ulongint = pcgL.rand
Return (TempVarU Shl 32 + TempVarL)/2^64
End Function

Function rand64() As Ulongint
Dim TempVarU As Ulongint = pcgU.rand
Dim TempVarL As Ulongint = pcgL.rand
Return (TempVarU Shl 32 + TempVarL)
End Function

'~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Dim As Ulong i
Dim As Double t

For i =1 To 10
	Print pcg32randd
Next
Print
t = Timer
For i = 1 To 10^8
	pcg32randd
Next
t = Timer - t
Print Cint(100/t);"MHz"
Print
Dim As Double tot
For i = 1 To 10^8
	tot += pcg32randd
Next
Print "Average of 10^8 double samples:"
Print tot/10^8
Print
For i =1 To 10
	Print rand64
Next
Print
t = Timer
For i = 1 To 10^8
	rand64
Next
t = Timer - t
Print Cint(100/t);"MHz"
Print
For i = 1 To 10^8
	tot += rand64
Next
Print "Average of 10^8 UlongInt samples:"
Print tot/10^8

Sleep
Typical output:

Code: Select all

0.7244844142238328
 0.3288639006586228
 0.4421658928959756
 0.2503057784210569
 0.2789690510583156
 0.8246482845908344
 0.3474181875890617
 0.2018797069094117
 0.9836970911930738
 0.2764443858985444

 297MHz

Average of 10^8 single samples:
 0.5000007645314547

2611866385563354880
17025239557695269292
7821792802138154523
5450711984170879449
17229855297602988219
2501086403623553106
5133161121061199885
10874322210193440157
6439893502220194760
6560867115308944295

 301MHz

Average of 10^8 UlongInt samples:
 9.223167988184634e+018
deltarho[1859]
Posts: 4292
Joined: Jan 02, 2017 0:34
Location: UK
Contact:

Re: Single and Range wrappers for minimal PCG PRNG

Post by deltarho[1859] »

Double Precision code above replaced - I am using a better method for generating seed, seq1 and seq2.
deltarho[1859]
Posts: 4292
Joined: Jan 02, 2017 0:34
Location: UK
Contact:

Re: Single and Range wrappers for minimal PCG PRNG

Post by deltarho[1859] »

In the above, replace the Get64Bit function with the following:

Code: Select all

Function Get64Bit() As UlongInt
  Return (Cast( Ulongint, Rnd*(2^32) ) Shl 32) Or Cast( Ulongint, Rnd*(2^32) )	
End Function
This is the result of a discussion in another thread.
deltarho[1859]
Posts: 4292
Joined: Jan 02, 2017 0:34
Location: UK
Contact:

Re: Single and Range wrappers for minimal PCG PRNG

Post by deltarho[1859] »

There is a new version of PCG32II.bas here dated 10 July 2017. It is an accumulated update including additions made since 2 July 2017.

.MyRandomize has been improved. It was using, for example, Rnd*(2^64). That results in a 64 bit number but it only has 32 bits of information. To get a full 64 bit the function Get64Bit has been put into PCG32II,bas, so is no longer required to be mentioned if you intend using the Double Precision code above.

A new function, .randse, has been added to the pcg32 structure. The 'e' stands for extended. This outputs double precision but with only 32 bits of granularity. This is in line with how some of the FreeBASIC generators operate. You may ask what took me so long. The reason is quite simple - I did not fully understand what FreeBASIC was up to. Speed reduction? Nope.
dodicat
Posts: 7976
Joined: Jan 10, 2006 20:30
Location: Scotland

Re: Single and Range wrappers for minimal PCG PRNG

Post by dodicat »

deltarho[1859] wrote:In the above, replace the Get64Bit function with the following:

Code: Select all

Function Get64Bit() As UlongInt
  Return (Cast( Ulongint, Rnd*(2^32) ) Shl 32) Or Cast( Ulongint, Rnd*(2^32) )	
End Function
This is the result of a discussion in another thread.
You should provide some sort of proof of concept for this.
Or some sort of demo.

Code: Select all

'Get64GIT() by Deltarho[1859]

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

   'substitute for rnd*N       
function rndX(N as ulongint) as ulongint
    static as ulongint u=18446744073709551615
    return iif(N=u,Get64Bit(),Get64Bit() mod (N+1))
end function

'               f<= range <= l
function range (f as ulongint,l as ulongint) as ulongint
   return RndX(l-f)+(f)
end function

redim as long a(0 to 5)

for n as long=1 to 2000000
    var n= range(18446744073709551610,18446744073709551615)
    var i=vallng(right(str(n),1))'value of last digit
    a(i)+=1
next

for n as long=0 to 5
    print a(n)
next
print

redim a(0 to 9)
'slightly smaller ulongints
for n as long=1 to 2000000
    var n= range(84467440737095510,84467440737095519)
    var i=vallng(right(str(n),1))'value of last digit
    a(i)+=1
next

for n as long=0 to 9
    print a(n)
next
print

sleep

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

Re: Single and Range wrappers for minimal PCG PRNG

Post by deltarho[1859] »

Thanks dodicat.

I will have a go now.

If we examine any bit of 'Cast( Ulongint, Rnd*(2^32) )' then provided Rnd has a granularity of 32 bit and is uniformly distributed then as the number of samples tends to infinity the ratio of set bit to unset bit will tend to 0.5. The likelihood of a consecutive run of 20 unset bits is 0.5^20 = One part in 1048576, that is highly unlikely. The following code does not consider 20 unset bits but 100 million.

The result is the granularity of 'Cast( Ulongint, Rnd*(2^32) ) which in turn also gives us the granularity of FreeBASIC's random number generators.

I get

Code: Select all

FB index 0: 32
FB index 1: 15
FB index 2: 32
FB index 3: 32
FB index 4: 24
FB index 5: 32
Is index 1 'ropey' or what?

So provided that we do not use index 1 or index 4 then Get64Bit will return a 64 bit value will the potential for 64 bit granularity. The Double Precision code aboe uses 'Randomize , 5' and so does .MyRandomize in PCG32II.bas.

This is not a mathematical proof but a statistical 'proof'.

Added: I replaced Rnd with the latest addition .randse and got a granularity of 32 bit. I had already decided that my default generator will be PCG32II and now my default precision will be .randse. 32 bit converts to 9.63 decimal.

Code: Select all

Dim As Long i, j, k, lBitset
Dim x As Ulongint

For k = 0 To 5
  Randomize , k
  For j = 31 To 0 Step -1
    For i = 1 To 10^8
      x = Cast( Ulongint, Rnd*(2^32) )
      If Bit(x,j) = -1 Then
        lBitset = true
        Exit For
      End If
    Next
    If lBitset = False Then Exit For
    lBitset = False
  Next
  Print "FB index";k;":";31-j
Next

Sleep
deltarho[1859]
Posts: 4292
Joined: Jan 02, 2017 0:34
Location: UK
Contact:

Re: Single and Range wrappers for minimal PCG PRNG

Post by deltarho[1859] »

When I ran the above on .rands I got a granularity of 32 which was not expected considering the output is Single. During the 'i' loop we pull out at the first x which has a 'j' bit set and move on to the next bit. If we get through the 'i' loop without finding a bit set then we pull out completely. So, it looked like the first 32 'i' loops fonnd a bit set.

I then set the 'i' loop to 2000 and did a set bit count. The first 24 bits 'hovered' around 1000. The next bit saw a count of about 500. Each subsequent bit saw a reduction until the 33rd bit which was zero followed by zeros thereafter.

Rnd and .randse have a common feature in that they are 32 bit internally and outputs a Double. In their case there was no 'tail' - the granularity was clear. .rands, on the other hand, is 32 bit internally and outputs a Single. I am going to assume that is where the tail is coming from.

I revised the code to do a bit count and 'pull out' if a bit count fell short of expected. I found that 'test_no/3' was the best filter to employ.

This new code gave .rands a granualaity of 24. Adding the Double Precision code I saw that it also had a tail. The filter gave a granularity of 53 which would we should expect for double precision. Here, we have 64 bit internally and outputting a Double, so why a tail? Not sure, but, assuming that the FPU unit is being used, then we will have clipping from 80 bit to 64 bit.

The bit count code gives the same output as the bit test code for Rnd and .randse - it would because they have no tail.

In view of the above and the fact that .randse has the same throughput speed as .rands, I cannot detect a difference, I see no compelling reason to keep .rands so have removed it. Just as well, I felt uncomfortable having too many options.

I have stayed with the name of .randse to remind us that it is neither Single nor Double but a double with only a granularity of 32 bits.

Bit count code:

Code: Select all

#Include "PCG32II.bas"
Dim As Long i, j, k
Dim x As Ulongint
Dim As Ulong test_no
Dim pcg As pcg32
 
test_no = 2000
 
For k = 0 To 5
  redim As Ulong bc(0 To 63)
  Randomize , k
  For j = 63 To 0 Step -1
    For i = 1 To test_no
      x = Cast( Ulongint, Rnd*(2^64) )
      If Bit(x,j) = -1 Then bc(j) +=1
    Next
  Next
  For i = 63 To 0 step -1
    If bc(i) < test_no/3 Then
      Print "FB index";k;":";63-i
      Exit For
    End If
  Next
Next
 
Sleep
 
' To test .randse simply use pcg.randse instead of RND.
deltarho[1859]
Posts: 4292
Joined: Jan 02, 2017 0:34
Location: UK
Contact:

Re: Single and Range wrappers for minimal PCG PRNG

Post by deltarho[1859] »

Nothing monumental here - all that I have done is too add a constructor such that the generator is randomised with a random seed and a random sequence when a UDT is created.

We can still apply a user randomisation but I don't bother, I just let the constructor do it's job and note the seed and sequence if a repeated output is required as in the following code.

Code: Select all

#Include Once "PCG32II.bas"

Dim pcg As pcg32
Dim As UlongInt InitialSeed = pcg.GetSeed, InitialSeq = pcg.GetSeq
Dim As Long i

For i = 1 To 6
  Print pcg.randse
Next
Print
pcg.MyRandomize( InitialSeed, InitialSeq )
For i = 1 To 6
  Print pcg.randse
Next

Sleep
and typically get

Code: Select all

 0.4678401728160679
 0.959404734428972
 0.6074013919569552
 0.5069460743106902
 0.009448804426938295
 0.5524768794421107

 0.4678401728160679
 0.959404734428972
 0.6074013919569552
 0.5069460743106902
 0.009448804426938295
 0.5524768794421107
To save you going back here is the latest version of PCG32II.bas

PCG32II.bas ( 3 Sept 2017 )

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
  Private:
  state As Ulongint
  seq   As Ulongint
  seed  As Ulongint
End Type

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

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

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\2
    Else
      this.state = Get64Bit
      this.seq = seq
    End If
  Else
    If seq = 0 Then
      this.state = seed
      this.seq = Get64Bit\2
    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

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

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

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

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

Constructor pcg32
  This.MyRandomize
End Constructor
deltarho[1859]
Posts: 4292
Joined: Jan 02, 2017 0:34
Location: UK
Contact:

Re: Single and Range wrappers for minimal PCG PRNG

Post by deltarho[1859] »

Just a bit of fun.

The following is an application session only encryption/decryption scheme. The core of the scheme is very simple but gets complexity from the number of rounds used. Each round implements an independent random number generator. No 'password/encryption key' is required as use is made of PCG32II remembering the generator's initial conditions.

Needless to say, if AES is reading this then there is nothing to worry about. "Haven't seen AES posting here" I heard someone cry. Well, that is OK then. <Ha,ha>

The code, as is, displays the result of each round. As you probably know if a message in a messagebox contains one or more null characters the messge is clipped at the first null. For display purposes any nulls are removed. The removal code is by Paul Squires. In a working application we would not, of course, display round results.

The test code uses five rounds. Any more than that and you may nod off clicking the OK button. The example string was subject to 1000 rounds of encryption and decryption and it took just less than 8 milli-seconds. How many rounds you use depends upon the age old question of "How long is a piece of string". <smile>

Code: Select all

#include "Windows.bi"
#Include Once "PCG32II.bas"

Const Rounds As Integer = 5
Const CrLf = Chr(10) + Chr(13)
const DQ = Chr(34)

Declare Function FF_Remove( Byref As String, Byref As String ) As String

Dim As Long i, j
Dim As String s

s = DQ + "The time has come," + DQ + " the Walrus said," + CrLf _
    + DQ + "To talk of many things:" + CrLf _
    + "Of shoes--and ships--and sealing-wax--" + CrLf _
    + "Of cabbages--and kings--" + CrLf _
    + "And why the sea is boiling hot--" + CrLf _
    + "And whether pigs have wings." + DQ

MessageBox( null, s, "Plaintext", MB_OK )

Dim pcg( 1 To Rounds ) As pcg32 ' Set up Rounds x generators
Dim As Integer Temp
' Encryption
For j = 1 To Rounds
  Temp = Iif( j Mod 2, 1, -1)
  For i = 0 To Len(s) - 1
    s[i] = s[i] + pcg(j).range(0,255)*Temp
  Next
  MessageBox( Null, FF_Remove(s, Chr(0)), "Round " + Str(j) + " encryption", MB_OK )
Next
' Decryption
For j = 1 To Rounds
  Temp = Iif( j Mod 2, -1, 1)
  pcg(j).MyRandomize( pcg(j).GetSeed, pcg(j).GetSeq )
  For i = 0 To Len(s) - 1
    s[i] = s[i] + pcg(j).range(0,255)*Temp
  Next
  MessageBox( Null, FF_Remove(s, Chr(0)), "Round " + Str(j) + " decryption", MB_OK )
Next
'MessageBox( Null, s, "PlainText", MB_OK )

Function FF_Remove( Byref sMainString As String, Byref sMatchPattern As String ) As String
  Dim i As Integer 
  Dim s As String 
  If Len(sMainString) = 0 Then Return sMainString
  s = sMainString
  Do
    i = Instr(s, sMatchPattern)
    If i > 0 Then 
      s = Left(s, i - 1) & Mid(s, i + Len(sMatchPattern))
    End If   
  Loop Until i = 0
  Return s
End Function
deltarho[1859]
Posts: 4292
Joined: Jan 02, 2017 0:34
Location: UK
Contact:

Re: Single and Range wrappers for minimal PCG PRNG

Post by deltarho[1859] »

Since writing the above instead of having alternating signs between rounds I looked at alternating signs between characters.

It then occurred to me that instead of alternating signs we could have random signs by using a range of [-255, 255] instead of [0,255]. Being equally distributed we would end up with about half '-' and half '+' but there would be no pattern.

The following example triples the size of the string to encrypt, uses 33 rounds and displays only the final round of encryption.

On my machine the encryption, on a single test, took 120 micro-seconds for encrytion and 193 micro-seconds for decryption. The decryption takes longer because the initial conditions are being retrieved.

At the PCG website, pcg-random.org, the PCG family is described as having a prediction difficulty of challenging as opposed to Mersenne Twister being easy and XorShift 32 being trivial, for example. The prediction difficulty of using 33 independent sequences will not be less challenging but I cannot say if it would be equally challenging or not. Having a random sign on the characters as opposed to an alternating sign on the rounds should make an attack more difficult.

It is worth noting that using a generator other than a compiler's inbuilt generator(s) also makes life harder for a would be attacker. Of course, using a FreeBASIC generator would also restrict us to a single sequence.

AES still has no grounds for concern but this code may be OK for some work.

For a Windows application we could use the CryptProtectMemory API, where the key is not made public, but the code here is not platform dependent.

Compile using console - both Printing and MessageBox are used.

Code: Select all

#include "Windows.bi"
#Include Once "PCG32II.bas"

Const Rounds As Integer = 33
Const CrLf = Chr(10) + Chr(13)
Const DQ = Chr(34)

Dim Shared pcg( 1 To Rounds ) As pcg32 ' Set up Rounds x generators

Function FF_Remove( Byref sMainString As String, Byref sMatchPattern As String ) As String
  Dim i As Integer 
  Dim s As String 
  If Len(sMainString) = 0 Then Return sMainString
  s = sMainString
  Do
    i = Instr(s, sMatchPattern)
    If i > 0 Then 
      s = Left(s, i - 1) & Mid(s, i + Len(sMatchPattern))
    End If   
  Loop Until i = 0
  Return s
End Function

Sub Encrypt( s As String )
  Dim As Integer i, j
  For j = 1 To Rounds
    For i = 0 To Len(s) - 1
      s[i] += pcg(j).range(-255,255) ' Note +=
    Next
  Next
End Sub

Sub Decrypt( s As String)
  Dim As Integer i, j, Temp
  For j = 1 To Rounds
    pcg(j).MyRandomize( pcg(j).GetSeed, pcg(j).GetSeq )
    For i = 0 To Len(s) - 1
      s[i] -= pcg(j).range(-255,255) ' Note -=
    Next
  Next
End Sub

Dim As String s

's = "2E61A5CD4FA57AD2060378239B6C7CAC3505689500EFDF68429C8A029492D2" ' imported passkey

s = DQ + "The time has come," + DQ + " the Walrus said," + CrLf _
+ DQ + "To talk of many things:" + CrLf _
+ "Of shoes--and ships--and sealing-wax--" + CrLf _
+ "Of cabbages--and kings--" + CrLf _
+ "And why the sea is boiling hot--" + CrLf _
+ "And whether pigs have wings." + DQ
s=s+CrLf+s+CrLf+s
MessageBox( null, s, "Plaintext length: " + Str(Len(s)), MB_OK )

Dim As Double t
t = Timer
Encrypt( s )
t = Timer - t
Print "Total encryption time (Micro-seconds):";Int(t*10^6)
MessageBox( null, FF_Remove( s, Chr(0) ), "Final Ciphertext", MB_OK )
t = Timer
Decrypt( s )
t = Timer - t
Print "Total decryption time (Micro-seconds):";Int(t*10^6)
MessageBox( null, s, "Plaintext length: " + Str(Len(s)), MB_OK )
deltarho[1859]
Posts: 4292
Joined: Jan 02, 2017 0:34
Location: UK
Contact:

Re: Single and Range wrappers for minimal PCG PRNG

Post by deltarho[1859] »

I didn't recognise it but the above is actually the same as XOR. [1]

Replace

Code: Select all

s[i] += pcg(j).range(-255,255) ' Note +=
and
s[i] -= pcg(j).range(-255,255) ' Note -=
with

Code: Select all

s[i] Xor= pcg(j).range(0,255)
We now have ourselves a synchronous stream cipher. The same starting state must never be used twice. We cannot guarantee that but since our starting state is seed + sequence and determined randomly then we have 2^64 x 2^63 = 2^127 possible starting states ie a key length of 127 bits per round.

[1] Added: I found a bug in my code snippet test - they are not the same. However, since both methods can alter s 256 ways, including no alteration, and there seems to be no difference in speed then it is a matter of 'six and two threes' as to which we use. I will stay with Xor as that is the classic approach for stream ciphers.
deltarho[1859]
Posts: 4292
Joined: Jan 02, 2017 0:34
Location: UK
Contact:

Re: Single and Range wrappers for minimal PCG PRNG

Post by deltarho[1859] »

We can also replace the subs Encrypt and Decrypt with a single sub.

Code: Select all

Sub EncDec( s As String, Flag as Boolean ) ' Decrypt if Flag is true
  Dim As Integer i, j
  For j = 1 To Rounds
    If Flag Then pcg(j).MyRandomize( pcg(j).GetSeed, pcg(j).GetSeq )
    For i = 0 To Len(s) - 1
      s[i] Xor= pcg(j).range(0,255)
    Next
  Next
End Sub
This may now appear ridiculously simple for encryption/decryption but the cipher is actually the function pcg32.range.
deltarho[1859]
Posts: 4292
Joined: Jan 02, 2017 0:34
Location: UK
Contact:

Re: Single and Range wrappers for minimal PCG PRNG

Post by deltarho[1859] »

I have mentioned a couple of times that the PCG paper should have used the PractRand test suite as well as TestU01. O'Neill has admitted that "PractRand hadn't been on my radar". This has been remedied and she is now an advocate of PractRand. PCG32, in particular, was tested up to 32TB, PractRand's maximum test, and it passed. The test took over six days to complete.

Her conclusion: "Results from PractRand do indeed validate the statistical quality claims I've made about the PCG family. Yay!"

'Yay''? I think she is American. <smile> She is based in Claremont, CA.
Post Reply