Nice... :)

Did you do any checking of the results, to see if the results comply with real randomness?

Post Edited (IWriteCode) : 3/22/2007 9:44:00 AM GMT

Bothersome bias or not, it's now fixed! Von Neumann had come up with a simple means to remove bias:

1) Gather your 'random' bits in sets of two.

2) If they are the same, throw them away.

3) If they are different, output the first one.

4) Repeat.

So, you throw away quite a few bits, but wind up with an unbiased stream, which does indeed check out fine.

I updated the new version of RealRandom into the first post of this thread.

This subject of randomness is quite fascinating and has a lot of very practical application, even for simple projects. Here is some explanation text I wrote for the object which I hope conveys the significance of the matter:

Background and Detail:                                                                              
                                                                                                    
A real random number is impossible to generate within a closed digital system. This is because there are no reliably-random states within such a system at power-up, and after power-up, it behaves deterministically. Random values can only be 'earned' by measuring something outside of the digital system.                                                

In your programming, you might have used 'var?' to generate a pseudo-random sequence, but found the same pattern playing every time you ran your program. You might have then used 'cnt' to 'randomly' seed the 'var'. As long as you kept downloading to RAM, you saw consistently 'random' results. At some point, you probably downloaded to EEPROM to set your project free. But what happened nearly every time you powered it up? You were dismayed to discover the same sequence playing each time! The problem was that 'cnt' was always powering-up with the same initial value and you were then sampling it at a constant offset. This can make you wonder, "Where's the end to this madness? And will I ever find true randomness?".

In order to have real random numbers, either some external random signal must be input, or some analog system must be used to generate random noise which can be measured. We're in luck here, because it turns out that the Propeller does have sufficiently-analog subsystems which can be exploited for this purpose -- each cog's CTR PLLs. These can be exercised internally to good effect, without any I/O activity.

This object sets up a cog's CTRA PLL to run at the main clock's frequency. It then uses a pseudo-random sequencer to modulate the target phase of the PLL. The PLL responds by speeding up and slowing down in a an endless effort to lock. This results in very unpredictable frequency jitter which is fed back into the sequencer to keep the bit salad tossing. The final output is a truly-random 32-bit unbiased value that is updated every few microseconds. This value can be sampled by your application whenever a random number is needed.                                               

Post Edited (Tracy Allen) : 3/23/2007 4:54:35 PM GMT

Post Edited (TransistorToaster) : 3/25/2007 1:52:08 AM GMT

Tracy,

It's true that it's now effectively generating one bit at a time (with the biasing algorthm in place), but if that bit is really random, I don't see how it changes anything in the aggregate (i.e. larger numbers made of multiple random bits). I just ran a bunch of tests and determined that, on average, it's updating the entire long every 100us. Worst case was measured at 170us, so I think 200us would be a conservative sample interval. I've added a waitcnt into the Spin routine which returns the random long, so that all-new bits are guaranteed. I'm posting the new version at the top of this thread. I made the assembly code a little more efficient and improved the docs.

Like you said, the LFSR is only serving as an excitation impetus. Most of the wackiness comes straight from the PLL, itself, in the form of CNT deviations which dramatically re-steer the LFSR every cycle.

One funny thing that seems apparent to me is that high-integrity random generators all seem to be rather event-driven, and never completely deterministic in their timing. After all, a basic task of theirs is to observe, not dictate. This means that samples don't lend themselves to exact timing, but percolate out when they are ready. I guess that's just part of randomness.