RSS Feed

randomness

September 6, 2005 by Saar Drimer

At Xilinx, I developed two new ways to generate truly random numbers inside an FPGA. One was submitted as a patent (11/2003, still there) and the other given upon specific customer request. My manager and I wrote “Thats So Random” to tease customers into asking us about our solutions. We had a few responses and I enjoyed helping customers out knowing that they use the fruits of my work. As part of the patent application and verification of randomness, I had to do quite a bit of reading and research. Randomness is a very interesting because it is a statistical process as opposed to other engineering problems that are deterministic in nature (keyword “spec.”) One can not prove randomness, but rather evaluate how close a sequence is to what is statistically considered to be random. The more I read about it, the more complicated it got; it took me quite some time to get a handle on what p-values actually mean, for example. There exists many tests for randomness (see NIST and Diehard for example) but they are constantly under criticism over their methods and results. In other words, there is no definitive test by the very nature of the problem, and that makes it interesting, and sometimes confusing.

Of course, Scott Adams nailed the issue in 3 comic frames…
dilbert random
Accounting Troll: “Over here we have our random number generator.”
Number Generator Troll: “Nine Nine Nine Nine Nine Nine”
Dilbert: “Are you sure that’s random?”
Accounting Troll: “That’s the problem with randomness: you can never be sure.”

I was thinking about randomness again when I read Michael Larsen’s “Press Your Luck” story (via Schneier.) I won’t ruin the ending for you, but he managed to find a pattern in what was supposedly a random sequence of events for a handsome reward. How many systems have this flaw? A lot would be my guess. It would be interesting to look for some as part of my future research.


2 Comments »

  1. Cool!

    When are you going to conquer pi and large prime numbers? (Guess you gotta leave something for England ;)

  2. Anonymous says:

    So what do you think of Wolfram’s random number generator based on Elementary Cellular Automaton Rule 30? (see http://mathworld.wolfram.com/ElementaryCellularAutomaton.html ).

    I implemented it after reading about it (his book does not say its use is restricted), i’ve used it, and I rather like it, in an artistic way.

    – The Precision Blogger
    http://precision-blogging.blogspot.com

Leave a Reply

Your email address will not be published.