Slashdot Mirror
Pi: Less Random Than We Thought
Autoversicherung writes "Physicists including Purdue's Ephraim Fischbach have completed a study comparing the 'randomness' in pi to that produced by 30 software random-number generators and one chaos-generating physical machine. After conducting several tests, they have found that while sequences of digits from pi are indeed an acceptable source of randomness -- often an important factor in data encryption and in solving certain physics problems -- pi's digit string does not always produce randomness as effectively as manufactured generators do."
Uhh.. we're surprised? Pi can be described by numerous simple iterative formulas. When we do that with especially built algorithms we get pseudo random numbers.
I'd expect pi to be much worse than a PRNG.
If you calculate pi long enough you'll come up with everything of any significance. Try downloading a pi generating program, such as PiX and requesting enough digits to run for a few days, then open the file in a basic text editor and search for things like your social security number, your phone number, etc. Part of it being infinate is comming across every possible sequence.
Given that its possible to compute any digit of pi without computing the preceding digits its not surprising that the digits have structure. The bizarre part of this algorithm is that computes digits in hexadecimal.
Two wrongs don't make a right, but three lefts do.
"less random"?
When you cite for example a deviation from a Chi distribution, then there is probably some connection between Chi and Pi that doesn't seem obvious from how Chi is calculated, but is there non-the-less.
I am not a mathematician (though I did work at Wolfram Research for ten years). I look forward to seeing real mathematicians take on this.
Letter To Iran
I was wondering, maybe not more than an hour ago, why not get a TV card and gather randomness from there? There are lots of channels on TV, and they have both a video and an audio component. You could set the thing up to change channels at random intervals, and gather things like the color of random pixels at random times, the frequency of random sounds, etc. Perhaps you could use a radio card to do something very similar with the radio. That, combined with entropy from the keyboard, mouse, the time between interrupts of various kinds, the contents of various processor registers or random memory locations, or whatever, should provide basically a random pool that is so random, you'll never have to worry about security problems with relation to them.
Speaking of which, there are ten digits used in our radix 10 notation; if you want to store a character string in a strange format, you could conceivably store two digits in one byte, because four bits are enough to describe all ten digits, leaving plenty of room for things like a decimal point or a negative sign. I'm saying this because it's not too terribly expensive these days to get a terabyte of storage. If you store, on this terabyte, nothing but digits from pi, in this space-saving format I'm describing, you could store 2,417,851,639,229,258,349,412,352 digits from pi. You'd need some kind of cluster, like PI@home, to compute all those digits. Once computed, who said you can't use pattern-matching algorithms to see if there isn't some kind of pattern? I still believe that somewhere in there, there is a pattern, though it is very large. Hell, who said you can't get an exabyte of storage and do this? If anything, it could become one component in a random number generator that simply never repeats itself.
Fractals, which resemble nature, are not random though they appear to be. Therefore, I've often considered all the universe to be one giant, multi-dimensional fractal.
I think "random" has a misleading connotation. Just because something is highly unpredictable, it is not necessarily without pattern. We take "random" to mean something that cannot ever be predicted, that follows no pattern. But attractor fractals and many areas of Chaos Theory have proved that there are patterns that defy the human pattern recognition faculty (or at least require the use of a pencil, calculator, super-computer, etc.).
Esoteric reference.
The fun thing about this is that if pi really is "normal", then if you compute long enough, you'll not only eventually find pictures of circles in base 11, you'll also find an MPEG-4 of NTS video of a hand writing, with goose-quill pen, "I exist, yours sincerely, God."
What's worse is that somewhere else is NTS video of the same hand, writing "I don't exist after all, yours sincerely, God."
(I leave the proof of this as an exercise for the interested student.)
Good enough for Solomon, good enough for me.
I must tell you a story.
In the first half of the 15th century the Persian mathematician Al-Kashi calculated pi to 14 places. It would be over a hundred years until a European calculated it to 9 places. But that's not what makes Al-Kashi cool, the Arabs where so much better at math in that period. What made him cool was that he stopped. He observed that, with his pi, the calculation of the circumference of a circle with a radius twice the size of Earth would have a margin of error smaller than a "horse hair" (a Persian unit). Problem solved, next problem. Meanwhile, people are still today using computers to get pi to _hundreds_of_billions_of_decimal_places!! As if there's something unique about pi because it's irrational and transcendental, when this is in fact true of the vast majority of all real numbers. Here's to Al-Kashi, a sane man and a pragmatic!
Detection of patterns starting at the buzillionth digit of pi (and other transcendentals) provided the starting point of a really good sci-fi book written probably 20+ years ago. The primary character, a nerdy and rich but manly guy (much like most /. readers) harnesses a supercomputer to compute the digits, finds patterns, deciphers same, uses knowledge gained to convert his personal 737 to a starship and sets off to explore. Accompanied (much like most /. readers) by his adoring and beautiful female companion. Sorry, can't remember the name of the book.
http://users.aol.com/s6sj7gt/picode.htm
:)
Quite an entertaining read
For example, lots of large numbers follow Benford's Law. Excerpt: "Benford's law states that in listings, tables of statistics, etc., the digit 1 tends to occur with probability ~= 30% , much greater than the expected 11.1%" The probability distribution is logarithmic; the probability of a digit D is log10(1 + 1/D). This is a way the SEC checks filings for fraud. If the numbers are too evenly distributed, there's a good chance of fraud. Obviously if you know about this law you can spoof it to some degree, but it was an effective tool for a while (still probably is for some not so smart firms).
"Nature doesn't care how smart you are. You can still be wrong." - Richard Feynman
In case, you find that interesting, here is a more recent article on their exploits.
Capturing the Unicorn
"sweet dreams are made of this..."