Home
JAQForum Ver 24.01
Log In or Join  
Active Topics
Local Time 22:50 13 Jul 2025 Privacy Policy
Jump to

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 Zealand
Posts: 9593
Posted: 04:15pm 27 Mar 2015
Copy link to clipboard 
Print this post

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: Netherlands
Posts: 81
Posted: 08:18am 28 Mar 2015
Copy link to clipboard 
Print this post

  JohnS said  My point is that I disagreed with the blanket statement that a test for randomness is to (try to) compress a chunk and it won't. Well, it may.


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 Kingdom
Posts: 4038
Posted: 04:53am 29 Mar 2015
Copy link to clipboard 
Print this post

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: Netherlands
Posts: 81
Posted: 07:21am 29 Mar 2015
Copy link to clipboard 
Print this post

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: Germany
Posts: 1576
Posted: 07:52am 29 Mar 2015
Copy link to clipboard 
Print this post

  Quote  improbably rare

Exact as rare as any big true random number?

  Quote  Your "counterexample" of the random bits happening to be all zeros is exponentially unlikely to happen,

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:
  robert.rozee said  ...

a truly random bit stream can not be compressed.


rob :-)
Edited by twofingers 2015-03-30
causality ≠ correlation ≠ coincidence
 
JohnS
Guru

Joined: 18/11/2011
Location: United Kingdom
Posts: 4038
Posted: 08:53am 29 Mar 2015
Copy link to clipboard 
Print this post

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: Germany
Posts: 1576
Posted: 09:31am 29 Mar 2015
Copy link to clipboard 
Print this post

  JohnS said   I suspect a truly random bit stream is a mathematical concept not achievable in the real universe.
...
John

I suspect the real universe IS a truly random bit generator.

42!
causality ≠ correlation ≠ coincidence
 
JohnS
Guru

Joined: 18/11/2011
Location: United Kingdom
Posts: 4038
Posted: 09:49am 29 Mar 2015
Copy link to clipboard 
Print this post

It's possible, but I don't think it is.

I don't know a way to be sure either way.

JohnEdited by JohnS 2015-03-30
 
Dylan
Regular Member

Joined: 17/06/2013
Location: Netherlands
Posts: 81
Posted: 10:48am 29 Mar 2015
Copy link to clipboard 
Print this post

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: Australia
Posts: 64
Posted: 07:32pm 31 Mar 2015
Copy link to clipboard 
Print this post

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: Germany
Posts: 1576
Posted: 04:47am 01 Apr 2015
Copy link to clipboard 
Print this post

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


To reply to this topic, you need to log in.

The Back Shed's forum code is written, and hosted, in Australia.
© JAQ Software 2025