A strong PRNG

General FreeBASIC programming questions.
Post Reply
neil
Posts: 555
Joined: Mar 17, 2022 23:26

A strong PRNG

Post by neil »

With this opening post I never claimed the algorithm passed any Practrand test. I did not know about Practrand when I posted this.
A simple algorithm for a strong PRNG. This PRNG math formula is George Marsaglia's multiply with carry. George Marsaglia was a mathematician and computer scientist. This passed all of the diehard battery of tests. The PRNG part is just 3 lines of code.

Code: Select all

'' Pseudo random number generator by Neil
'' The prng math formula is George Marsaglia's multiply with carry

'' This will fail any Practrand test. I only learned about Practrand after I posted it.
'' This passed all of the diehard battery of tests
'' This is a strong prng

dim as uinteger i,r1,r2
dim as ushort sr

'' 2 seed numbers from timer different numbers everytime
r2 = timer: r1 = r2 * 2

'' 2 seed numbers for same numbers every time on first run
'' r1 = 521288629:r2 = 3624316069

For i = 1 to 20

'' The magic is done with the next 3 lines of code
   r1 = 36969 * (r1 and 65535) + (r1 shr 16)
   r2 = 18000 * (r2 and 65535) + (r2 shr 16)
   r1 = (r1 shl 16) + r2  ''r1 = large prng numbers

'' sr = small prng numbers 0 - 255 
   sr = (r1 mod 256)
   print sr,r1

next

print
print i-1;" Random Numbers"
sleep
Last edited by neil on Mar 29, 2023 5:50, edited 2 times in total.
neil
Posts: 555
Joined: Mar 17, 2022 23:26

Re: A strong PRNG

Post by neil »

PRNG 16 color pixel test.

Code: Select all

'' 16 color PRNG pixel demo by Neil
'' Uses George Marsaglia's PRNG algorithm
'' screen updates every 3 seconds with new pixels
'' if you dont want to wait 3 seconds press a key

Dim shared as uinteger r1,r2
Dim As ulong i
Dim As ushort x,y
DIm As uByte c
Declare Sub Prng ()
ScreenRes 800,600
'' 2 seed numbers for different numbers every time
'' r2 = timer:r1 = timer * 2

'' 2 seed numbers for same numbers every time on first run
r1 = 521288629:r2 = 3624316069

Do
color 14,0
CLS

for i = 1 to 80000
  prng:x = (r1 mod 800)
  prng:y = (r1 mod 600)
  prng:c = (r1 mod 16) '' pixel color 0 - 15
  pset(x,y),c
next 

sleep 3000
Loop Until Inkey = chr(27)

Sub Prng()
   r1 = 36969 * (r1 and 65535) + (r1 shr 16)
   r2 = 18000 * (r2 and 65535) + (r2 shr 16)
   r1 = (r1 shl 16) + r2
End Sub
deltarho[1859]
Posts: 4292
Joined: Jan 02, 2017 0:34
Location: UK
Contact:

Re: A strong PRNG

Post by deltarho[1859] »

Hi neil

It is nice to see someone else getting involved in PRNGs.

Unfortunately, I have a few issues with your opening post.

Firstly, I do not recognize the 'math formula' as Multiply-with-carry (MWC).

There was a problem with MWC, and Marsaglia corrected that with Complementary-multiply-with-carry (CMWC). The best description of MWC and CMWC is at Wikipedia.

Marsaglia also introduced a lag MWC sequence. Lag 4 gives a period of 2^157, lag 8 gives a period of 2^205 up to lag 4096 giving a period of 2^131086. I ported CMWC4096 from PowerBASIC to FreeBASIC in 2018. The 'engine' is in asm. I wrote it for fun – nobody needs a period of 2^131086. Having said that, Marsaglia issued a challenge for a lag 8192 and lag 16384. As far as I know, nobody rose to the challenge and Marsaglia died shortly after in 2011 aged 86.

MWC is a bit long in the tooth, and the diehard test suite most certainly is being first published in 1995.

There are a few test suites today which are superior, and my favourite is PractRand. CMWC4096 got to 2TiB with very few small anomalies and is fairly fast.

In the last few years, a few PRNGs have been published and I have implemented most, if not all, of them on this forum. My favourite, regarding functionality, is MsWsII and comes with a Help file.
hhr
Posts: 205
Joined: Nov 29, 2019 10:41

Re: A strong PRNG

Post by hhr »

I was looking for a third generator for the following experiment. Thanks a lot.
lcg32_bad fails immediately with PractRand, xorshift32 manages 32KB and prng 1MB.
All three additively linked I tested with PractRand up to 256GB.

Code: Select all

dim shared as ulong r1,r2
r1 = 521288629:r2 = 3624316069 ' Two starting values

function prng as ulong
   r1 = 36969 * (r1 and 65535) + (r1 shr 16)
   r2 = 18000 * (r2 and 65535) + (r2 shr 16)
   r1 = (r1 shl 16) + r2
   return r1
end function

''-----------------------------------------

dim shared as ulong x32 = 314159265 ' Starting value, must be greater than zero

function xorshift32 as ulong ' https://en.wikipedia.org/wiki/Xorshift
   x32 Xor= (x32 shl 13)
   x32 Xor= (x32 shr 17)
   x32 Xor= (x32 shl 5)
   return x32
end function

''-----------------------------------------

dim shared as ulong x_lcg = 123456789 ' Starting value

function lcg32_bad as ulong ' https://en.wikipedia.org/wiki/Linear_congruential_generator
   x_lcg = x_lcg + 3567564561
   return x_lcg
end function

''-----------------------------------------

function nextnumber32 as ulong
   return prng + xorshift32 + lcg32_bad
end function

''-----------------------------------------

do
   print nextnumber32,bin(nextnumber32,32)
loop until getkey = 27 ' Esc

''-----------------------------------------

chdir "Path to PractRand's RNG_test.exe" ' PractRand Version 0.94
dim as string s = "RNG_test stdin32"
's &= " -tlmin 1KB"
's &= " -tlmaxonly"
s &= " -multithreaded"
open pipe s for binary access write as #1
do
   put #1,,nextnumber32
loop ' until len(inkey)
'close #1
'end
https://en.wikipedia.org/wiki/KISS_(algorithm)
https://de.wikipedia.org/wiki/KISS_(Zuf ... generator)
Last edited by hhr on Apr 06, 2023 8:51, edited 3 times in total.
neil
Posts: 555
Joined: Mar 17, 2022 23:26

Re: A strong PRNG

Post by neil »

Looking further into prng's someone even wrote code for a mersenne-twister-predictor. https://github.com/kmyk/mersenne-twister-predictor Thanks for info about PractRand.
dafhi
Posts: 1640
Joined: Jun 04, 2005 9:51

Re: A strong PRNG

Post by dafhi »

hi neil! i've also messed with prng creation. if you're into building one, i recommend starting with ubyte literals. if you're more adventurous, you could make a less-than-8-bit-literal system.

then have a suite of analysis tools.

Veritasium in a recent vid mentions (at least in thumbnail) that quantum computers already make classical cryptography obsolete. but for learning, there are a few here who enjoy prngs a great deal
deltarho[1859]
Posts: 4292
Joined: Jan 02, 2017 0:34
Location: UK
Contact:

Re: A strong PRNG

Post by deltarho[1859] »

@hhr

If we have two sequences A and B and one of them is random, then A + B will be random.

If we have two or more sequences and none are particularly random, then their addition will not be particularly random either. If none are random, then their addition will not be random.
deltarho[1859]
Posts: 4292
Joined: Jan 02, 2017 0:34
Location: UK
Contact:

Re: A strong PRNG

Post by deltarho[1859] »

dafhi wrote:quantum computers already make classical cryptography obsolete
RSA and ECDSA are certainly in trouble. AES 128 and SHA256 may be in trouble. AES 256 and SHA512 will probably be OK, and if not, both can be made quantum resistant by adding more rounds.
dafhi
Posts: 1640
Joined: Jun 04, 2005 9:51

Re: A strong PRNG

Post by dafhi »

i don't have nearly as much expertise for sure. i'm getting a sense though that "moore's law" for quantum comps is exponential compared with classical
Last edited by dafhi on Mar 22, 2023 2:15, edited 1 time in total.
dodicat
Posts: 7976
Joined: Jan 10, 2006 20:30
Location: Scotland

Re: A strong PRNG

Post by dodicat »

I tested this to 1Tb practrand.

Code: Select all



namespace rand64
dim as ulongint a,b,c,d,e
const max=18446744073709551615ull

function rndU  as  ulongint
   e = a - ((b shl 7) or (b shr (57)))
   a = b xor ((c shl 13) or (c shr (51)))
   b = c + ((d shl 37) or (d shr (27)))
   c = d + e
   d = e + a
   return d
end function

sub autoinit() constructor
var n=timer
a=n:b=n:c=n:d=n
    for m as long=n to n+2
        a+=m
    rndU()
next
print "automatic warm up done"
end sub

sub init(n as long)
    rand64.a=n:rand64.b=n:rand64.c=n:rand64.d=n
    for m as long=n to n+2
        rand64.a+=m
    rand64.rndU()
    next
end sub

#define rndf  rand64.rndU/rand64.max
#define rangeI(f,l) clngint((rand64.rndU() mod (((l)-(f))+(1))) + (f))
#define rangeF(f,l) Rndf * ((l) - (f)) + (f)
end namespace


#cmdline "-gen gcc -O 2"

#define millions 100000000

rand64.init(10000)

dim as long a(-5 to 5)

for n as long=1 to millions
      a(rangeI(-5,5))+=1
next


for n as long=-5 to 5
      print a(n)
next
dim as ulongint tot
for n as long=-5 to 5
      tot+=a(n)
next n
print"-----------"
print tot

dim as double d
for n as long=1 to millions
      d+=rndf
next
print
print d/millions
print
rand64.init(millions)
for n as long=1 to 5
      print rand64.rndu
next

print
rand64.init(millions)
for n as long=1 to 5
      print rand64.rndu
      next
sleep
 
 
neil
Posts: 555
Joined: Mar 17, 2022 23:26

Re: A strong PRNG

Post by neil »

@dodicat
Why do you have 2 identical FOR LOOPS at the end of your code ? I need something with limited range numbers working with 1 byte at a time. Writing small files. Would this be the correct way to do this ?

Dim As UByte rb
Open "rbtest.bin" For Binary As #1
for n as long=1 to 32
rb = rand64.rndu mod 256
put #1,,rb
next
Close #1
dodicat
Posts: 7976
Joined: Jan 10, 2006 20:30
Location: Scotland

Re: A strong PRNG

Post by dodicat »

Hello neil
Just to show that the sequence can be repeated with seeding (init)

Dim As UByte rb
Open "rbtest.bin" For output As #1
for n as long=1 to 32
'rb = rand64.rndu mod 256
rb=rangeI(0,255)
print #1,rb
next
Close #1

(to make it readable)
Binary would be OK also I reckon.
dafhi
Posts: 1640
Joined: Jun 04, 2005 9:51

Re: A strong PRNG

Post by dafhi »

i'd like to take this opportunity to apologize. specifically to deltarho[1859]. i can be a buzz-kill and while i may have intentionally been an a-hole before, such qualities can be residual even if they are not my intention now.

enjoy
neil
Posts: 555
Joined: Mar 17, 2022 23:26

Re: A strong PRNG

Post by neil »

PractRand users how long does it usually take for RNG_test for a one TeraByte test?
My tests have taken hours. Also what does Evaluation unusual mean? Thanks
dafhi
Posts: 1640
Joined: Jun 04, 2005 9:51

Re: A strong PRNG

Post by dafhi »

32 TB took approx 1 week
16 ~ 4 days
8 ~ 2 days
4 ~ 1 day
2 ~ 1/2 day
1TB - 1/4 day
Post Reply