A very slow prng

General FreeBASIC programming questions.
neil
Posts: 556
Joined: Mar 17, 2022 23:26

Re: A very slow prng

Post by neil »

This passed Practrand to a TeraByte in 57 minutes. Now that's fast. I was using Linux. I also used dodicat's large string algorithm from my64.bas. This works great for testing prng's with Practrand.

Code: Select all

'' 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
Practrand perfect test to a TeraByte no warnings.

rng=RNG_stdin64, seed=unknown
length= 256 gigabytes (2^38 bytes), time= 840 seconds
no anomalies in 369 test result(s)

rng=RNG_stdin64, seed=unknown
length= 512 gigabytes (2^39 bytes), time= 1712 seconds
no anomalies in 383 test result(s)

rng=RNG_stdin64, seed=unknown
length= 1 terabyte (2^40 bytes), time= 3440 seconds
no anomalies in 397 test result(s)
hhr
Posts: 206
Joined: Nov 29, 2019 10:41

Re: A very slow prng

Post by hhr »

Hi neil, that is already good.
Maybe your generator is good for 64 bit, but you are testing the lower 32 bit only (Two times 'Ulong Ptr').
To be able to see through your program better, I took the liberty of modifying it a bit.
I have tested both programs (32 bit and 64 bit) up to 128 GB.
A terabyte test would take more than five hours on my computer.
For a terabyte test you can write '-tlmin 1TB' instead of '-tlmin 1KB'.

Code: Select all

'' 3 line PRNG by neil  
'' 3line32 | RNG_test stdin32 -tlmin 1KB -multithreaded

#cmdline "-gen gcc -O 2"

Dim Shared As Ulongint s1, s2
s1 = 92348739
s2 = 38346595

Function Threeliner32ByNeil As Ulong '' Ulong
   s1 = (s1 Xor (s1 * s2)) + (s1 Shr 16) '' Order of variables, with brackets it is better to understand.
   s2 = (s1 Xor (s1 * s2)) + (s2 Shl 16)
   s1 = (s1 Xor (s1 * s2)) + (s1 Shr 16)
   Return s1
End Function

Dim Shared S As String * 1048576 '' = 262144 * 4 ; Ulong has 4 bytes.
Dim As Ulong Ptr SPtr, BasePtr '' Ulong
Dim As Long j

SPtr = Cptr(Ulong Ptr, Strptr( S )) '' Ulong
BasePtr = SPtr

Do
   For j = 1 To 262144
      *SPtr = Threeliner32ByNeil '' Name of the function.
      SPtr += 1
   Next
   Print s;
   SPtr = BasePtr
Loop

Code: Select all

'' 3 line PRNG by neil  
'' 3line64 | RNG_test stdin64 -tlmin 1KB -multithreaded

#cmdline "-gen gcc -O 2"

Function Threeliner64ByNeil As Ulongint
   Static As Ulongint s1 = 92348739
   Static As Ulongint s2 = 38346595
   s1 = (s1 Xor (s1 * s2)) + (s1 Shr 16) '' Order of variables, with brackets it is better to understand.
   s2 = (s1 Xor (s1 * s2)) + (s2 Shl 16)
   s1 = (s1 Xor (s1 * s2)) + (s1 Shr 16)
   Return s1
End Function

Dim Shared S As String * 1048576 '' = 131072 * 8 ; Ulongint has 8 bytes.
Dim As Ulongint Ptr SPtr, BasePtr '' Ulongint instead of Ulong
Dim As Long j

SPtr = Cptr(Ulongint Ptr, Strptr( S )) '' Ulongint instead of Ulong
BasePtr = SPtr

Do
   For j = 1 To 131072
      *SPtr = Threeliner64ByNeil '' Name of the function.
      SPtr += 1
   Next
   Print s;
   SPtr = BasePtr
Loop
Luxan
Posts: 222
Joined: Feb 18, 2009 12:47
Location: New Zealand

Re: A very slow prng

Post by Luxan »

Hi DeltaRho

At MIT there's a second order non linear differential equation
that expresses the behaviour of a series LRC diode circuit.

Might your code be able to find an approximate answer to
this.

Can't quite see how to solve this using the Lambert-W function.
neil
Posts: 556
Joined: Mar 17, 2022 23:26

Re: A very slow prng

Post by neil »

@hhr
You broke my PRNG algorithm. Practrand is complaining "Evaluation unusual". I only intended for it to work a 32 bit output. The ULongint is only for the seed numbers. I need large seed numbers or it won't work. Please put it back the way it was.
neil
Posts: 556
Joined: Mar 17, 2022 23:26

Re: A very slow prng

Post by neil »

@hhr
This has been updated this modified version passed Practrand to 32 TeraBytes with no complaints.
Here it is the newest 3-line PRNG 64 bit output version.

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
Last edited by neil on May 08, 2023 22:43, edited 3 times in total.
hhr
Posts: 206
Joined: Nov 29, 2019 10:41

Re: A very slow prng

Post by hhr »

@neil
I have not changed your algorithm. I just rearranged it to understand it better.

I also tried your new 3-line algorithm.
s2 must be greater than zero and with different initial values I had a few 'unusual' and only once 'mildly suspicious' in the KB range.
I think this is very good.
I tested up to 256 GB and on my machine a 1 TB test would have taken about 4.5 hours. That is fast.

Here is another one of my programs. It is slow, but generates a different output in each run.
I tested it up to 512 GB, a terabyte test would have taken about 6.7 hours.

Code: Select all

Function SumOfTSCValues32 As Ulong
   Static As Ulong sum
   Asm
      rdtsc
      Add Dword Ptr [sum], eax
   End Asm
   Return sum
End Function

Function Mwc32 As Ulong ' Multiply-with-carry
   Dim As Ulongint t, m = 698769069
   Static As Ulong z = 521288629
   Static As Ulong c = 7654321
   t = m * z + c
   c = t Shr 32
   z = t
   Return z
End Function

Function NextNumber32 As Ulong
   Return Mwc32 + SumOfTSCValues32 '' [ + | Xor ]
End Function

Function NextNumber64 As Ulongint
   Dim As Ulongint a = Mwc32 + SumOfTSCValues32
   a Shl= 32
   Return a + Mwc32 + SumOfTSCValues32
End Function

'===========================================

Do
   Dim As Ulong a, b
   a = SumOfTSCValues32
   b = Mwc32
   Print "TSC:"; Tab(10); Bin(a, 32)
   Print "Mwc:"; Tab(10); Bin(b, 32)
   Print "Mwc+TSC:"; Tab(10); Bin(a + b, 32)
   Print
   Print Bin(NextNumber32, 32)
   Print Bin(NextNumber64, 64)
   Print
Loop Until Getkey = 27 '' Esc
Last edited by hhr on May 09, 2023 17:27, edited 1 time in total.
neil
Posts: 556
Joined: Mar 17, 2022 23:26

Re: A very slow prng

Post by neil »

@hhr
I updated my 64 bit output version it passed Practrand to 32 TeraBytes.

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

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

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

rng=RNG_stdin64, seed=unknown
length= 32 terabytes (2^45 bytes), time= 121611 seconds
no anomalies in 455 test result(s)
hhr
Posts: 206
Joined: Nov 29, 2019 10:41

Re: A very slow prng

Post by hhr »

This program measures the time duration of a loop and outputs different values each time.

Code: Select all

dim as double t
dim as ulong i
do
   i = 0
   t = timer
   do while i < 100000000
      i += 1
   loop
   t = timer - t
   print t
loop until getkey = 27
The original idea was to use this inaccuracy for a prng that produces a non-repeatable sequence.

Code: Select all

Function CountLoops(dt As Double) As Ulongint
   Static As Ulongint counter, sum
   Dim As Double t = Timer + dt
   Do While Timer < t
      counter += 1 ''or another number.
   Loop
   sum += counter
   Return sum
End Function

Function Parity64(Byval n As Ulongint) As Ulongint
   n = n Xor (n Shr 32)
   n = n Xor (n Shr 16)
   n = n Xor (n Shr 8)
   n = n Xor (n Shr 4)
   n = n Xor (n Shr 2)
   n = n Xor (n Shr 1)
   Return n And 1
End Function 

Function NextNumber64 As Ulongint
   Dim As Ulongint y, x
   Dim As Ubyte i
   For i = 0 To 63
      x = CountLoops(0.00000001)
      If Parity64(x) Then y = Bitset(y, i)
   Next i
   Return y
End Function

''==========================================

Do
   Print Bin(NextNumber64, 64)
Loop Until Getkey = 27 '' Esc

''==========================================
''Measurement of slowness :-)
Dim As Double t
Dim As Ulongint i, z
Do
   t = Timer
   For i = 0 To 20000
      z += NextNumber64
   Next i
   t = Timer - t
   Print t, z
Loop

Code: Select all

Function CountLoops(dt As Double) As Ulong
   Static As Ulong counter, sum
   Dim As Double t = Timer + dt
   Do While Timer < t
      counter += 1 ''or another number.
   Loop
   sum += counter
   Return sum
End Function

Function Parity32(Byval n As Ulong) As Ulong
   n = n Xor (n Shr 16)
   n = n Xor (n Shr 8)
   n = n Xor (n Shr 4)
   n = n Xor (n Shr 2)
   n = n Xor (n Shr 1)
   Return n And 1
End Function 

Function NextNumber64 As Ulongint
   Dim As Ulong x
   Dim As Ulongint y
   Dim As Ubyte i
   For i = 0 To 63
      x = CountLoops(0.00000001)
      If Parity32(x) Then y = Bitset(y, i)
   Next i
   Return y
End Function

''==========================================

Do
   Print Bin(NextNumber64, 64)
Loop Until Getkey = 27 '' Esc

''==========================================
''Measurement of slowness :-)
Dim As Double t
Dim As Ulongint i, z
Do
   t = Timer
   For i = 0 To 20000
      z += NextNumber64
   Next i
   t = Timer - t
   Print t, z
Loop
:D
neil
Posts: 556
Joined: Mar 17, 2022 23:26

Re: A very slow prng

Post by neil »

@hhr
With your changes this passed Practrand to 16 TeraBytes.

Code: Select all

Function ThreeLiner As Ulongint
   Static As Ulongint s1 = 8492356923
   Static As Ulongint s2 = 8974240601

'' hhr's changes helped speed up a Practrand test.
   s1 = ((s1 shl 1) + s2) + (s1 shr 16)
   s2 = (s1 + (s2 shl 1)) + (s1 shl 16)
   s1 = ((s1 shl 1) + s2) + (s2 shr 16)
   Return s1
End Function
neil
Posts: 556
Joined: Mar 17, 2022 23:26

Re: A very slow prng

Post by neil »

I am still testing PRNG algorithms.
neil
Posts: 556
Joined: Mar 17, 2022 23:26

Re: A very slow prng

Post by neil »

This passed Practrand to 8 TeraBytes.
At 16 TeraBytes It got an Evaluation suspicious.
I stopped the test.

Code: Select all

Function ThreeLiner As Ulongint
   Static As Ulongint s1 = 8492356923
   Static As Ulongint s2 = 8974240601
 
   s1 = ((s1 shl 1) + s2) + (s1 + (s1 shr 4))
   s2 = (s1 + (s2 shl 1)) + (s2 + (s2 shl 4))
   s1 = ((s1 shl 1) + s2) + (s1 + (s1 shr 8))
   Return s1
End Function
Post Reply