FreeBASIC's PRNG #2

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

Re: FreeBASIC's PRNG #2

Post by deltarho[1859] »

My i7-3770K 3.5GHz (3.9GHz with boost) is not mentioned. It is discontinued being launched Q2'12 so it is a bit long in the tooth now.

The i9s came out last year with 10 to 18 cores. The i9-9900K is due out in October this year and maybe in my next machine. It has 8 cores/16 threads. It has a base frequency of 3.6GHz but will boost to 5GHz with one or two cores or 4.7GHz with all cores. It is said to have 16Mb of L3 cache and a 95W TPD. Pricing is not known yet but maybe about half the price of the 10 core i9. If not then I will go for one of the earlier i9s and that will depend upon what I am prepared to spend. I am not a power user so I don't need Task Manager showing bucket loads of cores.
deltarho[1859]
Posts: 4292
Joined: Jan 02, 2017 0:34
Location: UK
Contact:

Re: FreeBASIC's PRNG #2

Post by deltarho[1859] »

O'Neill does know about -tf and -te. She used them on a Linux machine.
deltarho[1859]
Posts: 4292
Joined: Jan 02, 2017 0:34
Location: UK
Contact:

Re: FreeBASIC's PRNG #2

Post by deltarho[1859] »

Eureka! Found -tf and -te in RNG_test.cpp. I used FileLocator Pro to do a text search of PractRand's full distribution folder.

The default test set options are '-tf 1' and '-te 0'

-tf FOLDING FOLDING may be 0, 1, or 2. 0 means that the base tests are
run on only the raw test data. 1 means that the base tests
are run on the raw test data and also on a simple transform
that emphasizes the lowest bits. 2 means that the base tests
are run on a wider variety of transforms of the test data.

-te EXPANDED EXPANDED may be 0 or 1. 0 means that the base tests used are
the normal ones for PractRand, optimized for sensitivity per
time. 1 means that the expanded test set is used, optimized
for sensitivity per bit.
... and now additional value(s) are supported. Setting this
to 10 will use an systematically expanding Birthday Spacings
Test in place of a normal test set. This test is separate
because it uses too much memory to run concurrently with other
tests

I will not be using them. The default test set options are good enough for me. '-tf 1' is what brings LCGs down and Vigna's work over the past few years.

It follows then that MsWs is OK at the lowest bits.

Added: Also found this in RNG_test.cpp. We can get the 'full monty' by using 'Rng_test -help'
dodicat
Posts: 7976
Joined: Jan 10, 2006 20:30
Location: Scotland

Re: FreeBASIC's PRNG #2

Post by dodicat »

I decided to test these extra switches to 16 GB, I'll maybe let it run on later.(My own algo)
The initial message:
test set = expanded, folding = extra

cpu usage about 60%
Memory usage, nothing too far from normal running.

What I do notice is that compiling the pipefile with -O3 and not O3 produces a slight difference.
But the seed is the same in each case.
This is like riding a fancy multi geared bicycle one mile, and riding that old heap I have in the shed the same mile, but events en route are slightly different, or a mile has changed value.
Which I don't know.

Anyway I passed 16 gb with one unusual evaluation at 256 MB.
[Low1/64]FPF-14+6/16:all R= +6.3 p = 2.7e-5 unusual
Pot hole perhaps.
Anyway, as I said before, I'll let you guys carry on, I am fed up with PractRand now.
I don't see much sense in concentrating so much on some c++ testing app to be honest.
Make a freebasic test, now that would be the ticket.
deltarho[1859]
Posts: 4292
Joined: Jan 02, 2017 0:34
Location: UK
Contact:

Re: FreeBASIC's PRNG #2

Post by deltarho[1859] »

@dodicat

Did you write

Code: Select all

Function random2.valu() As Ulongint
   e = a-((b Shl 39) Or (b Shr 25))
   a = b xor ((c Shl 11) Or (c Shr 53))
    b = c + d
   c = d + e
   d = e + a
   Return d
End Function
dodicat wrote:Anyway, as I said before, I'll let you guys carry on, I am fed up with PractRand now.
You may well have saved your bacon because John von Neumann wrote
Anyone who considers arithmetical methods of producing random digits is, of course, in a state of sin.
dodicat
Posts: 7976
Joined: Jan 10, 2006 20:30
Location: Scotland

Re: FreeBASIC's PRNG #2

Post by dodicat »

deltarho[]
The answer to your question , about 50 50 for Me and the algorithm and the Web for the algorithm.
I have come to the conclusion that there are as many or more random number algorithms as there are random numbers.

I found that to pass many of the PractRand criteria a good old mix up is as important as a clever algo.
For instance

Code: Select all

 

Function random2.valu() As Ulongint
	e = a- ((b Shl 39) Or (b Shr 25))
	a = b xor c
    b = c + d
	c = d + e
	d = e + a
	Return d
End Function   
Gave me an unusual evaluation at 16 gigabytes and a suspicious evaluation at 256 gigabytes.
This algo is of course one rotate (popular in generators) and one xor (very popular in generators) and a good old mix up afterwards.
John von Neumann I see has many quirky quotes.
Nice.
deltarho[1859]
Posts: 4292
Joined: Jan 02, 2017 0:34
Location: UK
Contact:

Re: FreeBASIC's PRNG #2

Post by deltarho[1859] »

dodicat wrote:I found that to pass many of the PractRand criteria a good old mix up is as important as a clever algo.
I agree.

Way back in 1991 George Marsaglia introduced add-with-carry and subtract-with-borrow before his multiply-with-carry. In those days he and his like used to write mathematical papers. Since then folk have got pretty good at analyzing generators greatly aided by computers and their increasing power this century. In Marsaglia'a earlier days tests on generators involved analyzing 10/20MB of data and here we are today analyzing TBs of data on desktop computers.

There are no mathematics at Melissa O'Neil's website or Sebastian Vigna's website. There is no mathematics at Bernard Widynski's website. What we have is some folk who have the understanding to allow them to come up with a clever algorithm but the mathematics has been dispensed with. It is easier to simply present the algorithm to a computer which in turn uses algorithms to look for weaknesses. These checking algorithms have become more sophisticated over the years. Mersenne Twister passed PractRand V0.92 and earlier and it was V0.93 which spotted a weakness resulting in a PractRand failure if we can call taking 256GB of data for the weakness to manifest itself as a failure.
Gave me an unusual evaluation at 16 gigabytes and a suspicious evaluation at 256 gigabytes.
So, that is one question answered. The next question is how fast is it?

On speed, some folk keep asking for faster and faster generators thinking that their applications will benefit from the fastest they can get their hands on. What many of them do not realize is that in a 'real world' environment the law of diminishing returns applies. So, doubling the speed of a generator will not give a doubling of speed of our code. In my code which compares generators given a task to complete for a given time, I have introduced a generator called Infinity. Instead of generating random numbers it reads constants as if it was generating random numbers at an infinite speed.

Here is a typical output of my comparison code.

Code: Select all

5              1.32
1            425.27
3            440.31
CMWC4096     463.02
4            472.75
CryptoRndII  474.13
2            484.07
RndMT        606.56
MsWs         779.99
Knuth64      874.49
PCG32II      874.52
Infinity     876.49
PCG32II is twice as fast as FB's #3. With tight loop code churning out random numbers and nothing else PCG32II is very much faster than FB's #3.

If I was able to tweak PCG32II to make it, say, twice as fast that would not be reflected above as PCG32II is only 0.22% slower than Infinity.

If I wanted more work to be done then looking at PCG32II is not the answer. The answer lies in looking at my computer.

O'Neill has some pcgs which are faster than pcg32 but all they would do is squeeze between PCG32II and Infinity. If she charged for the faster generators I would not be opening my wallet would I?
dodicat
Posts: 7976
Joined: Jan 10, 2006 20:30
Location: Scotland

Re: FreeBASIC's PRNG #2

Post by dodicat »

fb's #3 has two loops to fill
'

Code: Select all

if ( p >= state(0) + MAX_STATE ) then
      /' generate another array of 624 numbers '/
      for i = 0 to MAX_STATE - PERIOD
         v = ( state(i) and &h80000000 ) or ( state(i + 1) and &h7FFFFFFF )
         state(i) = state(i + PERIOD) xor ( v shr 1 ) xor xor_mask(v and &h1)
      next
      
      for j as long =i to MAX_STATE - 1
         v = ( state(i) and &h80000000 ) or ( state(i + 1) and &h7FFFFFFF )
         state(i) = state(i + PERIOD - MAX_STATE) xor ( v shr 1 ) xor xor_mask(v and &h1)
      next  
So hardly surprising it is slow.

But I'll probably continue to use it or 2.
I'll give 5 a miss.
4 or rand from c runtime would be OK for short numbers/singles I suppose.
Anyway, you are interested in crypt stuff.
I think crypt safe(ish) algorithms would probably need some sort of store array as in #3, but I am certainly not knowledgeable in any of that, thus my half-hearted attempts in this thread.
deltarho[1859]
Posts: 4292
Joined: Jan 02, 2017 0:34
Location: UK
Contact:

Re: FreeBASIC's PRNG #2

Post by deltarho[1859] »

dodicat wrote:So hardly surprising it is slow.
That is why I changed the BASIC engine to asm resulting in RndMT being faster than FB #3.
I'll give 5 a miss.
It has its uses. In PCG32II's MyRandomize the first statement is 'Randomize , 5' prior to calling Get64Bit. On Windows FB #5 uses CryptGenRandom which produces better quality random numbers than any PRNG.

Code: Select all

Function Get64Bit() As UlongInt
  Return (Cast( Ulongint, Rnd*(2^32) ) Shl 32) Or Cast( Ulongint, Rnd*(2^32) )
End Function
FB #5 is incredibly slow, see the table above, but Get64Bit only wants two random numbers and completes in only 10ms.

In cryptographic work we have to use a CPRNG but, generally, we don't need shed loads of random numbers which is just as well. RSA can use a fair number and we know how fast that is. <smile>
4 or rand from c runtime would be OK for short numbers/singles I suppose.
For a small number of requests, speed would not be an issue and it would not be possible to prove that the quality was not up to scratch.
I think crypt safe(ish) algorithms would probably need some sort of store array as in #3
The only problem with that is the longer they are in store the more vulnerable they are. I used to describe CryptoRndII, which uses buffers, cryptographic but I had to downgrade that after reading 'Serious Cryptography: A Practical Introduction to Modern Encryption' by Jean-Philippe Aumasson.

Added: "thus my half-hearted attempts in this thread." You don't do half-hearted attempts.
dafhi
Posts: 1640
Joined: Jun 04, 2005 9:51

Re: FreeBASIC's PRNG #2

Post by dafhi »

finally got practRand working. Did a Windows restore and installed vc redist 2013. my new generator works well.
dodicat
Posts: 7976
Joined: Jan 10, 2006 20:30
Location: Scotland

Re: FreeBASIC's PRNG #2

Post by dodicat »

Hi dafhi.
I tested the range by mod (0 to ulong) range.
Here is the code
range.bas

Code: Select all


'any ulongint generator
'Use this one here
type Rand
   a as ulongint
   b as ulongint
   c as ulongint
   d as ulongint
end type

function ranulong(x as rand) as ulongint
   dim e as ulongint = x.a - ((x.b shl 7) or (x.b shr (64 - 7)))
   x.a = x.b xor ((x.c shl 13) or (x.c shr (64 - 13)))
   x.b = x.c + ((x.d shl 37) or (x.d shr (64 - 37)))
   x.c = x.d + e
   x.d = e + x.a
   return x.d
end function

'function randouble(x as rand) as double ''NOT NEEDED
    'return ranulong(x)/18446744073709551615ull
   ' end function

 sub init(x as rand, byval seed as ulongint=100)
   dim i as ulongint
    x=type(4058668781,seed,seed,seed)
    for i as ulongint=1 to 20
        ranulong(x)
        next
end sub

'=========
dim shared as rand z
init(z)
'========


function range(f as longint,l as longint) as longint
    return (ranulong(z) mod ((l-f)+1)) + f
end function



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
    *SPtr = range(0,4294967295)
    SPtr += 1
  Next
  print S;
  SPtr = BasePtr
Loop
   
My generataor is slower than deltarho's of course.
I compiled with 64 bit -O3 optimisation.
I work within the pract-rand executable folder directly with a start_shell.
The computation time is slower than direct random (has to call the range function and the ranulong function.)
Here are some results to 128 gigabytes

Code: Select all

 Microsoft Windows [Version 10.0.17134.345]
(c) 2018 Microsoft Corporation. All rights reserved.

C:\Users\User\Desktop\bin\random\PractRand_0.94\PractRand_094\bin\msvc12_64bit>range.exe | rng_test stdin32 -multithread
ed
RNG_test using PractRand version 0.94
RNG = RNG_stdin32, seed = unknown
test set = core, folding = standard (32 bit)

rng=RNG_stdin32, seed=unknown
length= 256 megabytes (2^28 bytes), time= 3.2 seconds
  no anomalies in 165 test result(s)

rng=RNG_stdin32, seed=unknown
length= 512 megabytes (2^29 bytes), time= 6.6 seconds
  no anomalies in 178 test result(s)

rng=RNG_stdin32, seed=unknown
length= 1 gigabyte (2^30 bytes), time= 12.7 seconds
  no anomalies in 192 test result(s)

rng=RNG_stdin32, seed=unknown
length= 2 gigabytes (2^31 bytes), time= 24.0 seconds
  no anomalies in 204 test result(s)

rng=RNG_stdin32, seed=unknown
length= 4 gigabytes (2^32 bytes), time= 45.7 seconds
  no anomalies in 216 test result(s)

rng=RNG_stdin32, seed=unknown
length= 8 gigabytes (2^33 bytes), time= 90.6 seconds
  no anomalies in 229 test result(s)

rng=RNG_stdin32, seed=unknown
length= 16 gigabytes (2^34 bytes), time= 178 seconds
  no anomalies in 240 test result(s)

rng=RNG_stdin32, seed=unknown
length= 32 gigabytes (2^35 bytes), time= 371 seconds
  no anomalies in 251 test result(s)

rng=RNG_stdin32, seed=unknown
length= 64 gigabytes (2^36 bytes), time= 876 seconds
  Test Name                         Raw       Processed     Evaluation
  [Low1/32]Gap-16:B                 R=  +4.4  p =  1.0e-3   unusual
  ...and 262 test result(s) without anomalies

rng=RNG_stdin32, seed=unknown
length= 128 gigabytes (2^37 bytes), time= 1903 seconds
  no anomalies in 273 test result(s)

  
deltarho
I think you should get back here.
The forum's best programmer (IMO), D.J.Peters had a similar hiccup a while back.
dafhi
Posts: 1640
Joined: Jun 04, 2005 9:51

Re: FreeBASIC's PRNG #2

Post by dafhi »

the range thing. with a 64 bit state i guess the bias is ike a needle in a haystack. for a speedy range, you've found a highly unexpected (since mod relates with division) optimization

[update] haven't debugged yet with yours (have 2 tests running)

Code: Select all

Dim Shared As Ulongint x = 12, w = 0
Dim As String cmd = "RNG_test stdin32 -multithreaded"
Dim As Long fileHandle = Freefile()
Dim Shared S As String * 1048576
Dim As Ulong Ptr SPtr, BasePtr
Dim As Long j


type Rand       ' https://www.freebasic.net/forum/viewtopic.php?f=3&t=26996&start=255#p254251
   as ulongint a,b,c,d
end type

function ranulong(x as rand) as ulongint
   dim e as ulongint = x.a - ((x.b shl 7) or (x.b shr (64 - 7)))
   x.a = x.b xor ((x.c shl 13) or (x.c shr (64 - 13)))
   x.b = x.c + ((x.d shl 37) or (x.d shr (64 - 37)))
   x.c = x.d + e
   x.d = e + x.a
   return x.d
end function
 
 sub init(x as rand, byval seed as ulongint=100)
   dim i as ulongint
    x=type(4058668781,seed,seed,seed)
    for i as ulongint=1 to 20
        ranulong(x)
        next
end sub
dim shared as ulongint e
dim shared as rand z
init(z)
x=z.d


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

Open pipe cmd For Binary Access Write As fileHandle
Do
  For j = 1 To 262144
    
    #if 1
     const add = 1, Seed = 0, mul = 35
     w += add
     x *= mul
     x xor= x shr 8
     x xor= w
     'w -= (x = Seed) '' optional
    #elseif 0 
     e = z.a - ((z.b shl 7) or (z.b shr (64 - 7)))
     z.a = z.b xor ((z.c shl 13) or (z.c shr (64 - 13)))
     z.b = z.c + ((x shl 37) or (x shr (64 - 37)))
     z.c = x + e
     x = e + z.a
    #else   ' Middle Square Weyl Sequence
     x *= x
     w += &H5851F42D4C957F2D ' 64-bit prime as used by PCG32II
     x += w
     x = ( x Shr 32 ) Or ( x Shl 32 )
    #endif
    
    *SPtr = x
    SPtr += 1
  Next
  Print #fileHandle, S;
  if rnd < .2 then sleep 1
  SPtr = BasePtr
Loop
Close( fileHandle )
[update] "suspicioius" at 1T on my RNG.
[update] breezes through 16T w/ different constants (2018 Nov 10)
Post Reply