A strong PRNG

[neil]

@dodicat
FB64.bas is my favorite prng. How could I use it as an easy drop in replacement for FreeBasics RND.

Example
I don't care about FreeBasic's "Randomize" as that's done with seed numbers anyways.

FreeBasic's RND x = (rnd * 64) + 1

Could FB64.bas be used in such as x =(fb64rng * 64) + 1
or would this be to difficult to implement?

I was looking for an easy drop in replacement without changing a lot of code.
Then I could test different prng's much easier.

[dodicat]

To get a random double between [0 and 1) then divide the output by 18446744073709551615 for a 64 bit output generator or by 4294967295 for a 32 bit output generator.
I had it done like:
#define rndf rand64.rndU/rand64.max where rand64max is
const max=18446744073709551615ull
and the rand64. before means access to the namespace.

Is this what you mean?

[neil]

@dodicat

x = UByte
FreeBasic's RND x = (rnd * 64) + 1 pick a random number between 1 and 64

x= Ubyte
x = (fb64rng * 64) + 1 pick a random number between 1 and 64 I need to limit the number range somehow

"Fb64rng" is just a label i made up because RND is a keyword for FreeBasic's PRNG

[dodicat]

Something like:

Code: Select all

#define integerrange(f,l) Int(Rnd*(((l)+1)-(f))+(f))

#define doublerange(f,l) Rnd * ((l) - (f)) + (f)

for n as long=1 to 30
    randomize n
    print integerrange(1,64),
    randomize n
    print doublerange(1,64)
next
sleep
 

(randomising to set the seeds equal--entirely optional)

[neil]

@dodicat
Yes something like that will work.
Thanks

[neil]

@dodicat

x = UByte
Using FreeBasic's built in x =(RND * 64) + 1

How could I get 64 random numbers with only 1 of each number no duplicates?

[neil]

@dodicat
My two line prng algorithm with your mods to speed it up.

I have only tested this with FBC64.
I increased string s to a GigaByte. I got this compiler warning.
Variable too large for stack, consider making it SHARED

I made these changes and dim shared fixed it.

dim shared as string *1073741824 s '' 1 GigaByte for Practrand Test

for n as long=1 to 1073741824 '' 1 GigaByte for Practrand Test


Now this FreeBasic code is now a 3 hour Practrand test to a TeraByte.
My C version is a 4 hour test to a TeraByte. I need to add something like this to my C version.

[neil]

This passed Practrand to 16 TeraBytes with no complaints.
This is my new 3 line prng. It uses dodicat's large string algorithm for a very fast one TeraByte Practrand test. It only took 57 minutes.

Code: Select all

'' This passed Practrand to 16 TeraBytes perfectly with no complaints.
'' 3 line PRNG by neil  
'' 3line | RNG_test stdin64 -multithreaded

#cmdline "-gen gcc -O 2"
DIm AS Ulongint s1,s2

s1 = 92348739: s2 = 38346595
Dim Shared S As String * 1048576
Dim As Ulong Ptr SPtr, BasePtr
Dim As Long j
SPtr = Cptr(Ulong Ptr, StrPtr( S ))
BasePtr = SPtr

Do

For j = 1 to 262144
 
    '' 3 line PRNG algorithm 
    s1 = (s1 xor (s2 * s1)) + (s1 shr 16)
    s2 = (s1 xor (s1 * s2)) + (s2 shl 16)
    s1 = (s1 xor (s1 * s2)) + (s1 shr 16)

  *SPtr = s1
    SPtr += 1
  Next
  print s;
  SPtr = BasePtr
Loop

[neil]

This is a minimal C language version that works with Windows. I'm not sure how to add the 1048576 MiB string buffer algorithm to speed it up.

Code: Select all

// 3 line prng by Neil 
// C language Windows version
// prng3 | RNG_test stdin64 -multithreaded

#include <stdio.h>
#include <stdint.h>
#include <io.h>
#include <fcntl.h>

int main() {

unsigned long long s1,s2;
s1 = 92348739; s2 = 38346595;
_setmode( _fileno( stdout ), _O_BINARY);

while(1) {
s1 = (s1 + (s2 + s1)) + (s1 >> 16);
s2 = (s1 + (s1 + s2)) + (s2 << 16);
s1 = (s1 + (s1 +  s2)) + (s1 >> 16);
int32_t bval = s1;
fwrite((void*) &bval, sizeof(bval), 1, stdout);
}
}

This new C++ 3-line PRNG outputs 64 bits. It passed Practrand perfectly with no complaints to 32 TeraBytes.
Here's the C++ 64 bit output version that works with Windows also. It uses a 1MiB string buffer to speed up testing with Practrand.

Code: Select all

// a new 3 line PRNG C++ 64 bit output version By Neil
#include<iostream>
#include<cstdint>
#include <string>
#include <fcntl.h> // needed for _setmode only for Windows

namespace prng
{

uint64_t & threeliner()
{
  uint64_t static s1 = 92348739;
  uint64_t static s2 = 38346595;

 //   a new 3 line PRNG 64 bit output version 
    s1 = (s1 + (s1 + s2)) + (s1 >> 16);
    s2 = (s2 + (s1 + s2)) + (s1 << 16);
    s1 = (s1 + (s1 + s2)) + (s2 >> 16);
    return s1;
}
}// namespace prng ends

int main()
{
	std::string s;
	s.resize (1048576);

uint64_t *sptr;
uint64_t *baseptr;
uint32_t j;
sptr=(uint64_t *) &s[0];
baseptr = sptr;

// it needs _setmode only for Windows 
_setmode( _fileno( stdout ),  _O_BINARY );

while(1)
{
    for(j=1;j<=131072;j++)
    {
        *sptr = (uint64_t) prng::threeliner();
     sptr++;
    }

   std::cout<<s;
   sptr = baseptr;
}
}

// g++ -Wall prng3.cpp -o prng3
// prng3 | RNG_test stdin64 -multithreaded 

[neil]

The newest 3-line PRNG algorithm

This passed Practrand to 16 TeraBytes.
s1 = 92348739: s2 = 38346595

3-Line 64 bit output algorithm.
s1 = (s1 * (s1 + s2)) + (s1 shr 16)
s2 = (s2 xor (s1 + s2)) + (s1 shl 16)
s1 = (s1 * (s1 + s2)) + (s2 shr 16)

[neil]

This is another 3 line PRNG it tested perfect to a TeraByte with Practrand. It's intended output is 32 bits. Although it's being buffered to
1 MiB String before it's sent to Practrand. Thats why I am using Practrand's stdin64. If you change pointers to a Ulongint for a 64 bit output it wont work properly with Practrand. Also this is set for 32 bit. "For j = 1 to 262144" Someone changed this on another version and it broke the prng. It should work properly with "fbc32" and "fbc64".

Code: Select all

'' Another 3 line PRNG by neil  
'' 3line | RNG_test stdin64 -multithreaded

#cmdline "-gen gcc -O 2"

DIm AS Ulongint s1,s2
s1 = 92348739: s2 = 38346595
Dim Shared S As String * 1048576
Dim As Ulong Ptr SPtr, BasePtr
Dim As Long j
SPtr = Cptr(Ulong Ptr, StrPtr( S ))
BasePtr = SPtr

Do

For j = 1 to 262144
 
'' another 3 line PRNG algorithm 
   s1 = (s1 * s2) + (s2 shr 15)  
   s2 = (s2 + s1) + (s1 shl 11)
   s1 = (s1 xor s2) + (s2 shr 9)

  *SPtr = s1
    SPtr += 1
  Next
  print s;
  SPtr = BasePtr
  Loop

[dafhi]

new idea

Code: Select all

type small_literal as ubyte '' < =  ulong for expensive ops

dim as small_literal  a     '' expensive
dim as ulongint       b     '' use only cheap ops

dev w/ small test

Code: Select all

/'  combine preferred prng qualities - 2023 May 6 - by dafhi
  
  1. speed
   expensive ops on small state var (ulong or lower)
  
  2. large period
   (ulongint weyl sequence)

'/

'#include "dsi/boilerplate.bas"
' -- boilerplate.bas - 2023 Mar 19 - by dafhi
#define flo(x)      (((x)*2.0-0.5)shr 1) '' replaces int (and faster) - http://www.freebasic.net/forum/viewtopic.php?p=118633

#undef int
#define int         as integer

  
  namespace myrng


type small_literal as ubyte '' < =  ulong for expensive ops

dim as small_literal  a     '' expensive
dim as ulongint       b     '' 'b' use cheap ops


const lenx8 = len(a)*8      '' num small state bits

const as ubyte        _mask  = 2 ^ (lenx8-0) - 1

' inspired by PCG, calculates a "random" bit rotate
const                 c_rotbits = log(lenx8) / log(2)


sub reset(aa as ulongint = 0, bb as ulongint = 0)
  a = aa
  b = bb
End Sub

sub rotr(byref q as typeof(a), amount as byte)
  q = q shr amount or ( q shl (lenx8 - amount)) and _mask
End Sub

function valu( seed as ubyte = 0) as ulongint
  '' Knuth..  values stolen from a post
'    a = 6364136223846793005ull * (a + seed) + 

  a *= 3 '' expensive ops only on small literals
  b += 1442695040888963407ull '' Knuth

  a xor= b shr (64 - lenx8)
  
  dim as ubyte  rot_amount = a shr (lenx8 - c_rotbits)
  var aa = a
  rotr aa, rot_amount

  return aa
  
End Function
'const mulC = &b10000000001000000001000000010000001000001000010001001011

'    b += ((a+seed) * mulc) shr 1 '' old algo for keeps
'    'rotr b, 4
'    a xor= 1 + b '+ seed

End Namespace

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


  namespace bVis64 '' visualize a binary value

dim as long y '' namespace global

sub reset_y(valu as long = 0)
  y = valu
end sub

sub draw_val( _
  inputval as ulongint, x as long = 1, _
  pixel_size as long = 4, _
  fgcol as ulong = rgb(255,255,255), _
  bgcol as ulong = rgb(0,0,255), _
  pixel_border as long = 1)
    
  var draw_step = pixel_size + pixel_border
  
  line (x - 0,y)-(x + draw_step*64, y+draw_step-1), bgcol, bf
  
  for shift_amount as long = 63 to 0 step -1
    var mycolor = iif((inputval shr shift_amount)and 1, fgcol, bgcol)
    line (x, y) - (x + pixel_size-1, y + pixel_size-1), mycolor, bf
    x += draw_step
  next
  y += draw_step
  
end sub

End Namespace

sub show_me_some_bits
  var y = 20
  var x = 150 + y
  bvis64.reset_y y
  myrng.reset 0,0',0,0
  myrng.a = 0
  myrng.b = 0
  for i as long = 0 to 150
    var pixel_size = 3
    bvis64.draw_val myrng.valu(), x, pixel_size
  next
end sub


var w = 1280
var h = 720

ScreenRes w,h,32

  for period_test int = 0 to 3
myrng.reset period_test, period_test*2

  screenlock
for y as long = 0 to h-1
  for x as long = 0 to w-1
    var c = myrng.valu * (1 + 256 + 65536)
    pset(x,y),c
  Next
Next
show_me_some_bits
screenunlock

sleep 300
next

sleep

[neil]

This algorithm the first 3 line one I posted passed Practrand to 16 TeraBytes. I Tested it on a slow PC it took over 22 hours.
It was a perfect test with no complaints from Practrand.

'' 3 line PRNG algorithm
s1 = (s1 xor s2 * s1) + (s1 shr 16)
s2 = (s1 xor s1 * s2) + (s2 shl 16)
s1 = (s1 xor s1 * s2) + (s1 shr 16)

rng=RNG_stdin64, seed=unknown
length= 4 terabytes (2^42 bytes), time= 20364 seconds
no anomalies in 422 test result(s)

rng=RNG_stdin64, seed=unknown
length= 8 terabytes (2^43 bytes), time= 40784 seconds
no anomalies in 434 test result(s)

rng=RNG_stdin64, seed=unknown
length= 16 terabytes (2^44 bytes), time= 81484 seconds
no anomalies in 445 test result(s)

[dafhi]

i'm thinking my idea is half-baked. compiler might use big nums regardless. i shall look at the asm when i get a chance.

congrats neil.

there's a new lang coming out, Mojo made by Modular, looks great

[neil]

This new 3-line PRNG outputs 64 bits. It passed Practrand perfectly with no complaints to 32 TeraBytes.

Code: Select all

'' 3 line  PRNG 64 bit output by Neil
'' This passed Practrand to 32 TeraBytes with no complaints.
'' prng3 | RNG_test stdin64 -multithreaded

#cmdline "-gen gcc -O 2"

Function ThreeLiner As Ulongint
   Static As Ulongint s1 = 92348739
   Static As Ulongint s2 = 38346595
    s1 = (s1 * (s1 + s2)) + (s1 shr 16)
    s2 = (s2 xor (s1 + s2)) + (s1 shl 16)
    s1 = (s1 * (s1 + s2)) + (s2 shr 16)
   Return s1
End Function

Dim Shared S As String * 1048576
Dim As Ulongint Ptr SPtr, BasePtr 
Dim As Long j

SPtr = Cptr(Ulongint Ptr, Strptr( S )) 
BasePtr = SPtr

Do
   For j = 1 To 131072
      *SPtr = ThreeLiner
      SPtr += 1
   Next
   Print s;
   SPtr = BasePtr
Loop