Beta
×

Welcome to the Slashdot Beta site -- learn more here. Use the link in the footer or click here to return to the Classic version of Slashdot.

Thank you!

Before you choose to head back to the Classic look of the site, we'd appreciate it if you share your thoughts on the Beta; your feedback is what drives our ongoing development.

Beta is different and we value you taking the time to try it out. Please take a look at the changes we've made in Beta and  learn more about it. Thanks for reading, and for making the site better!

Are The Digits of Pi Random?

Hemos posted more than 13 years ago | from the answering-the-age-old-question dept.

Science 478

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. "

Sorry! There are no comments related to the filter you selected.

Re:yeth (1)

Anonymous Coward | more than 13 years ago | (#2188988)

my 6th class chemistry teacher:
"pi is 3.14... which is close to 3 ... for easier calculation we'll use 2."
Dr. Donner
(Yes, this is really true.)

BTW:
Shouldn't that be ...doh.gov ?

anti
ps:
yes, I should lookup my password.

Re:To Random or not To Random (1)

Anonymous Coward | more than 13 years ago | (#2188989)

Umm, that's trivial. The string of random numbers in pi can be compressed down to Leibnitz's series or Wallis's formula, or the formula mentioned in the article, without loss. Although these formulae are all infinite series, they can be represented as a finite number of instructions to instruct a computer to "decompress" pi. finite < infinite, therefore this is pi, compressed.

yeth (2)

Anonymous Coward | more than 13 years ago | (#2188995)

pi = 3

Re:nth digit of pi (1)

phil reed (626) | more than 13 years ago | (#2188999)

Last I heard, the algorithm only worked in base 16, but that may have changed now.

Uh, since the article says it finds the Nth binary digit, I think it would be safe to say that the algorithm actually works in binary. That technically means you're right, since hex is a binary shorthand.


...phil

Re:To Random or not To Random (2)

Tim Macinta (1052) | more than 13 years ago | (#2189001)

here's a simple test... try to compress the "random" string of numbers; if you can compress a string of random numbers, it isn't

I don't think that's correct. Consider an irrational number whose digits after the decimal point each have a 9/10 probability of being a 0 and a 1/10 probability of being a 1. Here are some examples that satisfy this:

0.0000001010000010000000000001....

0.0100000000000001100001000000....
0.0000001001000000001000000101....
This is definitely random (you have no way of knowing whether the next digit will be a 0 or a 1), but it is also definitely compressable (each such number should be compressable to about 1/10th of the original size).

Now, I'm not saying that PI can be compressed in this manner, but if any digit did happen to appear more than another it could be compressed while still being random. A simple Huffman coding should suffice for such cases.

formula for nth digit != random? (5)

Hitch (1361) | more than 13 years ago | (#2189008)

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.

Just one question (2)

Odinson (4523) | more than 13 years ago | (#2189015)

When someone breaks into a beowulf/supercomputer, what will be the default job now? N queens? Traveling salseman? 6 month Market Predictions?

Or maybe just rendering 5 min of Jar-Jar galumping around...Shiver

pi vs. /dev/urandom (2)

boinger (4618) | more than 13 years ago | (#2189016)

So, if pi is random, is it a "good" random? How does it compare to /dev/urandom for useability?

I think someone's said it before, but, doesn't having a formula that allows calculation of arbitrary binary digit, in fact, make it NOT random? I'm just trying to grok how something can be "easily calculated" and still be truly random.

Re:Hate to be a nag, but... (1)

Maxx (9947) | more than 13 years ago | (#2189030)

That link works for me...

Re:nth digit of pi (2)

shaka (13165) | more than 13 years ago | (#2189034)

That's correct, more info here:

http://www.mathsoft.com/asolve/plouffe/plouffe.htm l [mathsoft.com] ,

or for goatse.cx aware:

http://www.mathsoft.com/asolve/plouffe/plouffe.htm l

Last I heard, the algorithm only worked in base 16, but that may have changed now.

Re:To Random or not To Random (1)

ethereal (13958) | more than 13 years ago | (#2189035)

It's tough with an infinitely long number, though. There's no requirement that the compression be done on the fly - I could write a compression algorithm which wouldn't work unless I had access to the entire number.

You could say that the first N digits of pi are random or not based on the compression test, and make some sort of argument that since so far every sequence of pi we've tested was random, it's likely that the whole thing is, but that wouldn't be a very rigorous proof.

Remember: it's a "Microsoft virus", not an "email virus",

Re:The Digits of Pi? (1)

maroberts (15852) | more than 13 years ago | (#2189041)

Huh... I thought pi was a movie

Only when pi is written in the US. Now its got a sequel - American Pi^2!!

Re:Hmmm (2)

platypus (18156) | more than 13 years ago | (#2189048)


People think that randomness is this impersonal force that makes things happen for no reason at all.
What it really is, is an explanation when the factors involved in the outcome are too complicated to grasp.


Nope,
there's just a difference between deterministical chaos and randomness.
That doesn't mean the the latter doesn't exist.

Re:Students Discover Pattern in Pi Digits: (1)

Seanasy (21730) | more than 13 years ago | (#2189056)

Shouldn't it be:
"Sorry for the inconvenience."

Neumann is most likely correct (2)

arasinen (22038) | more than 13 years ago | (#2189057)

Pi will not, unfortunately, give you an arithmetical method of producing random digits.

If you pick digits from pi's decimal expansion with some deterministic method, say, every third digit, the sequence will be the same each and every time you run it. What you do get from pi are non-repeating pseudorandom numbers: you can eg. pick every nth digit where n is your seed (cf. usual (pseudo)random number generators)

To get truly random numbers from pi, you need pick the digits randomly... for which you of course need a random number generator...

Re:Hmmm (3)

PigleT (28894) | more than 13 years ago | (#2189063)

Yes, that's a good philosophical position..

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
--
.|` Clouds cross the black moonlight,

Pi and Sanity (1)

mcwop (31034) | more than 13 years ago | (#2189069)

Don't lots of people go insane thinking about the how's and why's of pi?

Re:To Random or not To Random (1)

jmauro (32523) | more than 13 years ago | (#2189072)

That's wrong. A truely random system has a probabilty that the compression would work. It could genenrate a set of numbers where all are about the same. Probability is low, but the chance is there.

Re:Hmmm (1)

Blindman (36862) | more than 13 years ago | (#2189076)

I think that by random, they mean that the Nth digit has no correlation with any other digit in the sequence.

Regardless of the existence of a pi formula, pi is not random any more than the constant e. Afterall, pi always starts with 3.

Re:Pi is great as a random source. (2)

csbruce (39509) | more than 13 years ago | (#2189077)

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.

I though that you could construct Taylor series for functions like arctan(x) and arctan(1) = 1/4*pi, so pi = 4*(ArcTanTaylorSeries(1)).

I just love these discoveries (1)

chrysalis (50680) | more than 13 years ago | (#2189081)

Now, when someone will show how good he is in maths, I will tell him about that. Chances are that he'd never have heard about this discovery, and he will shut up.

-- Pure FTP server [pureftpd.org] - Upgrade your FTP server to something simple and secure.

Re:To Random or not To Random (1)

MartinG (52587) | more than 13 years ago | (#2189086)

the set is descrete. they are a string of integers.

Re:Why? There are only 3 digits. (1)

1010011010 (53039) | more than 13 years ago | (#2189087)

Great commentary on BattleBots the other night:

(introducing a returning champion)
"With just one more execution, he'll be eligible for the governorship of Texas!"

- - - - -

Re:The signature of the artist ... (1)

be-fan (61476) | more than 13 years ago | (#2189095)

Actually, the point of the research is not to caculate additional digits of Pi, but to understand the mathematical nature of Pi. And such inquiries about mathematics have been show to be immensely useful in all sorts of real world applications. Take the whole "quantum physics" thing. One could ask, "who really cares how a quark behaves on the sub-atomic scale?" Today, it has been found that a significant fraction of the US economy is based on the application of quantum physics.

Partly old news (5)

LinuxParanoid (64467) | more than 13 years ago | (#2189104)

The fact that there's a algorithm for determining the Nth digit of Pi is old news. The BBP formula which does that was discovered by Bailey, Borwein, and Plouffe in 1995. (PDF paper here [cecm.sfu.ca] ).

There was a distributed computing project called PiHex [cecm.sfu.ca] 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 [www-stud.enst.fr] .

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. [google.com]

True story. (4)

BlueUnderwear (73957) | more than 13 years ago | (#2189111)

You can find any of those in Pi... The real challenge however is to find not only an interesting message, but also to find it at an interesting position. And indeed, at position 242424 (including the 3 and the .), you find 42424242. Check for yourself at the PI Search page [angio.net] .

For an even more spooky coincidence, click twice on Find Next, and carefully note the 3 last digits of the error message (start position...).

Re:Neumann said ... (1)

dismayed (76286) | more than 13 years ago | (#2189112)

Just wondering, but did that come from the book Python Standard Library?I was just reading it, and that quote at the beginning of the Random chapter stood out.

Re:To Random or not To Random (1)

shockwaverider (78582) | more than 13 years ago | (#2189113)

No - Not BS.

The size of the decompressor has to be included in the compression calcs.

In addition splitting on a predfined series of bytes is consdered to be a "trick" as it merely offloads the data to the filesystem involved.

Of course they're not random! (2)

jefferson (95937) | more than 13 years ago | (#2189127)

If they were truly random, we'd have a different PI each time we calculate it. Remember that the so-called "random number generators" are in fact pseudorandom. Like the digits of PI, they are deterministic, and with the same starting point in the sequence, you always get the same set of numbers.

Pseudorandom numbers are often used in place of true random numbers, because usually what is needed is a set of numbers with certain properties common to random numnbers, e.g. uniform distribution. Note that for cryptography, pseudorandomness is often not sufficient, and truly random numbers are needed. These are usually generated by sensing the physical world in some way, where, we assume that the combination of chaotic processes and quantum effects makes the incoming values truly unpredictable.

Old News (1)

SamBeckett (96685) | more than 13 years ago | (#2189129)

There has existed an algorithm to find the nth hexadecimal digit of PI for a couple of years now. It seems to me, going from hex to binary is trivial.

More info can be found http://www.mathsoft.com/asolve/plouffe/scimath.txt [mathsoft.com] - there.

DOE - Interesting? (1)

kannen (98813) | more than 13 years ago | (#2189131)

Dude,

This may be the first time they've EVER had significant traffic on their servers. How often do YOU look for cool, interesting articles on the DOE's website. Not very often, I suspect. =)

Base 5 (1)

shpoffo (114124) | more than 13 years ago | (#2189148)

What have we been telling [ology.org] people? It's all about Base 5!


Ewige Blumenkraft!
-shpoffo

Re:Hmmm, YABL (Yet, Another, Broken, Link) (1)

shpoffo (114124) | more than 13 years ago | (#2189149)

it was /.ed - also try his home page [nersc.gov] for more links and such.

pi randomness and algorithmic information theory (1)

jejones (115979) | more than 13 years ago | (#2189151)

Somebody tell me where I'm screwing up here:

Algorithmic information theory defines the amount of information in a string as the length of the (shortest, I would presume--you can always pad code) program that generates it. A random sequence is one that's uncompressible--the best you can do for a program to emit it is to have a copy of the sequence itself in initialized data and spit it out.

Now...if there's an algorithm to generate an arbitrary digit of pi, obviously you can use it to write a function to generate all of them (eventually, in the sense that for any fixed N, you'll only have to wait a finite amount of time for the Nth digit to come out). That seems pretty darned compressible to me, so how the heck can the digits of pi be random? Is my understanding totally off here, or do counterintuitive things happen for infinite strings?

Re:nth digit of pi (1)

daoine (123140) | more than 13 years ago | (#2189157)

I think the more generalized algorithm (which might be what they are talking about) is the PSLQ, which is only like a year and a half old. They talk a little about it at http://www.nersc.gov/news/bailey1-20-00.html [nersc.gov] , but the PSLQ link seems to have been removed due to a copyright lawsuit.

Re:Students Discover Pattern in Pi Digits: (2)

SuiteSisterMary (123932) | more than 13 years ago | (#2189158)

Actually, "We apologise for the inconvenience."

Homer (1)

Nastard (124180) | more than 13 years ago | (#2189159)

Mmmmmm, pi

lalala (2)

Lord Omlette (124579) | more than 13 years ago | (#2189161)

So, anyone can calculate nth digit right? nth digit doesn't require n-1 digits, right? Am I the only one thinking "THIS WOULD MAKE A GREAT DISTRIBUTED CLIENT!!!"?

Peace,
Amit
ICQ 77863057

Depends on how you choose to define "random" (1)

SLi (132609) | more than 13 years ago | (#2189169)

From the Webster's:

Function: adjective
Date: 1565

1 a : lacking a definite plan, purpose, or pattern b : made, done, or chosen at random <read random passages from the book>

2 a : relating to, having, or being elements or events with definite probability of occurrence <random processes> b : being or relating to a set or to an element of a set each of whose elements has equal probability of occurrence <a random sample>; also : characterized by procedures designed to obtain such sets or elements <random sampling>

---

So, pi probably has no plan or pattern, but arguably does have a definite purpose. It wasn't probably made, done or chosen at random, though it's hard to know.

I don't know if we can talk about probabilities together with pi, more than "if we pick a 5 from the decimal representation, which is the probability of the next digit being 8".

Re:To Random or not To Random (1)

SLi (132609) | more than 13 years ago | (#2189170)

Explain to me why I can get this out of a "perfect" random number generator:

Because the probability of a random number being equal to some predetermined value when the set of possible random numbers is not discrete is exactly zero. Perhaps that's why.

Re:To Random or not To Random (1)

SLi (132609) | more than 13 years ago | (#2189171)

here's a simple test... try to compress the "random" string of numbers; if you can compress a string of random numbers, it isn't

Sure, this is a good way of being sure some number is not random. But it doesn't work the other way round. You can't compress already compressed files or encrypted files (well, from good encryption and compression programs), yet they're not random.

Re:Also depend on compression scheme... (1)

SLi (132609) | more than 13 years ago | (#2189172)

Depending of your algorithm (repetion, fractal regression,...) you will get VERY DIFFERENT RESULTS using the same original file.

_No_ compression algorithm ever will compress purely random numbers.

Or to be more precise, no compression algorithm ever will compress more than 50% of all possible inputs of the size n or less for any given n. Proof left as an exercise (it's really simple).

Re:To Random or not To Random (1)

SLi (132609) | more than 13 years ago | (#2189173)

No.

Mathematically, given two infinite sets A and B such that A is continuous and B a discrete subset of A, the probability of a randomly picked number from set A belonging to set B is not only very small (i.e. low probability), but zero. Now A is the group of all "numbers" and B is the group of all compressible numbers. Ergo, the chance is not there.

Pi (1)

SLi (132609) | more than 13 years ago | (#2189174)

Pi is an interesting number for not only being the ratio of a circle's circumference to its diameter, but also another constant in software development. What follows is empirical:

t=pi*t_e, where

t = the time required to finish a project, and
t_e = the estimated time required to finish a project (which also happens to be equal to d-dt, where d is the deadline and dt is the current time).

Cool Application! (5)

FreezerJam (138643) | more than 13 years ago | (#2189188)

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.

Did they crack it or not? (1)

jessh (144140) | more than 13 years ago | (#2189195)

Well the site has been slashdoted so can someone tell me, did they crack pie or didnt they? the description seems to suggest they did but i cant help but think there is a catch.

Encryption (1)

KhaliF (160350) | more than 13 years ago | (#2189203)

This is good :)

Because we can now skip forward in pi orders of magnitude further than before, we could (if we wanted) use pi (with a random and gigantic start point or seed) as an xor source for cheap and nasty encryption :)

more haiku (1)

ReidMaynard (161608) | more than 13 years ago | (#2189205)

not pi in the sky
I beg forgiveness, for I
ate all the pi, *sigh*

Re:Hmmm (1)

sqlrob (173498) | more than 13 years ago | (#2189214)

But if there's a simple formula, that means it is EXTREMELY compressible. Don't compress the output of the formula, just present the formula.

There you go, infinite digits in a small, finite space. You don't get better compression than that.

Re:Students Discover Pattern in Pi Digits: (2)

taliver (174409) | more than 13 years ago | (#2189216)

But I thought the message from God was

Sorry for the inconvenience

Why? There are only 3 digits. (2)

pizen (178182) | more than 13 years ago | (#2189224)

A few years ago, the Texas state legislature official rounded Pi to 3.14 because it was "easier". The have since undone that but just think about what that says about the man leading my country. I didn't vote for him.
---

Re:So what? (2)

Alien54 (180860) | more than 13 years ago | (#2189231)

Can someone tell me some down to earth, real reasons that anyone should care what the 12,345th digit of Pi is? I mean really, who cares?Well for most general engineering purposes 5 to 10 places is enough. How many car parts are manufactured to a milli millimeter spec, for example? and to tell the truth, once you hit the quantum level further precision can get a little silly.

I saw that movie last summer ... (1)

Wordsmith (183749) | more than 13 years ago | (#2189233)

... and I don't think it some random digit he was putting in the pie, if you know what I mean.

Re:So what? (2)

Abcd1234 (188840) | more than 13 years ago | (#2189238)

Is that really the point? This is pure science for the science's sake. What's wrong with that? Besides, one day this knowledge may become useful, who knows? Perhaps, by studying the digits of pi, we'll be able to come up with theories about it's nature. Or, perhaps the pursuit of simplified equations/methods for calculating the digits of pi will lead to other mathematical revelations (just look at this situation... no one thought an equation like the one mentioned in this article was possible). There's no way to tell. I mean, think of all the things people have researched without thinking of practical applications ahead of time. Quantum mechanics, atomic theory, relativity, the myriad forms of pure mathematics such as number theory... and, I'll bet you, all along, people were saying "What's the point of all this? Who cares?" But, because of quantum mechanics, we have computers... because of number theory, we have encryption. So, please, think twice before making comments like this... you never know, one day, the theory behind the nature of Pi may drive the random number generator you use to encrypt your email.

Someone has to say it... (1)

Junior J. Junior III (192702) | more than 13 years ago | (#2189244)

"Easy as pi" takes on new meaning...

nth digit of pi (1)

Ummite (195748) | more than 13 years ago | (#2189247)

I can't exactly remember where, but this is old from at least 3 years.

Re:Base 5 (1)

LoudMusic (199347) | more than 13 years ago | (#2189249)

All your Base 5 are belong to us.

Sorry, couldn't resist (:

~LoudMusic

Re:Site Slashdotted, Alternate link! (1)

el_nino-2000 (200437) | more than 13 years ago | (#2189250)

Incase that link goes down, here is a copy of that article. BERKELEY, CA -- David H. Bailey, chief technologist of the Department of Energy's National Energy Research Scientific Computing Center (NERSC) at Lawrence Berkeley National Laboratory, and his colleague Richard Crandall, director of the Center for Advanced Computation at Reed College, Portland, Oregon, 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. 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. Describing the normality property, Bailey 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 Crandall 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. 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." For more about the normality of pi and other constants, visit David Bailey's website. The BBP algorithm for calculating binary digits of pi was found using the PSLQ algorithm developed by Bailey and mathematician-sculptor Helaman Ferguson; it is discussed at Bailey's website and also in the Fall 2000 issue of Berkeley Lab Highlights. The Berkeley Lab is a U.S. Department of Energy national laboratory located in Berkeley, California. It conducts unclassified scientific research and is managed by the University of California. Contact information: Scientific queries can be addressed to David Bailey at dhbailey@lbl.gov

Site Slashdotted, Alternate link! (3)

el_nino-2000 (200437) | more than 13 years ago | (#2189251)

Lawrence Berkley lab has the orignial story their website [lbl.gov]

Re:To Random or not To Random (2)

11223 (201561) | more than 13 years ago | (#2189253)

That's a bunch of B.S.

In other words, all strings of random numbers have entropy of 1? Nope. Explain to me why I can get this out of a "perfect" random number generator:

000000000000000000000000....

Now, granted, the probability of that is *low*, but it's there just the same.

Now, your statement would work just fine if you were talking about the *complete* digits of PI. In fact, if you give me a stack of disks with a complete listing of all of the digits of PI, I'd be happy to compress it for you.

Re:Why? There are only 3 digits. (3)

L41N14L (205602) | more than 13 years ago | (#2189257)

No-one did. They just rounded up his number of votes. It was easier that way.

To Random or not To Random (1)

Morphine007 (207082) | more than 13 years ago | (#2189266)

here's a simple test... try to compress the "random" string of numbers; if you can compress a string of random numbers, it isn't

Biblical precidence (4)

vslashg (209560) | more than 13 years ago | (#2189273)

pi = 3

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.

1 Kings 7:23

Well, duh! (2)

tswinzig (210999) | more than 13 years ago | (#2189275)

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.

In light of this article, the obvious method is now:

srand(time); #random enough, thank you
$nth_digit = random();


Duh!

Students Discover Pattern in Pi Digits: (4)

tenzig_112 (213387) | more than 13 years ago | (#2189279)

For centuries, mathematicians have called the seemingly random pi digits, "The hidden language of God."

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:

Re:Why? There are only 3 digits. (2)

b1t r0t (216468) | more than 13 years ago | (#2189284)

Nope, that was Kansas. And once they were quietly taken aside and had it explained to them by a math professor, they withdrew the bill.

Re:Why does this matter? (1)

The Troll Catcher (220464) | more than 13 years ago | (#2189288)

Or even better:

Use *base pi*. Why didn't someone think of this before? It would save a LOT of effort... those silly guys!

Now, all we have to do is find out what pi^1 is... oh, wait. :)

Here is the article (4)

rabtech (223758) | more than 13 years ago | (#2189290)

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

Hmmm (1)

James Foster (226728) | more than 13 years ago | (#2189293)

I don't think anything is ever "random".
Everything has its logical base... but alot of things can be way beyond our comprehension and thus can be considered "random".

What do the mean random. (3)

bmongar (230600) | more than 13 years ago | (#2189294)

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

Neumann said ... (5)

(H)elix1 (231155) | more than 13 years ago | (#2189296)

"Anyone who considers arithmetical methods of producing random digits is, of course, in a state of sin."
(John Von Neumann, 1951 )

Hmmm, YABL (Yet, Another, Broken, Link) (2)

gwizah (236406) | more than 13 years ago | (#2189299)

Or is it slashdotted already??

Why does this matter? (3)

Bonker (243350) | more than 13 years ago | (#2189316)

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?

Hate to be a nag, but... (2)

RareHeintz (244414) | more than 13 years ago | (#2189319)

...that algorithm (and variants) have been around [mathsoft.com] for a while.

And does anyone know if that link is incorrect in some way? My DNS can't resolve it.

OK,
- B
--

Pi is great as a random source. (5)

acidblood (247709) | more than 13 years ago | (#2189333)

I did some very interesting work this year with this, in the course of planning a high-quality pseudo-random library. I calculated the first 512 megabits of Pi, and then started splitting up the file in smaller pieces, to study whether they had an "information-theoretic randomness quality". That is, they're not random (you can calculate them), but they exhibit desirable randomness properties, such as uniform statistical distribution.

Here's the output of John Walker's ent [fourmilab.ch] program for 512 megabits of Pi:

Entropy = 7.999997 bits per byte.

Optimum compression would reduce the size of this 67108864 byte file by 0 percent.

Chi square distribution for 67108864 samples is 245.38, and randomly would exceed this value 50.00 percent of the times.

Arithmetic mean value of data bytes is 127.4938 (127.5 = random).
Monte Carlo value for Pi is 3.142281720 (error 0.02 percent).
Serial correlation coefficient is -0.000145 (totally uncorrelated = 0.0).

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.

Re:The signature of the artist ... (1)

Pov (248300) | more than 13 years ago | (#2189337)

It may seem like that, but then you never know until you discover something. Electricity was "just a toy" when it was first being researched. It turned out pretty well. No, I don't know what calculating pi to this extent could possibly produce that would be worth all the effort, and it probably won't be, but then again . . . .

Re:Hmmm (1)

OpCode42 (253084) | more than 13 years ago | (#2189339)

Everything has its logical base

I thought that all your logic base belonged to us...

Zounds!!!! (1)

TigerBaer (264665) | more than 13 years ago | (#2189350)

Quite possibly one of the most significant articles to ever slap slashdot across the face (possibly- i havent read the article yet), and already with a mere 11 comments posted, it is SLASHDOTTED.....

ZOUNDS!!@$!$

Formula for a != message. (1)

KupekKupoppo (266229) | more than 13 years ago | (#2189351)

description of thought.

contradiction or deviation from thought of article.

semi-insightful, semi-obvious, somewhat-karma-whoring conclusion.

(posted after seeing a X != Y on every story for the past day)

Re:Why? There are only 3 digits. (1)

BillX (307153) | more than 13 years ago | (#2189365)

Well, at least Texans can round. In IN they made a (now repealed) law that Pi = 4. I think I saw this on dumblaws.com [dumblaws.com] .

--

Re:lalala (2)

vidarh (309115) | more than 13 years ago | (#2189366)

Why the hell would you want to calculate Pi to a lot of digits? It's been done to an accuracy that nobody needs already. Again and again and again. We don't really need yet another waste of resources.... :)

--

Remove Trash+ to reach my actual inbox

Memorizing Pi... (1)

SirJimbo (320247) | more than 13 years ago | (#2189387)

So does this mean that those people that can recite 500 digits of pi are figuring them out as they go?
That would make it even easier to trip them up in the middle

Who is more foolish, the fool,
or the fool that follows him? (Obi-Wan Kenobi)

So what? (1)

Uttles (324447) | more than 13 years ago | (#2189390)

Can someone tell me some down to earth, real reasons that anyone should care what the 12,345th digit of Pi is? I mean really, who cares?
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Re:So what? (1)

Uttles (324447) | more than 13 years ago | (#2189391)

wouldn't that be a nanometer?
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Re:So what? (1)

Uttles (324447) | more than 13 years ago | (#2189392)

Look, all I'm saying is that after a certain amount of precision it's really useless. If we knew like 100, or maybe 500 digits of Pi that would be enough.
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

I suspect... (1)

gamgee5273 (410326) | more than 13 years ago | (#2189397)

...the answer will be "42."

Kolmogorov complexity (2)

s20451 (410424) | more than 13 years ago | (#2189398)

try to compress the "random" string of numbers; if you can compress a string of random numbers, it isn't

Not really. Since pi is some constant, and not generated by a random process, the most meaningful description of its compressibility is its Kolmogorov complexity, which refers to the shortest program capable of re-generating the original string. Unfortunately, Kolmogorov complexity is not computable in general.

Also depend on compression scheme... (1)

da5idnetlimit.com (410908) | more than 13 years ago | (#2189399)

Depending of your algorithm (repetion, fractal regression,...) you will get VERY DIFFERENT RESULTS using the same original file.

+ PI having no end in itself, can you please send me the method you think you will use before actually compressing pi, and which involve calculating pi to it's end ? 8)

Please call me 5' before World's End, so I can come and check youir results 8)

Low probability ? as in Free - As - Beer ? (1)

da5idnetlimit.com (410908) | more than 13 years ago | (#2189400)

Because a low probability is not a truth in itself.

I also have a LOW probability to win the Lotery 8|
(1/14 600 000, under French Lotery system)

PI IS STATIC AND PREDICTABLE ! (2)

da5idnetlimit.com (410908) | more than 13 years ago | (#2189401)

if not, it could not be used as universal common point.

the famous "Golden Number" is more impressive, I think

Algorithm sources and other stuff (3)

Zarhan (415465) | more than 13 years ago | (#2189402)

At the man's homepage.

http://www.nersc.gov/~dhbailey/ [nersc.gov]

Check out the piqp.c in the middle of the page.

Re:formula for nth digit != random? (1)

the_2nd_coming (444906) | more than 13 years ago | (#2189408)

if they are predictable there has to be a pattern. that is what makes somthing pradictable.

Re:Hmmm (1)

stoolpigeon (454276) | more than 13 years ago | (#2189427)

Seeing this post made me so very happy. I have been trying to explain that nothing is random to others for some time now. People look at me as if I am a little off.

Randomness is the 'god' of the scientific age. We have simply moved from "God did not create the universe- Random did."

People think that randomness is this impersonal force that makes things happen for no reason at all.
What it really is, is an explanation when the factors involved in the outcome are too complicated to grasp.

Re:Students Discover Pattern in Pi Digits: (1)

Captain_Vegetable (470429) | more than 13 years ago | (#2189458)

Pi is exactly 3

memory much? (3)

emoeric (470708) | more than 13 years ago | (#2189460)

"Bailey memorized pi to more than 300 digits 'as a diversion between classroom lectures' while still a graduate student at Stanford"

Where do they find these guys? He memorizes pi, i play snake on my cellphone. eh

|---------------|

Are The Digits of Pi Random? (1)

JimEL (471364) | more than 13 years ago | (#2189461)

Try this link instead: http://www.lbl.gov/Science-Articles/Archive/pi-ran dom.html
Load More Comments
Slashdot Login

Need an Account?

Forgot your password?