RandomBit() or how to get random yes or no behavior.

[Demivec]

"The decrease in framerate is due to the lines getting longer, they're drawn each frame."

So then even this is not random because you can predict the outcome. You know the lines are going to get longer and you know they are going to be drawn every frame.

I knew you'd say that.

[Rescator]

I managed to improve the speed of Demivec's code a little, there's still some things that can be doe to speed thing up even more.

One idea I had but too lazy to try was to draw or rather put the data into a bitmap and copy that to the screen, should be much faster than drawing each line to the screen.

Other than that, the loop itself can still be improved some more.

In any case, there are 3 different RNG's here,
just uncomment the one you wish to test and comment the others)

All 3 in this source perform pretty similar speedwise, the spread (balance of 1's and 0's) are also pretty similar.

One of the RNG's is the Pureasic Random()
The other is a very crude Multiply With Carry I made, MWC is the basis for many RNG's out there.
The third is PureBasic's CRC32FingerPrint() a "trick" someone on the net mentioned using a lot, the result might surprise you.

All 3 are seeded using RandomSource() which basically fetches the TSC of the cpu, but you can really use anything here as well, you could use a fixed value and the sequence should be the same each time, or you could use QueryPerformanceCounter or the system time or some other source as seed.

I the test only the LSB of the random number is used, this makes the test easier, but obviously there is no way to "see" if the balance of 1's and 0's are the same higher up.
But as per the original post I made in this thread, the whole focus is on random "coin toss" behavior.

If anyone has other RNG's they'd like to share please do so,
just make sure the speed is similar to these three.

Note! None of these are really suitable for cryptography, but for games, misc apps, AI and simple simulation (I wonder what The Sims are using?)
these should be "ok".

If you want crypto level RNG's ten look at the Windows Crypt API which has a insane RNG that uses TSC + pretty much every any other damn thing that produces a unpredictable number in Windows/hardware/user etc. as it's seed, it's a huge list of sources it has.

Anyway, have fun with testing these 3 RNG's.

Code: Select all

EnableExplicit
DisableDebugger
Define.l sWidth,sHeight,sDepth,sRefresh
ExamineDesktops()
sWidth = DesktopWidth(0)
sHeight = DesktopHeight(0)
sDepth = DesktopDepth(0)
sRefresh = DesktopFrequency(0)

Procedure.i RandomSource()
 !RDTSC ;Read the CPU Time Stamp Counter
 ProcedureReturn ;Return the EAX register content, (32bit)
EndProcedure ;we're not using the upper half (EDX) as that hardly changes at all.

Structure ran_seed_struct
 seed.l
 carry.l
EndStructure
Define ran_seed.ran_seed_struct, random.l
random.l=RandomSource() ;for CRC32
RandomSeed(random) ;for Random()
ran_seed\seed=random ;for MWC()

Procedure.l MWC(*seed)
 !mov ecx,dword[p.p_seed]
 !mov eax,dword[ecx]
 !mov edx,3373259949
 !mul edx
 !add eax,[ecx+4]
 !adc edx,0
 !mov dword[ecx],eax
 !mov dword[ecx+4],edx
 ProcedureReturn
EndProcedure

InitSprite()
InitKeyboard()
SetRefreshRate(sRefresh)
OpenScreen( sWidth, sHeight, sDepth, "RandomDemo3" )
Dim vert.l(sWidth - 1)

#TextColor=$FF8000
Dim color.l(8)
color(0)=RGB(255,0,128)
color(1)=RGB(128,255,0)
color(2)=RGB(0,128,255)
color(3)=RGB(0,255,128)
color(4)=RGB(192,64,64)
color(5)=RGB(192,64,192)
color(6)=RGB(64,192,192)
color(7)=RGB(64,64,192)
color(8)=RGB(0,128,255)

timeBeginPeriod_(1)
Define last.l,time.l,fps.i,lastfps$,oldfps.i,rnd.i,total.q,zeroes.q,ones.q,now.l,n.l,r.l,length.l
last=timeGetTime_()
now=last
Repeat
  now=timeGetTime_()
  ExamineKeyboard()
  For n = 0 To sWidth - 1
   ;start of RNG's, uncomment the one you want to test, and comment the others out.
;   r = Random(-1)&%1 ;PureBasic's RNG
;   random=CRC32Fingerprint(@random,4) : r=random&%1 ;CRC32 RNG
   r=MWC(ran_seed)&%1 ;Multiply With Carry RNG
   ;end of RNG's
   rnd+1
   If r
    vert(n)+1
    ones+1
   Else
    vert(n)-1
    zeroes+1
   EndIf
  Next
  StartDrawing(ScreenOutput())
    Box(0,0,sWidth,sHeight,0)
    If (now-last)>999
     last=now
     total+rnd
     lastfps$=Str(fps)+" Frames/s, "+Str(rnd)+" RND/s, Total "+Str(total)+" RND, Spread "+StrD((zeroes/ones)*100.0)+" ("+Str(ones-zeroes)+")"
     fps=0
     rnd=0
    EndIf
    DrawText(0,0,lastfps$,$FFFFFF,$0)
    For n = 0 To sWidth - 1
      length = Abs(vert(n)) / (sWidth / 16)
      If length>8 Or length<0
       length=8
      EndIf
      Line(n, sHeight/2 - 1, 0, -vert(n),color(length))
    Next
  StopDrawing()
  Delay(0)
  FlipBuffers(#PB_Screen_NoSynchronization)
  fps+1
Until KeyboardPushed(#PB_Key_Escape)
timeEndPeriod_(1)

EDIT: Fixed some spelling.

[Rescator]

Two more RNG's have been added.

So now there is: PuureBasic's Random(), CRC32, MWC (Multiply With Carry), LCG (Linear Congruential Generator), XS (XOR/Shift Generator)

My personal favorite is the LCG, not for it being better than any of the others but simply due to how darn simple it is. That it also has one of the better spreads also helps obviously

I'm a bit shaky on the asm stuff, especially when it's paraphrased from C etc.
I used asm on some of these (besides speed) to avoid extra clutter to do unsigned math.

I may have screwed things up (hope not) but in any case I based the code on the examples found here: http://hmtown.com/random.htm

PS! The way I did the XS means it's not thread safe, LCG and WC and CRC32 as well Iassume should be threadsafe (hence why you pass the seed to it at each run, my advice is separate seeds per thread), not sure about Random(). By threadsafe I mean that one thread will not interfere with eachother's seed/sequence if both are using the same RNG routine.

Enjoy more number stuff folks This is starting to become quite a nice "library" of RNG's geared particularly towards coin tosses.

Fun things to try: Uncomment more than one, or even all for a chain effect of RNG's

Code: Select all

EnableExplicit
;DisableDebugger
Define.l sWidth,sHeight,sDepth,sRefresh
ExamineDesktops()
sWidth = DesktopWidth(0)
sHeight = DesktopHeight(0)
sDepth = DesktopDepth(0)
sRefresh = DesktopFrequency(0)

Procedure.i RandomSource()
 !RDTSC ;Read the CPU Time Stamp Counter
 ProcedureReturn ;Return the EAX register content, (32bit)
EndProcedure ;we're not using the upper half (EDX) as that hardly changes at all.

Structure ran_seed_struct
 seed.l
 carry.l
EndStructure
Define ran_seed.ran_seed_struct, random.l
random.l=RandomSource() ;for CRC32 and LCG, XS
RandomSeed(random) ;for Random()
ran_seed\seed=random ;for MWC()

Procedure.l MWC(*seed)
 !mov ecx,dword[p.p_seed]
 !mov eax,dword[ecx]
 !mov edx,3373259949
 !mul edx
 !add eax,[ecx+4]
 !adc edx,0
 !mov dword[ecx],eax
 !mov dword[ecx+4],edx
 ProcedureReturn
EndProcedure

Procedure.l LCG(seed)
 !mov eax,dword[p.v_seed]
 !mov edx,1664525
 !mul edx
 !add eax,7
 ProcedureReturn
EndProcedure

Procedure.l XS(*x.Long)
 Static y.l,z.l,w.l
 Protected temp.l
 temp = *x\l ! (*x\l << 15)
 *x\l = y
 y = z
 z = w
 w = w ! (w >> 21) ! temp ! (temp >> 4)
 ProcedureReturn w
EndProcedure

InitSprite()
InitKeyboard()
SetRefreshRate(sRefresh)
OpenScreen( sWidth, sHeight, sDepth, "RandomDemo4" )
Dim vert.l(sWidth - 1)

#TextColor=$FF8000
Dim color.l(8)
color(0)=RGB(255,0,128)
color(1)=RGB(128,255,0)
color(2)=RGB(0,128,255)
color(3)=RGB(0,255,128)
color(4)=RGB(192,64,64)
color(5)=RGB(192,64,192)
color(6)=RGB(64,192,192)
color(7)=RGB(64,64,192)
color(8)=RGB(0,128,255)

timeBeginPeriod_(1)
Define last.l,time.l,fps.i,lastfps$,oldfps.i,rnd.i,total.q,zeroes.q,ones.q,now.l,n.l,r.l,length.l
last=timeGetTime_()
now=last
Repeat
  now=timeGetTime_()
  ExamineKeyboard()
  For n = 0 To sWidth - 1
   ;start of RNG's, uncomment the one you want to test, and comment the others out.
;   r = Random(-1)&%1 ;PureBasic's RNG
;   random=CRC32Fingerprint(@random,4) : r=random&%1 ;CRC32 RNG
;   r=MWC(ran_seed)&%1 ;Multiply With Carry RNG
   random=LCG(random) : r=(random>>31)&%1 ;LCG RNG
;   r=xs(@random)&%1 ;XOR/Shift RNG
   ;end of RNG's
   rnd+1
   If r
    vert(n)+1
    ones+1
   Else
    vert(n)-1
    zeroes+1
   EndIf
  Next
  StartDrawing(ScreenOutput())
    Box(0,0,sWidth,sHeight,0)
    If (now-last)>999
     last=now
     total+rnd
     lastfps$=Str(fps)+" Frames/s, "+Str(rnd)+" RND/s, Total "+Str(total)+" RND, Spread "+StrD((zeroes/ones)*100.0)+" ("+Str(ones-zeroes)+")"
     fps=0
     rnd=0
    EndIf
    DrawText(0,0,lastfps$,$FFFFFF,$0)
    For n = 0 To sWidth - 1
      length = Abs(vert(n)) / (sWidth / 16)
      If length>8 Or length<0
       length=8
      EndIf
      Line(n, sHeight/2 - 1, 0, -vert(n),color(length))
    Next
  StopDrawing()
  Delay(0)
  FlipBuffers(#PB_Screen_NoSynchronization)
  fps+1
Until KeyboardPushed(#PB_Key_Escape)
timeEndPeriod_(1)

[Rescator]

I just had to share this one. It's a perfect truly random uniform number generator.

Unfortunately it's useless for pretty much anything beyond coin toss and yes/no situations.

Code: Select all

Procedure.l LCG2(*seed.Long)
 Static bias.l
 Protected bit.l,random.l
 random=*seed\l
 !mov eax,dword[p.v_random]
 !mov edx,1664525
 !mul edx
 !add eax,7
 !mov dword[p.v_random],eax
 *seed\l=random
 bit=(random>>31)&%1
 If bit
  bias+1
 Else
  bias-1
 EndIf
 If bias>1
  bit=0
  bias-2
 ElseIf bias<-1
  bit=1
  bias+2
 EndIf
 ProcedureReturn bit
EndProcedure

To use it with the test source in the post above,
add this line among the others:

Code: Select all

   r=LCG2(@random) ;LCG2 RNG

Now run the test, do you see something interesting?
It looks pretty much like some other the others right?
How is that possible? Isn't my LCG2() perfectly uniform?

Yup! It is, just try a loop like this:

Code: Select all

Define random.l,r.l
For i=1 To 100
 r=LCG2(@random)
 Debug r
Next

Count the number of 1's and 0's.
50 each, precisely.

So why is the fancy graphics behaving like that?

Well! Despite being perfectly uniform, it's still random.
As soon as the bias goes above 2 it snaps back by returning the opposite of what it really is.

This means you get sequences like, 0,1,0,1 but also 0,0,1,1 or 0,1,1,0,0,1,0,1,1.
There is no way of knowing when singles our doubles may appear.
The only thing you do know is that there is never more than maximum two same bits in a sequence.

This is as close to perfectly fair as you can get for a "coin toss", as 0,1,0,1,0,1,0,1 forever..... while truly perfectly fair, isn't exactly random now is it?
What I've done with LCG2() is to do it the only way it can be done if you want fair but random coin toss.

There is no way to "game" the computer, as player A and player B wile having a fair chance of getting even sides, there is still the element of natural randomness. It is quite possible that one player get almost always tales, while the other only gets a mix of both.

There should be no flaw in LCG2(), because even when the RNG starts to repeat it's internal cycle, thanks to the bias check, there is no way to distinguish such an eve from any other results.

PS! It "is" possible to check for bias for larger numbers, but only single bits like this can easily be checked.
The only way to improve LCG2() further is to optimize it properly and maybe do it all in asm.

[rsts]

I must be missing something, but it seems to me anytime I see 00 I know the next will be 1 and anytime i see 11 I know the next will be 0.

With a coin toss shouldn't I be able to get HHHHH or TTTHHH?

[Rescator]

Adjust the bias if you want that.

But the point is, player A would toss the coin, then player B would toss the coin. None of the players would toss the coin multiple times in a row.
The number of players can vary too for example.

EDIT: Likewise with an AI doing a yes/no choice, just like the coin toss an AI would not do a bunch of yes/no choices in a row, alternating between AI's is better.

Also, at some regular or random (pardon the pun) interval reseeding might be nice to do.

[freak]

> It's a perfect truly random uniform number generator.

You are again using very strong words without any solid proof. I would be more careful with that


About the CRC32 number generation:
One important property of PRNG's is the length of the cycles they produce. Since they are all based on a finite-sized state, every PRNG at some point reaches a state it reached before, and from this point on, all outputed numbers will be the same as in the last "loop". How big these loops are gets important when you use the generator for much data, and generally a generator with bigger loops is though to be better.

Long story short: The CRC32 generator has only the 32bit output as state, so as soon as it outputs a number it reached before, you have entered a loop. Note that this is probably much less then 2^32-1 steps because it is unlikely that you can get that many different outputs with a method like that. This is the reasons why generators such as the LCG's usually come with very specific parameters because they where shown to produce the largest loops. With other parameters you get much shorter loops.

Would be intresting to compare the loop length of the methods you have shown here, although i am not going to try that because it will take quite a while to test that if the methods are not entirely bad

btw, PB Random() uses a larger circular buffer as state data, so even when it outputs a number twice it has not reached a loop yet.

[Rescator]

I like big words. Hehe!

Oh btw!

A tip: If you use Random() with the unsigned maximum for an integer type (so $FFFFFFFF on x86, $FFFFFFFFFFFFFFFF on x64) then even this multiplication step is skipped and you get plain 32 or 64 pseudo-random bits which actually gives you better statistical properties than using another maximum.

On PB 4.31 x64:
Debug Random($FFFFFFFFFFFFFFFF)
Always returns zero.
Debug Random($FFFFFFFFFFFFFFFE)
works however.
Is there no way to make $FFFFFFFFFFFFFFFF (aka -1) work on x64 as well?