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

Share your advanced PureBasic knowledge/code with the community.
User avatar
Rescator
Addict
Addict
Posts: 1769
Joined: Sat Feb 19, 2005 5:05 pm
Location: Norway

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

Post by Rescator »

Public Domain.

Code: Select all

;I always wanted a random yes/no function,
;but Random() is a pseudo-random generator,
;and it has some overhead too.
;After contemplating using date/time, or high res timers,
;I remember the CPU Time Stamp Counter (TSC),
;which has a tendancy to be erratic, especially on modern systems,
;this is why Microsoft advice QueryPerformanceCounter for timings instead,
;but for hours use an unreliable high res CPU cycle counter is perfect.
EnableExplicit

Procedure.i RandomBit()
 !RDTSC ;Read the CPU Time Stamp Counter
 !AND EAX,$1 ;We only want the least significant bit as that changes the most.
 ProcedureReturn ;Return the EAX register content. (0 or 1 in this case)
EndProcedure
;An alternative would be using QueryPerformanceCounter,
;but using that has more overhead.
;Minimum CPU supported with the RDTSC call is original Pentium,
;and CPU's fully compatible to it, which includes pretty much
;every x86 CPU relased the last 10+ years.
;Works on x64 as well, although using 64bit register in that case "might" be faster than this.

Define.i o,z,r,i
DisableDebugger

For i=1 To 10000
 If RandomBit()
  o+1
 Else
  z+1
 EndIf
 Delay(1) ;Due to CPU caching we need to spread the calls apart,
 ;otherwise we end up with many calls in too close proximity
 ;possibly causing a bias towards 1 or 0.
 ;Even a delay of 0 ()task switch may be too tight,
 ;a delay of 1ms provides more consistent results,
 ;and is probably closer to real use as implemetend in games and applications.
Next

EnableDebugger
Debug o
Debug z

;You should get close to even numbers on average (50%/50%) in the above test,
;but you will also see abnormalies or even slight biases,
;the reason for this is many: caching, cores, brand, speed, processes/threads, programs running,
;system uptime, CPU speed stepping.
;Considering how "busy" CPU's are on a PC, the cycle count is constantly changing and very rapidly,
;and it changes at unknown intervals, all this makes it perfect as the base for a random function.
;Note! This is "random" we are talking about, not pseudo-random like Random() or perfect entropy (impossible really)
;RadomBits() is perfectly random in that, there is no way to predict at all what that least signficant bit will be.
;So now you can make your "AI" seemingly behave randomly (or unexpectedly) in Yes/no, Positive/Negative, On/of situations,
;shoot/do not shoot, the player has been seen/not seen, a car is about to drive by/or not drive by.
;In a game or application, depending on your needs, you may also want to track the last n choices,
;just to avoid behaviour that migth seem tiresome to the player or user. (sort of like a pseudo-random function).
;Part of what makes RandomBit() so great is that combined with the time when it's called makes it even more unpredictable.
rsts
Addict
Addict
Posts: 2736
Joined: Wed Aug 24, 2005 8:39 am
Location: Southwest OH - USA

Post by rsts »

Very interesting.

I'm sure we'll have some statistians weigh in on how random it really is, but if so, it looks very useful. However, it looks like under some processor circumstances it may not be random.

Thanks.
User avatar
Rescator
Addict
Addict
Posts: 1769
Joined: Sat Feb 19, 2005 5:05 pm
Location: Norway

Post by Rescator »

Sure it is, you can't predict what it will be right? That's truly random.

Even the small procedure itself eats up 'n' number of CPU cycles.
Everything eats CPU cycles, even the most trivial things.
whether it is a Intel or a AMD the cycles eaten is different,
or if it's a Athlon or Phenom, the cycles are different,
different clock speeds, the cycles are different.
CPU throttling, the cycles are different,
different PB compiler/libs used, the cycles are different.

The only way to predict would be to "intercept" every single clock cycle on the CPU core being used, but that itself would eat a lot of cycles and would really slow things down, it would just be easier to either hack the program or write a virus or logger of sorts, the bit fetched may not always come from the same CPU core (the OS might have moved the thread/program to another core)

This is the complexity of a advanced computer system, reduced to a single unpredictable toggling of a bit being 1 or 0 :P

I'm not saying this is perfect for security randomness, or maybe it is?
Except that even security software would only use the least significant bit,
the rest do have a increasing pattern of time, if you need more "random bits" then a soundcard could be a interesting source.

The whole gimmick about the procedure above is how fast it is, compared to anything else, and how unpredictable.
Those two numbers shown are all the ones and zeros measured,
the real number of cpu cycles is way higher than that,

We're basically picking the bit randomly (our timing is not guaranteed),
from a random indefinite stream of bits (CPU cycles never end and is unpredictable).

The tests I've shown here are facinating, I only managed to get a 50/50 perfect balance a single time so far, usually it's balance is 50% (+/- 1% to 2%) with bit sampling done over time,
picking millions of bit samples in a tight loop is not advised as caching may cause bias due to CPU optimization, it is "predictable" as it takes place x cycles after the last bit sampling
Taking bit samples at each VBLANK should also be ok, as there is no way to know how many cycles will actually happen between each VBLANK.

Just play around with the loop and you'll see how it works.
Of course, in theory as this is close to natural random as you can get (this easily at least),
there is always the chance that you might end up with almost only 1's rather than 0 over a period of time.
So my advise for a game where a NPC use RandomBits() to pick the left or right path to walk, it might be smart to swap the two so that =1 is not always the left path for example, use 0 sometimes.

Of and this RandomBits() is perfect to simulate a coin toss among other things, heads or tails? *laughs*

After all it would be silly if the npc went in circles wouldn't it (if it got a bunch of 1's in a row)
Then again, a single npc walking in a circle would be a random act in and of itself, I guess it depends on whether that behavior would fit the situation.

As to applications the opportunities are endless, although I haven't tested, the bit sampling should be pretty similar to white noise (or is it pink?)

Remember, when some of you think random you are actually thinking pseudo random, in that you do not want a bunch of 1's in a row, or do not want a bunch of 0's in a row, well sorry but this tiny procedure do not guarantee that, just like in real life you never know what you'll get :)
User avatar
Rescator
Addict
Addict
Posts: 1769
Joined: Sat Feb 19, 2005 5:05 pm
Location: Norway

Post by Rescator »

Here are two examples. A coin toss, and a Yatzee dice roll.
A possible enhancement for the dice roll is to add a Delay(0) in some places.

Code: Select all

EnableExplicit
DisableDebugger

Procedure.i RandomBit()
 !RDTSC ;Read the CPU Time Stamp Counter
 !AND EAX,$1 ;We only want the least significant bit as that changes the most.
 ProcedureReturn ;Return the EAX register content. (0 or 1 in this case)
EndProcedure

Procedure.i RandomDice()
 Protected bit.i,dice.i
 bit=RandomBit()
 If bit ;1,3,5
  bit=RandomBit()
  If bit ;1,5
   bit=RandomBit()
   If bit
    dice=1
   Else
    dice=5
   EndIf
  Else ;3
   dice=3
  EndIf
 Else ;2,4,6
  bit=RandomBit()
  If bit ;2-6
   bit=RandomBit()
   If bit
    dice=2
   Else
    dice=6
   EndIf
  Else ;6
   dice=4
  EndIf
 EndIf
 ProcedureReturn dice
EndProcedure

Define bit.i

bit=RandomBit()
EnableDebugger
If bit
 Debug "Coint=Heads"
Else
 Debug "Coint=Tails"
EndIf
Debug ""
DisableDebugger

Define.i dice1,dice2,dice3,dice4,dice5
dice1=RandomDice()
dice2=RandomDice()
dice3=RandomDice()
dice4=RandomDice()
dice5=RandomDice()
EnableDebugger
Debug "Dice1="+Str(dice1)
Debug "Dice2="+Str(dice2)
Debug "Dice3="+Str(dice3)
Debug "Dice4="+Str(dice4)
Debug "Dice5="+Str(dice5)
Debug ""
DisableDebugger
PS! Did you know that the thermal temperature of a CPU also influence the CPU cycle counter? :)
User avatar
idle
Always Here
Always Here
Posts: 5049
Joined: Fri Sep 21, 2007 5:52 am
Location: New Zealand

Post by idle »

very interesting, thanks
"pin a tail on it and call it a weasel"
-blackAdder. (meaning very cunning)
freak
PureBasic Team
PureBasic Team
Posts: 5929
Joined: Fri Apr 25, 2003 5:21 pm
Location: Germany

Post by freak »

However unpredictable you think this may be, it still not "truly random". :P

If it were that easy, everybody would be doing it this way ;)
quidquid Latine dictum sit altum videtur
User avatar
Rescator
Addict
Addict
Posts: 1769
Joined: Sat Feb 19, 2005 5:05 pm
Location: Norway

Post by Rescator »

Well, yes and no.

It is only the least significant bit that has this behavior,
so that limits it's usefulness to random bit (on/off) only.
And since it is truly random (you might get a 50% spread in one test or a 75% spread in another) it is not that useful other than typical "coin toss" generation.

99% of random number generators are pseudo random number generators.
PureBasic's Random() is based on Mersienne Twister or? In any case, Random() has a nice even spread (very close to 50%)
So you could use Random(1) instead of the RandomBit() procedure and still get good results.

But the whole point of RandomBit() is it's truly random, you have no guarantee of anything, you could get:
A: 0,1,0,1,0,1,0,1
B: 0,0,0,0,0,0,0,0
C: 1,1,1,1,1,1,1,1
D: 0,1,1,0,1,0,1,1
etc:

With Random() you would never get A, B or C as it's tuned towards D behavior.
Something truly random also have a chance of exhibiting temporary patterns, anyone that knows a little about chaos, know that there are unpredictable patterns in chaos as well.

Just like in real life if you toss a coin, on average you'd assume equal amounts of heads or tails, but in reality you could end up with 3 heads in a row then 1 tail and 2 heads again, if playing against someone they might accuse you of cheating or using a biased coin,
but unless you actually did cheat, then it's simply the behavior of true randomness in other words unpredictability.

For example the simple dice test above needs to be modified before actual use, preferably by a quick statistical test so that the dice picker can ensure that 6's are less common than 5's, and that 1's are more common than 2's.
Obviously this is not real behavior but it does make for a more balanced play, and in games like Yahtzee it really makes getting all 6's really special.

Take the following test for example.
Random() has a nice even spread, while RandomBit() does not.
But we all know that in real life (aka nature) that things are never evenly balanced, and that the balance shifts all the time, i.e. the bias that is there is also unpredictable.

If there is a 50% chance the next bit retrieved will be 0, if it's truly random, there is also a 50% chance it never ever will be 0, though highly unlikely, aka improbable.

Those of you who have read Hitchhikers Guide To the Galaxy and recall the Improbability Drive might understand what I'm hinting at here.
Just because something is improbably, does not mean it's impossible that it could happen.
Just by swapping the position of a few lines, or swapping the 5 and 6 in the dice selection, the apparent biases change completely to something way unexpected.

Now if that isn't random, then I don't know what is. :)
I think that RandomBit() used at random intervals would make for a excellent random bitstream.

Code: Select all

DisableDebugger
EnableExplicit

Procedure.i RandomBit()
 !RDTSC ;Read the CPU Time Stamp Counter
 !AND EAX,$1 ;We only want the least significant bit as that changes the most.
 ProcedureReturn ;Return the EAX register content. (0 or 1 in this case)
EndProcedure


Define.i bitone,bitzero,randone,randzero,i

For i=1 To 1000000
 If Not RandomBit() ;originally the Not wasn't here,
  bitzero+1 ;and this
 Else
  bitone+1 ;and this was swapped
 ;but the results had an odd bias then, (cpu caching?)
 ;your system has probably a completely different behavior than this.
 EndIf
Next

For i=1 To 1000000
 If Random(1)
  randone+1
 Else
  randzero+1
 EndIf
Next
EnableDebugger

Debug Str(bitone)
Debug Str(bitzero)
Debug ""
Debug Str(randone)
Debug Str(randzero)
PB
PureBasic Expert
PureBasic Expert
Posts: 7581
Joined: Fri Apr 25, 2003 5:24 pm

Post by PB »

> However unpredictable you think this may be, it still not "truly random"

Yep. As I say: "Randomness is just an equation that humans don't understand."

> you might get a 50% spread in one test or a 75% spread in another

True random means 100 coin tosses could be 100 heads and 0 tails.
I compile using 5.31 (x86) on Win 7 Ultimate (64-bit).
"PureBasic won't be object oriented, period" - Fred.
User avatar
netmaestro
PureBasic Bullfrog
PureBasic Bullfrog
Posts: 8425
Joined: Wed Jul 06, 2005 5:42 am
Location: Fort Nelson, BC, Canada

Post by netmaestro »

;You should get close to even numbers on average (50%/50%) in the above test
Yes, the numbers are quite close but I'm seeing a marked bias toward 0. After many runs, each result set is within 2% or so of its counterpart but the problem is that virtually all runs result in the 0 set being the higher one, never the other way around.
BERESHEIT
User avatar
Rescator
Addict
Addict
Posts: 1769
Joined: Sat Feb 19, 2005 5:05 pm
Location: Norway

Post by Rescator »

Yep! Please note that the tests here are small, and specific.

In a game or app you would not do a million coin tosses in a row wold you?
no, you'd toss the coin when the user click Toss, or the Roll Dice button etc.

Thus the user themselves become the random time interval between each time RandomBit() is called which itself is affected by every single thing going on inside the PC.

In a dice app, I may or may not use RandomBit() id' probably base it on Random() but depending on the app and how it interacts with the user I might use RandomBit() to add unpredictability into the mix for example.

I'd never advise using RandomBit() as it is for crypto stuff, for that it's far to random, erm, unpredictable.
Maybe it should be named UnpredictableBit() so as not to be confused with pseudo-random generators ;)
User avatar
Rescator
Addict
Addict
Posts: 1769
Joined: Sat Feb 19, 2005 5:05 pm
Location: Norway

Post by Rescator »

netmaestro wrote:
;You should get close to even numbers on average (50%/50%) in the above test
Yes, the numbers are quite close but I'm seeing a marked bias toward 0. After many runs, each result set is within 2% or so of its counterpart but the problem is that virtually all runs result in the 0 set being the higher one, never the other way around.
Try adding a Delay(0) to force a task switch on the thread/process,
as it is possible that the cpu cache/optimizing ends up looping the routine, and with code padding it is possible to get a bias towards 2's complement using either 0 or 1 as it's starting point.

A interesting use could be to use Random() but seed it using the system time, but use RandomBit() to decide if this timestamp should be used or if another should be used instead. Very useful if seeding multiple random numbers at the start of a program for example, and the behavior would be different from system to system even if two systems was perfectly synced and picked seeded Random() at the exact same moment in time.
(the chance of two cpu's on two different systems being in exact cycle sync is highly improbable heh)
User avatar
Kaeru Gaman
Addict
Addict
Posts: 4826
Joined: Sun Mar 19, 2006 1:57 pm
Location: Germany

Post by Kaeru Gaman »

a way for a (most close to) true random value is
to use a synth to produce white noise and read out the lowbyte of the pitch value...

;)

old method from C64's SID, you could directly Peek the lowbyte of OSC3...
oh... and have a nice day.
freak
PureBasic Team
PureBasic Team
Posts: 5929
Joined: Fri Apr 25, 2003 5:21 pm
Location: Germany

Post by freak »

Sorry, you just reiterated your original argument, which is "it looks random to me"

Why do you think cryptographic save random number generators use as many sources for entropy ("randomness") as they can get their hands on (soundcard, noise on other ports, kernel data structures, timers, etc etc), and even then post-process the combined data to make the output as unbiased as possible. If a simple method of input like yours would be enough, then they would not be that complicated. There is a good reason why generating random numbers is an entire field of study.

> I'd never advise using RandomBit() as it is for crypto stuff, for that it's far to random, erm, unpredictable.

Sorry, but thats just the joke of the day :P

It may well be enough for your tasks, but "truly random" is something very different from this.
quidquid Latine dictum sit altum videtur
User avatar
Rescator
Addict
Addict
Posts: 1769
Joined: Sat Feb 19, 2005 5:05 pm
Location: Norway

Post by Rescator »

http://en.wikipedia.org/wiki/Random
If a simple method of input like yours would be enough, then they would not be that complicated.
I never said it would be enough on it's own, I never said this was for cryptography.
I said and have said every time that this is perfect for a coin toss or possibly to help cast dice etc.

A PRNG like PureBasic's Random() can not produce sequences like 11111 or 0000 or 010101 as it's designed not to do that.
Something truly random, something truly unpredictable, COULD produce such patterns, and the LSB of the CPU's TSC does exhibit that behaviour.

Also, some crypto systems DO use the TSC as one of multiple sources to seed their PRNG's.
> I'd never advise using RandomBit() as it is for crypto stuff, for that it's far to random, erm, unpredictable.
Sorry, but thats just the joke of the day
And why is that? It's obvious that using the TSC as a RNG would be a horrible choice, you can't have a unpredictable RNG, that's why crypto uses PRNG's instead to avoid anything resembling patterns (even naturally occurring random patterns).
Even a temporary pattern could make a key stream weak at a moment and thus allow an attacker to crack the stream or key.

"truly random" is something very different from this.
Oh really? Something that is random is something that is unpredictable (synonym). There is no way of knowing what something might be at any given moment in time. The LSB of the TSC fit that criteria. (EDIT: Not entirely true, at the moment the CPU starts the LSB of the TSC will most likely be 0, but after the first task starts it's truly random from then on)

So if you know what truly random is then please enlighten us.
Just saying "haha your wrong" and not backing it up rubs me the wrong way, as far as I can recall there's never been any beef between us before, so where this is coming from I have no idea.
But if you can back up what random is and it means something else than the dictionaries state then by all means do so, I'm all ears to be corrected.
User avatar
Rescator
Addict
Addict
Posts: 1769
Joined: Sat Feb 19, 2005 5:05 pm
Location: Norway

Post by Rescator »

Read this: http://www.nytimes.com/1988/04/19/scien ... ssful.html

"The way people perceive randomness in the world around them differs sharply from the way mathematicians understand it and test for it."
"Although it seems paradoxical, if the zeroes and ones are too evenly mixed, they are not random."
"A real sequence of 100 coin flips is likely to contain several strings of five or six consecutive heads or tails."
The LSB of the TSC fit those criteria.
Post Reply