Slashdot Mirror
Are The Digits of Pi Random?
Steve Hamlin writes "A researcher at Lawrence Berkeley National Laboratory, and his colleague at the Center for Advanced Computation at Reed College, have taken a major step toward answering the age-old question of whether the digits of pi and other math constants are "random."
In addition, a simple formula discovered makes it possible to calculate the Nth binary digit of Pi without computing any of the first N-1 digits, and do the computation with very little computing power.
"
I was wondering the same thing...BUT. I think we're looking at this the wrong way. the number are not, and have never been, and are in no danger or question of BEING, truly random. they're there, they're set, and it's done. the question is "is there a pattern"? and so, the formula does not automatically force there to be a pattern, just forces us to realize that they're static and predictable.- ----------
-----------------------------------
All that glitters has a high refractive index.
You see, without that little doohicky, the universe stops.
http://propheteer.org
I whipped up a little perl script earlier this summer that a friend and I used to informally prove to ourselves that the digits 0..9 are fairly evenly distributed in the first million digits of pi. I guess that doesn't really have anything to do with the randomness of their positions, but it didn't look like there are, for example, significantly more 5's than 8's in there...
Posted from the wireless couch.
A lot of people are playing fast and loose with the word 'random' today. The value of Pi, in whole or of any one digit, isn't random at all. It's entirely deterministic, defined rigidly by a simple formula. No matter how many times or ways that formula is interpreted, the value of Pi is the same, and not random.
What can be said to be 'random' (really pseudorandom or, in the parlance of mathematicians, 'random enough') is an arbitrary digit or sequence of digits from pi, given that the starting decimal place N is also random, or at least non-repeating. The randomness of pi is that each succeeding digit of Pi has no correlation to the preceding digit.
Of course we all know this inherently, but it wouldn't hurt to be a little clearer in these posts about exactly what is random (or not) about Pi.
Kevin Fox
--
Kevin Fox
If the circumference measurement is from inside the brim (or something like that), you get a value for pi that is 0.073% accurate, well within the significant figures used by Hebrews for measuring at that time.
Not that the bible is a Mathematics text...
--LP
There was a distributed computing project called PiHex that lasted several years for computing the five trillionth, 40 trillionth, and the quadrillioth bit of Pi, using a variant of the Plouffe discovery, Bellard's formula.
A proof that digits of Pi are random would indeed be news, albeit not exactly a surprise; I'd comment on it but the article's link seems bad or swamped at the moment.
--LP
P.S. Google has a nice list of Pi links.
For an even more spooky coincidence, click twice on Find Next, and carefully note the 3 last digits of the error message (start position...).
Say no to software patents.
in 1897 Representative T.I. Record introduced House Bill 246 suggesting three values for pi: 3.2, 4, and ~3.23. These three figures were based on the work of an amateur mathematician Edward Goodwin. The bill was quickly forwarded to the Committee on Swamp Lands (of course), which then forwarded it to the Committee on Education. This committee gave it a pass, where the House approved it unanimously. The bill made it to the Senate.
Before the Senate could make asses of themselves as well, a professor of mathematics at Purdue named C.A. Waldo, intervened, and it died an embarrassing death.
For a more humorous account, read Cecil Adam's account of this at the Straight Dope.
Insert simplistic political, ideological, or personal proselytization here.
Suppose there is some base b such that the digits of repeat. Then Pi * b * m = n where m and n is some integer. And so we would have Pi = n / b *m. But m and n are integers, as is b. So you've just shown that Pi is a rational number. It is not. Hence, no such base exists.
I couldn't get the link in the story to work, and found this while searching for the story.
The Economics of Website Security
Well, if you're going to be using "cubits", it's not like precision is really a concern to begin with. IIRC, The cubit was the distance from the elbow to the tip of the longest finger. Whoever was ruler at the time set the standard. It would be interesting to see how close we could come doing it by hand, or with a "cubit-stick".
For all intensive purposes, "whom" is no longer a word. That begs the question, "who cares"?
Since pi predates the DMCA and everything 'protected' under it, pi must count as 'prior art', invalidating ALL copyright and patent claims.
If it is possible to calculate digits of Pi starting at any point, then you could easily use Pi as a pseudo-random pad.
Once you know the starting digit location, you can easily decrypt something that has been XOR'd with the sequence from that point onward. But - given that each n-bit sequence occurs 1/n of all n-bit sequences, there are essentially an infinite number of options facing the code-breaker - even after each successful step!
If you are feeling particularly vicious that day, encrypt with two XOR sequences, based on two difference starting points.
And he made a molten sea, ten cubits from the one brim to the other: it was round all about, and his height was five cubits: and a line of thirty cubits did compass it round about.
And today, thanks to the hard work of a pair of students at Carnegie Mellon University, we can read that language.
And without further ado, here is the hidden message starting at the 74088 digit:
Since the website seems to be /.ed, I give you the article:
===
Are the Digits of Pi Random? A Berkeley Lab Researcher May Hold the Key
A researcher at the Department of Energy's National Energy Research Scientific Computing Center (NERSC) at Lawrence Berkeley National Laboratory, and his colleague at the Center for Advanced Computation at Reed College, have taken a major step toward answering the age-old question of whether the digits of pi and other math constants are "random." Their results are reported in the Summer 2001 issue of Experimental Mathematics.
July 26--Pi, the ubiquitous number whose first few digits are 3.14159, is irrational, which means that its digits run on forever (by now they have been calculated to billions of places) and never repeat in a cyclical fashion. Numbers like pi are also thought to be "normal," which means that their digits are random in a certain statistical sense.
David Bailey
Describing the normality property, David H. Bailey, chief technologist at NERSC, explains that "in the familiar base 10 decimal number system, any single digit of a normal number occurs one tenth of the time, any two-digit combination occurs one one-hundredth of the time, and so on. It's like throwing a fair, ten-sided die forever and counting how often each side or combination of sides appears."
Pi certainly seems to behave this way. In the first six billion decimal places of pi, each of the digits from 0 through 9 shows up about six hundred million times. Yet such results, conceivably accidental, do not prove normality even in base 10, much less normality in other number bases.
In fact, not a single naturally occurring math constant has been proved normal in even one number base, to the chagrin of mathematicians. While many constants are believed to be normal--including pi, the square root of 2, and the natural logarithm of 2, often written "log(2)"--there are no proofs.
The determined attacks of Bailey and his colleague Richard Crandall, director of the Center for Advanced Computation at Reed College, Portland, Oregon, are beginning to illuminate this classic problem. Their results indicate that the normality of certain math constants is a consequence of a plausible conjecture in the field of chaotic dynamics, which states that sequences of a particular kind, as Bailey puts it, "uniformly dance in the limit between 0 and 1"--a conjecture that he and Crandall refer to as "Hypothesis A."
"If even one particular instance of Hypothesis A could be established," Bailey remarks, "the consequences would be remarkable"--for the normality (in base 2) of pi and log(2) and many other mathematical constants would follow.
A simple formula discovered with the integer-relation algorithm dubbed PSLQ makes it possible to calculate the Nth binary digit of Pi without computing any of the first N-1 digits, and do the computation with very little computing power.
This result derives directly from the discovery of an ingenious formula for pi that Bailey, together with Canadian mathematicians Peter Borwein and Simon Plouffe, found with a computer program in 1996. Named the BBP formula for its authors, it has the remarkable property that it permits one to calculate an arbitrary digit in the binary expansion of pi without needing to calculate any of the preceding digits. Prior to 1996, mathematicians did not believe this could be done.
The digit-calculation algorithm of the BBP formula yields just the kind of chaotic sequences described in Hypothesis A. Says Bailey, "These constant formulas give rise to sequences that we conjecture are uniformly distributed between 0 and 1--and if so, the constants are normal."
Bailey emphasizes that the new result he and Crandall have obtained does not constitute a proof that pi or log(2) is normal (since this is predicated on the unproven Hypothesis A). "What we have done is translate a heretofore unapproachable problem, namely the normality of pi and other constants, to a more tractable question in the field of chaotic processes."
He adds that "at the very least, we have shown why the digits of pi and log(2) appear to be random: because they are closely approximated by a type of generator associated with the field of chaotic dynamics."
For the two mathematicians, the path to their result has been a long one. Bailey memorized pi to more than 300 digits "as a diversion between classroom lectures" while still a graduate student at Stanford. In 1985 he tested NASA's new Cray-2 supercomputer by computing the first 29 million digits of pi. The program found bugs in the Cray-2 hardware, "much to the consternation of Seymour Cray."
Crandall, who researches scientific applications of computation, suggested the possible link between the digits of pi and the theory of chaotic dynamic sequences.
While other prominent mathematicians in the field fear that the crucial Hypothesis A may be too hard to prove, Bailey and Crandall remain sanguine. Crandall quotes the eminent mathematician Carl Ludwig Siegel: "One cannot guess the real difficulties of a problem before having solved it."
Among the numerous connections of Bailey's and Crandall's work with other areas of research is in the field of pseudorandom number generators, which has applications in cryptography.
"The connection to pseudorandom number generators is likely the best route to making further progress," Bailey adds. "Richard and I are pursuing this angle even as we speak."--by Paul Preuss
===
Enjoy.
-- russ
Natural != (nontoxic || beneficial)
"Anyone who considers arithmetical methods of producing random digits is, of course, in a state of sin."
(John Von Neumann, 1951 )
+++ UGUCAUCGUAUUUCU
Consider:
Therefore, somewhere in the digits of Pi is a string of digits which, when transformed into binary, form the code to decrypt CCS on a Linux box. All the scientists have to do is find the correct starting position and how may digits need to be calculated. The resulting information could be spread throughout the internet and used to decrypt protected content.
Further investgation into the true nature of Pi is a violation of the DMCA! This must stop at once!
or... Holy moley! Taking that same argument, one could reason that every movie ever made, or that ever could be made, is buried digitally in Pi somewhere! Piracy is built in to the very structure of the universe!!!!
Tatsujin
"It is a profound and necessary truth that the deep things in science are not found because they are useful; they are found because it was possible to find them." -Robert Oppenheimer
Robert Moody from the Department Mathematical Sciences, University of Alberta illustrates the importance of curiosity based research in his paper using lasers as an example of why curiosity based research is necessary.
Carl Sagan in his book, The Demon Haunted World, also stresses the importance of curiosity based research using James Clark Maxell's discoveries as an example of how it effects our lives today by providing the necessary building blocks for radio, television, computers, lasers, etc.
It may be a while before we can find any spectacular applications with this new knowledge of pi, or we may not find any spectacular applications before we dissapear in the cosmos.
The point is: We'll never know if there are any spectacular or even merely useful applications if it isn't shared, discussed and debated throughout the community.
"Communism is like having one [local] phone company " - Lenny Bruce
Here's the output of John Walker's ent program for 512 megabits of Pi:
For the entropy test, a completely random sample would have an entropy of 8.0 bits per byte, and the ideal Chi Square distribution would be 256.0 (considering there are 256 degrees of freedom in an 8-bit data structure, or 2**8 possibilities.) As you can see, that's about as random as you can get. And the larger the samples you feed it, the more it converges to the ideal values.I've also done some testing with other transcendental numbers, such as e (2.718281828...), and they all seem to show great randomness properties, in the information-theoretic sense at least. However, I have a feeling to "trust" Pi more than e, given that you can write e in form of continued fractions with repeating patterns, and nobody has yet found a pattern in the continued fractions of Pi.
As for my pseudo-random library project, my programming skills are quite bad, but if you have some knowledge of scientific computing (multiplication algorithms using FFTs, for example), you can contact me and I might revive the idea.
Join the NFSNET. Our prime goal is making little numbers out of big ones. http://www.nfsnet.org/