A very slow prng

[hhr]

The output of this program cannot be repeated. It uses the timer function to calculate the output.

Because Windows calculates when the program should be active, the output cannot be random.
But if you don't know how Windows calculates it, you can consider the sequence as random.
It is a matter of point of view.

Anyway, if you need a non-repeatable sequence that you know how and where it came from, maybe such a program can be useful.

I have tested the program with PractRand and RaBiGeTe.

Code: Select all

Function SumOfTimerValues As Double
   Dim As Double a
   Static As Double b, sum
   Do
      a = Timer
      If (a <> b) Then b = a : Exit Do
   Loop
   sum += a
   Return sum
End Function

Function DoubleToUlongint(x As Double) As Ulongint
   Dim As Ulongint Ptr p = Cast(Ulongint Ptr, @x)
   Static As Ulongint sum
   sum += (*p)
   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
   Dim As Ubyte i
   For i = 0 To 63
      If Parity64(DoubleToUlongint(SumOfTimerValues)) Then y = Bitset(y, i)
   Next i
   Return y
End Function

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

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

Translated with www.DeepL.com/Translator (free version)

[deltarho[1859]]

@hhr

You very nearly scored 'nul points' as they say in the Eurovision Song Contest.

Who would have thought that summing values taken from the temporal dimension could be a source of entropy for a PRNG? Well, you did and you seem to have found some.

Since "Top quality distribution uniformity is a necessary condition for top quality randomness but it is not sufficient." the first thing that I do is to provide a dump for ENT to examine. If the distribution uniformity is poor then I don't bother getting PractRand out.

Here is a 100MiB dump examination.

Code: Select all

Entropy = 7.999998 bits per byte.
 
Optimum compression would reduce the size
of this 104857600 byte file by 0 percent.
 
Chi square distribution for 104857600 samples is 278.00, and randomly
would exceed this value 15.42 percent of the times.
 
Arithmetic mean value of data bytes is 127.5090 (127.5 = random).
Monte Carlo value for Pi is 3.141501051 (error 0.00 percent).
Serial correlation coefficient is -0.000056 (totally uncorrelated = 0.0).

The first five metrics are good. The serial correlation coefficient with four zeros after the decimal point is telling us that it is worth a PractRand run.

I have tested the program with PractRand and RaBiGeTe.

I am going to take your word for that. This PRNG is so slow, goodness knows how long a PractRand test would take.

How far did you go with PractRand?

Firstly, this PRNG works. Secondly ",maybe such a program can be useful." is, to my mind, questionable given the variety of PRNGs we have available nowadays.

What I find commendable is the uniqueness of your approach. Using Timer is unusual.

Well done and thanks.

[srvaldez]

hello deltarho[1859]
I ran your code viewtopic.php?t=32095
like so

Code: Select all

dim as double sum, t
dim as long i

sum=0
t=timer
for i= 1 to 10000000
	sum+=CryptoDX
next
t=timer-t
? sum
? t
sleep

time 13 seconds

then I ran hhr's code likewise

Code: Select all

dim as double sum, t
dim as long i

sum=0
t=timer
for i= 1 to 10000000
	sum+=NextNumber64
next
t=timer-t
? sum
? t

time 24 seconds

but if I shorten the loop to 1000000 then your time is about .003 seconds and hhr's 2.4 seconds
hhr's time makes sense but yours does not
another puzzling thing is that hhr's code with 1000000 loops is 2.7 times slower in 64-bit

[SARG]

@srvaldez
My times with hhr's code big then smaller loop

gcc64 : 64,56s then 6.4s
gas64 : 64.55 then 6.4s
gas32 : 90s then 9.0s

[srvaldez]

hello SARG
my times are almost identical to yours

[SARG]

Hi srvaldez

hhr's code with 1000000 loops is 2.7 times slower in 64-bit

I did not see that.

[deltarho[1859]]

@srvaldez

With your CryptoDX code above, I get 0.268s for 10,000,000.

How do you get 13s for 10,000,000?

I knew hhr's code was slow when I did a 100MiB dump – it took ages and much longer than dumping other PRNGs.

When it comes to timing, I gave up using a timing loop with gcc. What I now do is to load MsWsII in addition to a new PRNG to be tested. I give them several real life scenarios, number crunching or graphics, and then compare them. I do that in 32-bit and 64-bit. Loop timings and MHz are meaningless.

[srvaldez]

Hi srvaldez

hhr's code with 1000000 loops is 2.7 times slower in 64-bit

I did not see that.

that timing was using the gcc backend, your gas64 times are much faster than gas32

[deltarho[1859]]

I loaded my PRNG graphics test program and looked at xoroshiro128**, a 64-bit output PRNG, and then hhr's code.

xoroshiro128**: 0.36s
hhr : 89.26s

xoroshiro128** was 248 times faster than hhr.

So hhr is "A very slow prng"

I looked at Mersenne Twister as well. That came in at 0.76s and that is a 32-bit output PRNG.

[deltarho[1859]]

So, where does hhr's code's randomness come from? As indicated from SumOfTimerValues. Its output is passed to DoubleToUlongint and its output is passed to Parity64. We go past Parity64 64 times.

Parity64 returns zero if its parameter has an even parity and one otherwise. If hhr's code is random, then we should get as many evens as odds. A counter was put into Parity64 to count the number of even parities. NextNumber64 was called 10^8 times. 'count/64/10^8' should be close to 0.5.

I got 0.50000271875. That'll do.

What this tells us is this PRNG has an excellent distribution uniformity. We need something as rigorous as PractRand to dig deeper. hhr has done that, and a poor result would probably have not seen this thread being started.

So, there we have it, hhr's code is analogous to tossing an unbiased coin.

[deltarho[1859]]

With Windows, since Timer is a function of the QueryPerformanceCounter (QPC) then why not use QPC and be done with it. We no longer need to be involved with Doubles, and we can dispense with DoubleToUlongint.

Here is the code:

Code: Select all

#include "windows.bi"
 
Function SumOfQPCValues As UlongInt
Dim As UlongInt TimeNow
Static As UlongInt sum
  QueryPerformanceCounter Cast( Large_Integer Ptr, @TimeNow )
  sum += TimeNow
  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
   Dim As Ubyte i
   For i = 0 To 63
      If Parity64(SumOfQPCValues) Then y = Bitset(y, i)
   Next i
   Return y
End Function

The 0.50000271875 that I got in the last post is now 0.499995391875.

The graphic test timing has dropped from 89.26s to 22.7s. It is still slow, but faster than using Timer; nearly four times faster.

We now need a PractRand test.

I am going out shortly and may be gone for a while, so will do that on my return.

Since hhr already has code for PractRand, perhaps I can be beaten to it.

[hhr]

Thank you deltarho,
I have tested your program with PractRand from 1KB to 8GB. This took about 1.4 hours.
There were three 'unusual' at 1GB, 2GB and 4GB. At 8GB there were again 'no anomalies'.
(I had tested my program before up to 2GB. This took about five hours.)

[deltarho[1859]]

I have tested the program with PractRand...

I didn't figure on you only going to 2GB.

...from 1KB to 8GB. This took about 1.4 hours.

So, we could be looking at a week to test one TB.

An interesting idea, but I doubt that we have a runner.

[deltarho[1859]]

One more thought.

We have another counter to consider – the Time Stamp Counter (TSC).

I have used the TSC for seeding PRNGs, but not for generating random numbers – nobody does – it ain't random. However, it might work with your SumOf... method.

The 'count/64/10^8' using the QPC was 0.499995391875. Using the TSC I get 0.49999128125.

The graphic test timing has dropped from 22.7s to 18.06s which is nearly five times faster than the Timer method as opposed to nearly four times faster using the QPC.

So, it is still slow. PractRand will now run a little faster, but not by much, I shouldn't think.

I also think that the TSC approach may fail PractRand. Give it a whirl.

It is worth noting that although this PRNG is very slow, many graphics programs written by UEZ and dodicat, for example, very often only require 50 or so random numbers, so the lack of speed may not be an issue. Having said that, with a requirement of only 50 or so random numbers, there is no incentive to use anything apart from the default of Mersenne Twister with RND.

Here is the TSC code. — no need for "windows.bi" this time.

Code: Select all

Function SumOfTSCValues As UlongInt
Dim As UlongInt TimeNow
Static As UlongInt sum
  Asm
    rdtsc
    Mov Dword ptr [TimeNow], eax
    Mov Dword ptr [TimeNow+4], edx
  End Asm
  sum += TimeNow
  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
   Dim As Ubyte i
   For i = 0 To 63
      If Parity64(SumOfTSCValues) Then y = Bitset(y, i)
   Next i
   Return y
End Function

[hhr]

I tested the TSC program with PractRand from 1KB to 4GB. There were two or three 'unusual' and otherwise 'no anomalies'.
Then I ran two separate tests for 8GB and 16GB:

Code: Select all

RNG_test using PractRand version 0.94
RNG = RNG_stdin64, seed = unknown
test set = core, folding = standard (64 bit)

rng=RNG_stdin64, seed=unknown
length= 8 gigabytes (2^33 bytes), time= 4590 seconds
  no anomalies in 294 test result(s)

Code: Select all

RNG_test using PractRand version 0.94
RNG = RNG_stdin64, seed = unknown
test set = core, folding = standard (64 bit)

rng=RNG_stdin64, seed=unknown
length= 16 gigabytes (2^34 bytes), time= 9245 seconds
  no anomalies in 310 test result(s)

I chose a large string buffer to make the TSC program run as fast as possible:
Dim Shared S As String * 134217728
and
For j = 1 To 16777216.