PureBasic Forum

Public Domain.

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.

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

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

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.



PS! Did you know that the thermal temperature of a CPU also influence the CPU cycle counter?

very interesting, thanks

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

If it were that easy, everybody would be doing it this way

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.

> 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.

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.

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

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)

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...

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

It may well be enough for your tasks, but "truly random" is something very different from this.

http://en.wikipedia.org/wiki/Random



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.



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.




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.

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.