## A party trick for random number generators.

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

### Re: A party trick for random number generators.

@dodicat

Here is a 'proper' 16-bit generator.

Return y=(y......
and it should have been
y=(y......
Return y

It was a translation from some C code where my mistake is allowed.

FB code:

Code: Select all

``````function rand as ushort
static x as ushort = 12
static y as ushort = 34
dim as ushort t=(x xor (x shl 5))
x=y
y=(y xor (y shr 1)) xor (t xor (t shr 3))
return y
end function``````

x and y are the seeds - so a 32-bit internal state.

Anyway, the average over 2^16 should be 2^15. I got 3.5 significant figures. Not brilliant but, hey, we are talking 16-bit.

By 'proper' I mean the generated numbers are anyone's guess.

What I got was expected:

We get a repetition at 2^15.688032; just shy of the 'saturation point' at 2^16. I tested for rand and not [0,1).
dodicat
Posts: 8043
Joined: Jan 10, 2006 20:30
Location: Scotland

### Re: A party trick for random number generators.

a repeat at 2^15.688032 means the distribution is not clean at 2^16.
My distribution is pure, guaranteed no repeats in the range.
Here it is again with seeding available.

Code: Select all

``````
#cmdline "-gen gcc -Wc -O2"
screenres 1024,768,32

namespace array
#define irange(f,l) ((rand() mod (((l)-(f))+(1))) + (f))
#define frand rand/65536
dim  as ushort a(65535)
Sub shuffle(a() As ushort)
#define range(f,l) Int(Rnd*((l+1)-(f))+(f))
For n As Long = Lbound(a) To Ubound(a)-2
Swap a(n), a(range((n+1),Ubound(a)))
Next n
End Sub

sub start constructor
for n as long=0 to ubound(array.a)
a(n)=n
next
shuffle(array.a())
end sub

end namespace

function rand(flag as long=0)  as ushort
static as long s
if flag<>0 then s=flag
function= array.a(s)
s+=1
if s>65535  then s=0
end function

sub seed(m as long)
randomize m
array.start
rand(m)
end sub

#define bits16   '<-------------

dim as string i
dim as long start=100
var t=timer
do
#ifdef bits16
seed start
#endif
for x as long=0 to start

#ifdef bits16
var x=irange(0,1025)
var y=irange(0,768)
#else
var x= rnd*1024
var y= rnd*768
#endif
var r=x\4 ,g=y\3 ,b=abs(x-y)/y
pset (x,y),rgb(r,g,b)
next
start+=100
i=inkey
loop until i=chr(27) or start>50000
print "done in ";timer-t
sleep

``````
You can think of it as a transform from as 32 bit random with repeats (fb Mersenne twister) to a 16 bit random with no repeats.
deltarho[1859]
Posts: 4430
Joined: Jan 02, 2017 0:34
Location: UK
Contact:

### Re: A party trick for random number generators.

dodicat wrote:a repeat at 2^15.688032 means the distribution is not clean at 2^16.
Agreed.
My distribution is pure, guaranteed no repeats in the range.
Agreed.

To generate 10 * [0,1) I think that we can use:

Code: Select all

``````seed(12345) ' or whatever
for i as ulong = 1 to 10
print array.a(i)/2^16
next
``````
You can think of it as a transform from as 32 bit random with repeats (fb Mersenne twister) to a 16 bit random with no repeats.
Agreed.

I am now buying into it.

However, it's Achilles heel: “For ulong the array is way too big, so the shuffle method would not work.” Pity
deltarho[1859]
Posts: 4430
Joined: Jan 02, 2017 0:34
Location: UK
Contact:

### Re: A party trick for random number generators.

@dodicat

In the post here I rattled on about shuffling.

I mention a deck of cards which has 52! possible permutations. There isn't a generator on the planet which can cover them. Mersenne Twister (MT) with its massive period can only cover a list of 2,080 items. See at the bottom of this Wikipedia entry: Fisher–Yates shuffle That article fails to mention a cryptographic generator for giant lists.

With your Ushort code, we have a list of 65536! items; that is 5.16 * 10^287193. I think that is the largest number that I have ever seen on the internet.

2080/65536! is vanishingly small.

CryptoRndII will cover all, 65536! permutations and is about six times faster than MT.

Your latest Ushort code works fine.

However when I use #include "I:\FreeBASIC\RNDGenerators\CryptoRndII.bas" compilation fails with:

'Return type here does not match DECARE prototype in rand(flagas long=0) as ushort.

I only added the #include - nothing else.

I have been using CryptoRndII for years - and 'rand' is not used.

Now you may be happy with 2,080 permutations by using MT, but there are an unbelievable number which are not being covered. Even my CMWC4096 will only cover 10,940 items. You may be happier with that, but that needs an #include so we may as well #include CyptoRndII and be done with it.

What say you?

In your original code you did not use Namespace, but you do in your latest code. Why?
Last edited by deltarho[1859] on Jul 31, 2024 9:50, edited 1 time in total.
deltarho[1859]
Posts: 4430
Joined: Jan 02, 2017 0:34
Location: UK
Contact:

### Re: A party trick for random number generators.

In fact, the compiler will not let me #include any source code at the head.
dodicat
Posts: 8043
Joined: Jan 10, 2006 20:30
Location: Scotland

### Re: A party trick for random number generators.

deltarho[]
I used namespace to hide the array and shuffle and start which are private to rand.
(A bit like private bits of OOP)
rand will conflict with crt.bi, (also windows.bi), they both use it. I have changed all rand to rnd16 here and it is OK.
deltarho[1859]
Posts: 4430
Joined: Jan 02, 2017 0:34
Location: UK
Contact:

### Re: A party trick for random number generators.

Thank you.

I got a successful compilation, but something was wrong. I am rewriting the Shuffle procedure to use CryptoRndII. A console opened and swiftly crashed. So I used -exx and, boy, did I get some errors.

So I retuned to your Shuffle and left -exx on and, boy, did I get some errors.

Run your code using -exx. You are getting away with it, but I am not.
srvaldez
Posts: 3451
Joined: Sep 25, 2005 21:54

### Re: A party trick for random number generators.

@deltarho[1859]
would post a link to the code in question?
as it is, I am lost as to what code you and dodicat are talking about, is it the code 6 posts above this one by dodicat ?
@dodicat
I find your use of namespace and constructor in your post above obfuscating and confusing rather than useful, namespace and constructors are useful if it simplifies the program logic and makes it easier to understand
deltarho[1859]
Posts: 4430
Joined: Jan 02, 2017 0:34
Location: UK
Contact:

### Re: A party trick for random number generators.

@srvaldez

Yes
srvaldez
Posts: 3451
Joined: Sep 25, 2005 21:54

### Re: A party trick for random number generators.

well, I compiled that code with -exx and it runs fine without any issues
deltarho[1859]
Posts: 4430
Joined: Jan 02, 2017 0:34
Location: UK
Contact:

### Re: A party trick for random number generators.

I went out for some fresh air.

This is what I get with fbc 1.10.1/gcc32 9.3.0, #cmdline "-exx -gen gcc -Wc -O2"

Code: Select all

``````lfb -lfbgfx -lgdi32 -lwinmm -lgcc -lmsvcrt -lkernel32 -luser32 -lmingw32 -lmingwex -lmoldname -lgcc_eh "-)" "I:\WinFBE_Suite\Toolchains\FreeBASIC-1.10.1-winlibs-gcc-9.3.0\lib\win64\crtend.o"
I:\WinFBE_Suite\Toolchains\FreeBASIC-1.10.1-winlibs-gcc-9.3.0\bin\win64\ld.exe: I:\FreeBASIC\RNDGenerators\SixteenBitDodicat.o:fake:(.text+0xab): undefined reference to `fb_ArrayDimensionChk'
I:\WinFBE_Suite\Toolchains\FreeBASIC-1.10.1-winlibs-gcc-9.3.0\bin\win64\ld.exe: I:\FreeBASIC\RNDGenerators\SixteenBitDodicat.o:fake:(.text+0x173): undefined reference to `fb_ArrayBoundChkEx'
I:\WinFBE_Suite\Toolchains\FreeBASIC-1.10.1-winlibs-gcc-9.3.0\bin\win64\ld.exe: I:\FreeBASIC\RNDGenerators\SixteenBitDodicat.o:fake:(.text+0x19e): undefined reference to `fb_ArrayDimensionChk'
I:\WinFBE_Suite\Toolchains\FreeBASIC-1.10.1-winlibs-gcc-9.3.0\bin\win64\ld.exe: I:\FreeBASIC\RNDGenerators\SixteenBitDodicat.o:fake:(.text+0x1c7): undefined reference to `fb_ArrayBoundChkEx'
I:\WinFBE_Suite\Toolchains\FreeBASIC-1.10.1-winlibs-gcc-9.3.0\bin\win64\ld.exe: I:\FreeBASIC\RNDGenerators\SixteenBitDodicat.o:fake:(.text+0x1f3): undefined reference to `fb_ArrayDimensionChk'
I:\WinFBE_Suite\Toolchains\FreeBASIC-1.10.1-winlibs-gcc-9.3.0\bin\win64\ld.exe: I:\FreeBASIC\RNDGenerators\SixteenBitDodicat.o:fake:(.text+0x218): undefined reference to `fb_ArrayBoundChkEx'
I:\WinFBE_Suite\Toolchains\FreeBASIC-1.10.1-winlibs-gcc-9.3.0\bin\win64\ld.exe: I:\FreeBASIC\RNDGenerators\SixteenBitDodicat.o:fake:(.text+0x2dc): undefined reference to `fb_ArraySngBoundChkEx'
I:\WinFBE_Suite\Toolchains\FreeBASIC-1.10.1-winlibs-gcc-9.3.0\bin\win64\ld.exe: I:\FreeBASIC\RNDGenerators\SixteenBitDodicat.o:fake:(.text.startup+0x5f): undefined reference to `fb_ArraySngBoundChkEx'
linking failed: 'I:\WinFBE_Suite\Toolchains\FreeBASIC-1.10.1-winlibs-gcc-9.3.0\bin\win64\ld.exe' terminated with exit code 1
``````
Not a pretty sight.

fbc 1.10.1/gcc32 8.1.0 works fine
deltarho[1859]
Posts: 4430
Joined: Jan 02, 2017 0:34
Location: UK
Contact:

### Re: A party trick for random number generators.

I got a fresh copy of 9.3 - back in business.

Some source code came in with some corruption.

WinFBE.ini has been corrupted a few times of late.

The lot is on a Samsung T3 250GiB SSD which is getting on in years. However, CrystalDiskInfo reckons Good 92%. The metics look OK.

I have a younger T5 1TiB SSD where I put my system backups and FreeBASIC development folder backups. That is showing Good 96%.

My ancient C: drive is showing Good 96%. SSDife Pro reckons it has 6 years to go. I will have a new computer by then with, probably Win12.

There is a fair amount of free space on the T3 which is a pain because it is now going to get the chop.

I also have 1TiB internal hard drive with three partitions, so WinFBE_Suite and my FreeBASIC development folder will be getting a temporary new home.

I still have a problem with dodicat's code. Something is taking an exception to CryptoRndII. I wrote that some time ago, and it looks like an overhaul is due. Too much asm for a start.

Added: TheT3 is sobbing its heart out. Tough.
deltarho[1859]
Posts: 4430
Joined: Jan 02, 2017 0:34
Location: UK
Contact:

### Re: A party trick for random number generators.

This is at the head dodicat's code.

Code: Select all

``````#include "F:\FreeBASIC\CryptoRnd\CryptoRndII.bas"
InitializeCryptoBuffers(128*1024)
Print CryptoR(7,90)
Sleep ``````
CryptoR(7,90) does not get printed. The console opens, but after a second or so it closes.

I replaced CryptoRndII.bas with CryptoRndIIfxm.bas. That is fxm's alternative to Microsoft's threadpooling feature.

This time the console opened with a flashing cursor and remained like that.

I tested InitializeCryptoBuffers(128*1024) and it is being executed. I also tested the Function CryptoR and that is being executed.

So why does Print CryptoR(7,90) not get printed. Not getting CryptoR will make my Shuffle procedure to fail.

Obviously, we have a conflict somewhere, but fbc is not trapping it. It doesn't matter whether gas or gcc is used.

Talking of conflicts my hackles rose reading dodicat's comments earlier: “I used namespace to hide the array and shuffle and start which are private to rand”.

OK, but was there a real need?

I had to laugh with rand being in the open, so speak, getting its head being blown off by crt.bi or windows.bi.

I am now 'in the doldrums and don't know what to do next.

dodicat's code will greatly benefit from a working CryptoRndII or CryptoRndIIfxm as the permutations currently got don't give much randomness. The shuffling speed should also be significantly reduced.

Woe is me.
deltarho[1859]
Posts: 4430
Joined: Jan 02, 2017 0:34
Location: UK
Contact:

### Re: A party trick for random number generators.

srvaldez wrote:I find your [dodicat. editor] use of namespace and constructor in your post above obfuscating and confusing rather than useful, namespace and constructors are useful if it simplifies the program logic and makes it easier to understand
I now have dodicat's code working.

I simply removed the namespace and constructor.

I am sure that dodicat meant well, but I reckon some people use them to impress.

dodicat's MT shuffle took 2.045 ms whereas my Crypto shuffle took 1.579 ms; nearly30% faster. Further evidence that using a much faster generator does not mean that your application will go into orbit.

My reason for using Crypto was to give dodicat's generator access to all possible permutations.

I am now a happy sausage.
dodicat
Posts: 8043
Joined: Jan 10, 2006 20:30
Location: Scotland

### Re: A party trick for random number generators.

Constructor after a sub means it automatically runs without calling, but it can be called at any time.
I cannot call inside a namespace.
Namespace is hardly impressing anybody, but I like it here anyway.
I use fbide with absolutely no build options.
I can write options at the head of the code if required.
Does your ide/editor kick off setting build options?
Maybe that is a reason namespace/ constructor gives problems.
Here, again sorry, namespace, with the option of choosing your limit, line 10.
Please don't try 2^32-1 for obvious reasons.
It is a straight psetting random points, if you choose 2^16-1 then you will get 2^16-1 points only, no refreshing or re seeding.
The seed now doesn't include resetting and reshuffling the array, only a bare seed so you can repeat results.

Code: Select all

``````#cmdline "-gen gcc -Wc -O2"

screenres 1024,768,32
width 1024\8,768\16
dim as long xres,yres
screeninfo xres,yres

namespace array
const lim=2^24-1
#define irange(f,l) ((rndE() mod (((l)-(f))+(1))) + (f))
#define frndE rndE/(lim+1)
dim  as ulong a(lim)
Sub shuffle(a() As ulong)
#define range(f,l) Int(Rnd*((l+1)-(f))+(f))
For n As Long = Lbound(a) To Ubound(a)-2
Swap a(n), a(range((n+1),Ubound(a)))
Next n
End Sub

sub init constructor
for n as long=0 to ubound(a)
a(n)=n
next
shuffle(a())
end sub

end namespace

function rndE(flag as long=0)  as ulong
static as long s
if flag<>0 then s=flag
function= array.a(s)
s+=1
if s>array.lim  then s=0
end function

sub seed(m as long)
randomize m
rndE(m)
end sub

#define bits   '<-------------

var t=timer

#ifdef bits
seed timer
#else
randomize timer
#endif
for x as long=0 to 7000000

#ifdef bits
var x=irange(0,xres)
var y=irange(0,yres)
#else
var x= rnd*xres
var y= rnd*yres
#endif
var r=x\4 ,g=y\3 ,b=abs(x-y)/y
pset (x,y),rgb(r,g,b)
next

print "done in ";timer-t;" seconds"
sleep

``````