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
If it's really low, could we even use /dev/urandom as a seed for the digit choice? Or vice versa?
Send your friends messages of love at fuck-you.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.
Its got a 50% chance of being correct though and
involves coin flipping.
http://www.lbl.gov/Science-Articles/Archive/pi-ran dom.html
Perhaps. But it's a nice tool to beef up your rot-13 substitution cypher.
:-)
What you want is, say, a 1 MB block of the digits of PI expressed in base 256. Then you pick a starting position, and for each byte that you transfer, you rot it by the value of the corresponding byte.
P.S.:
Caution: Now approaching the (technological) singularity.
I think we've pushed this "anyone can grow up to be president" thing too far.
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
Yes, that's a good philosophical position..
.|` Clouds cross the black moonlight,
I'm just wondering, if there's a "formula" for the n'th bit of the thing, it *can't* be random, can it?
For values of `random' that mean `uncompressible' of course, it can probably rate pretty highly.
~Tim
--
~Tim
--
Rushing on down to the circle of the turn
Another good reference is in Chapter 17 of "A History of PI" by Petr Beckman (ISBN 0-88029-418-3). Beckman goes so far as to include a reproduction of the bill.
The bill doesn't actually give any values for PI directly. Rather, it supposes to provide simple formulas for computing the value of PI based on enclosing squares. Here's part of section 1:
"It has been found that the cirular area is to the quadrant of the circumference, as the area of an equilateral rectable is to the square on one side."
And later in section 2:
"By taking the quadrant of the circle's circumference for the linear unit, we fulfill the requirements of both quadrature and rectification of the circle's circumference. Furthermore, it has revealed the ratio of the chord and arc of ninety degrees, which is as seven to eight, and also the ratio of the diagonal and one side of a square, which is as ten to seven, disclosing the fourth important fact, that the ratio of the diameter and circumference is as five-fourths to four, and because of these facts and the further fact that the fule in present use fails to work both ways mathematically, it should be discarded as wholly wanting and misleading in practical applications."
Now, there are about three different "values" for PI in there. Dr. Edwin Goodman, who came up with this tripe, was a "circle-squarer", one who thought PI could be computed, well, easily.
It's scary that the guy was a doctor given his profound misunderstanding of simple geometry, and seeming inability to do the simple measurements which would prove his theories wrong.
But this bill is much bigger in folklore than in real life. Some facts regarding it:
1. It was never passed in to law. Ever. It passed unanimously in the House, and was tabled in the Senate, and never voted on there.
2. It doesn't say that PI=3, PI=3.14, or that PI is equal to any other simple number. Rather, it gives a number of methods (all of which are grossly incorrect) that could be used to very easily calculate PI.
3. It never made it into any textbooks that I know of. That was the goal of Dr. Goodman.
4. It did happen in Indiana, 1897, House Bill No. 246
5. Dr. Goodman, in section 3 of the bill, also claims to have previously trisected an angle. The guy was either a fruitcake or a charlatan.
Michael
Do you have ESP?
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.
And they'll be hearing from God's lawyers. This "formula" is clearly a circunvention device.
--
--
Stay tuned for some shock and awe coming right up after this messages!
Does a base have to be an integer? If not, pi in base(pi) is 10 exactly.
<grub> Reading
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.
The value of the starting position for any useful work would be such a large number that simply expressing the number would in almost all cases take far more bytes than to store the work itself (barring some infinitesimally unlikely occurrence, which is just as unlikely as finding the work randomly occurring in any other form in nature, such as twigs falling from a tree and arranging, just by random luck, into letters and spelling a message). In fact, since the stream of digits of pi is infinitely long, not only can every work that has ever, does, and will ever exist be found in it, but every single work must lie buried an infinite number of times! For any work, you could come up with as many numbers as you want to describe its position.
Small numbers indicating a quantity cannot be copyrighted, but the numbers necessary to express these digit positions would be far beyond any useful quantity imaginable. Just as all digital data is reducible to a long number, these digit positions are encoded data, not useful quantities, and therefore would be protected by copyright as just a representation of the works they are "pointing" to in the digits of pi.
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.
Lawrence Berkley lab has the orignial story their website
No-one did. They just rounded up his number of votes. It was easier that way.
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)
Too bad I can't get to the article to see how they are defining random. I have studied random numbers quite a bit, and have worked on the assumption that any thing that can be calculated is not truely random. So under that definition no, it isn't random, and neither are any of the random number generator algorithms.
The comon test for randomness is the chi squared test which actually tests for dispersion of numbers. That is are number occuring in 'equal' frequencies in an order that isn't too similar to the order in other sections of the sample. Failing the chi squared tests shows you aren't 'Pseudo Random' passing it only proves your numbers are dispersed not random
As x approaches total apathy I couldn't care less.
"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
Whithout being a flaming asshole, what applications are there for knowing if the digits of PI are random or not?
Also, since Pi is a ratio that we 'choose' to express in a base10 numerical system, would the fact that the digits are random in a decimal system mean that they would be random if we expressed Pi in a hexidecimal or octal system?
The next Slashdot story will be ready soon, but subscribers can beat the rush and slashdot the links early!
"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/
At the man's homepage.
http://www.nersc.gov/~dhbailey/
Check out the piqp.c in the middle of the page.
Where do they find these guys? He memorizes pi, i play snake on my cellphone. eh
|---------------|
|---------------|
practically an AC