 Notice. New forum software under development. It's going to miss a few functions and look a bit ugly for a while, but I'm working on it full time now as the old forum was too unstable. Couple days, all good. If you notice any issues, please contact me. |
Forum Index : Microcontroller and PC projects : Truly random?
  Page 3 of 3 |
|||||
| Author | Message | ||||
Grogster Admin Group  Joined: 31/12/2012 Location: New ZealandPosts: 9593 |
Yes, I much prefer the classic TV series or radio show, to the mess that was the movie. ...but I digress.... Smoke makes things work. When the smoke gets out, it stops! |
||||
| Dylan Regular Member  Joined: 17/06/2013 Location: NetherlandsPosts: 81 |
The "blanket statement" you refer to was however prefaced by "one rough-and-ready method", and it was also in the context of detecting NON-RANDOM streams. Specifically, imagine that your method of generating random bits is not "fair". For simplicity, imagine a 2-to-1 ratio of zeros-to-ones (but the same logic applies to 51-to-49). That means that there is a 4/9 chance of "00", 2/9 of both "01" and "10", and just 1/9 of "11". Encode (Huffman) these as "0", "10", "110" and "111" respectively. (4*1 + 2*2 + 2*3 + 1*3)/9 = 17/9 = 1.889 bits required to encode 2 bits => clearly not random enough. If you have such a biased source, then you can take two input bits at a time, ignore them if they are equal, and use one or the other as your output. See http://openfortress.org/cryptodoc/random/ for details. |
||||
| JohnS Guru  Joined: 18/11/2011 Location: United KingdomPosts: 4038 |
Good point though in no way at all does it fit my idea of rough and ready since it can very easily accept a bad RNG and reject a good RNG. If I wanted to test any RNG I'd go read how to do it since it's not anything like as easy as people tend to guess. John |
||||
| Dylan Regular Member Joined: 17/06/2013 Location: NetherlandsPosts: 81 |
It cannot "very easily" accept a bad RNG, even less so reject a good RNG. In two COMPLETELY different ways. A PNRG is, by definition, a bad RNG. It repeats, after all. Worse yet, the classic ax+b mod 2^n PRNGS only look random for about 2^(n/2); that is to say a 32-bit PRNG can only generate 2^16 values before things start looking remarkably similar. Your "counterexample" of the random bits happening to be all zeros is exponentially unlikely to happen, for a "rough and ready test", you are insisting that it fails something asymptotically approaching 0% of the time, and is therefore invalid. Please note that you are "technically correct", and I do not mean that in a disparaging way at all. But you are (or seem to be, perhaps) missing the wood for the trees. Or rather that counterexample you can find which is improbably rare. |
||||
twofingers Guru Joined: 02/06/2014 Location: GermanyPosts: 1576 |
Exact as rare as any big true random number? 
No need for zeros if there occur repeating (squeezable) patterns. Btw. we were talking about truly random number generation. Still to remember, this was the point to proof: causality ≠ correlation ≠ coincidence |
||||
| JohnS Guru Joined: 18/11/2011 Location: United KingdomPosts: 4038 |
I suspect a truly random bit stream is a mathematical concept not achievable in the real universe. ERNIE et al may well not be truly random, but good enough for what they're used for. John |
||||
| twofingers Guru Joined: 02/06/2014 Location: GermanyPosts: 1576 |
I suspect the real universe IS a truly random bit generator. 
42! causality ≠ correlation ≠ coincidence |
||||
| JohnS Guru Joined: 18/11/2011 Location: United KingdomPosts: 4038 |
It's possible, but I don't think it is. I don't know a way to be sure either way. John |
||||
| Dylan Regular Member Joined: 17/06/2013 Location: NetherlandsPosts: 81 |
I realise it is not important to have mathematical intuition about "infinity" in daily life. For my own part, I worked only a little harder than Douglas Adams did at the same place. He apparently wrote three essays in three years, I wrote none. Then again, his subject wasn't Mathematics. Infinite improbability drives do not exist just because anything random enough could happen. The universe doesn't work that way. Truly random bit streams cannot be compressed, because that is the way the universe does actually work. |
||||
brucepython Regular Member Joined: 19/06/2011 Location: AustraliaPosts: 64 |
Perhaps this can provide useful sets of random numbers: http://www.fourmilab.ch/hotbits/how3.html Sadly, using a radioactive source makes this technique somewhat less than portable. Bruce |
||||
| twofingers Guru Joined: 02/06/2014 Location: GermanyPosts: 1576 |
To win twice a million in a lottery is better than owning a TRNG. 
It's really easy to build a good RNG with Maximites and Micromites. BUT it's really hard to create compressible truly bit streams with mmBasic.
... and takes hours! 
Michael causality ≠ correlation ≠ coincidence |
||||
| Page 3 of 3 |
|||||
 Print this page |
 |
The Back Shed's forum code is written, and hosted, in Australia. | © JAQ Software 2025 |
