Are The Digits of Pi Random? 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.
"
yeth (Score:2)
Eh not really (Score:2)
IANAC(ryptographer), but this isn't quite as "simple" as you make it out, regardless.
Your first assumption is bad, to start with. Someone can always "just use more bits". Since OTP's are usually transported in whole, using a million bits for the offset isn't going to be an unduly burden. You could fit that on a 3.5" floppy with room to spare.
Now, a million bits is a lot of bits. Let's see... 2^(1024*1024) = 6.74e315653, if my calculations are correct. For reference, there are only about 1e130 atoms in the universe. Saying you could do a million comparisons per second (grab the PI subset, XOR, compare with your "known" string), you need 6.74e315647 seconds to search the keyspace (given there are no repetitions in PI). Now, IANAP(hysicist) either, but my guess is that's more time than you've got left in the universe on a good day.
So your third point isn't at all reasonable. And that merely assumes someone is using a single OTP. It also assumes they're using a simple XOR and not doing some convolution to produce multiple resulting pads, etc.
Finally, your forth point is much handwaving. Any given data might be valid. With a OTP, you can't tell! You could probably find many valid headers in even a much more limited keyspace: likely those sequence of bytes could at one offset appear to be a perfectly valid JPEG, the next a word document, the next a random stream of numbers. And who says it isn't the random number stream that's the right one?
So while this may seem like an obvious way to defeat it on the surface, it's much more time consuming and less productive than you might think, especially on arbitrary encrypted data.
IANAM(athemetician) either (I'm a programmer, dagnabit ;-)), but I think the point here is that an arbitrary "slice of PI" is a random sequence. And with the properties of a pad, you're still going to be spending a very long time trying to decrypt it.
floor and pow functions (Score:2)
--
Re:To Random or not To Random (Score:2)
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:
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.
Re:To Random or not To Random (Score:2)
No, that's called a uniform distribution. It's a sufficient, but not necessary condition of randomness. There are plenty of other random distributions.
you are redefining "random".
Not quite. Take at look at the second definition of "random" from dictionary.com [dictionary.com] (the one that's explicitly labeled as the mathematical definition):
And then take a look at this list of probability distributions [znet.com]. You will see that your "definition" of random actually only describes the uniform distribution and that there are plenty of other ways for a variable to be random.Re:To Random or not To Random (Score:2)
Ah, so there's the problem. You specifically said in your first post (and I quote):
That would certainly indicate that you were talking about the mathematical definition of "random" (which doesn't require "an even distribution"). I guess the Slashdot title and description didn't help matters - I don't know why they used the colloquial meaning of "random" in a context where it means something different (the mathematical context).Anyway, my original post was in response to the assertion that you can't compress "a string of random numbers". If the string were an unknown sequence of uniformly distributed random variables, then that makes sense, but that wasn't stated.
Re:To Random or not To Random (Score:2)
This guy [slashdot.org] sounds like he did something similar.
formula for nth digit != random? (Score:5)
-----------------------------------
All that glitters has a high refractive index.
Re:Optimum compression... (Score:2)
Except some of those programs will never halt. And Turing taught us that by simply at a program, you cannot tell whether it will ever halt. You have to run it. And that may take time.
--
Re:This is a clear violation of the DMCA (Score:2)
You've misunderstood something very basic. The fact that something is infinate does not guarentee that it will contain everything. There may be sequences that do not occur.
On the otherhand, once you've located a particular sequence, providing the offset and length may be a good compression algorithm, depending on how efficiently you can store the offset. ;-}
Re:To Random or not To Random (Score:2)
Just one question (Score:2)
Or maybe just rendering 5 min of Jar-Jar galumping around...Shiver
pi vs. /dev/urandom (Score:2)
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.
sligtly OT (Score:2)
If this formula to calculate arbitrary binary digits is derived from being able to calculate pi as a whole, how is it proven that the original formula is valid?
The article discusses a formula now in use that allow computation with less computing power than before...Does this imply that the earlier formulae were flawed such that errors were introduced into the sequence? I'm sure someone would notice some huge error 250 digits in, but, after 250,000? 250,000,000?
Maybe my brain has discarded the answers to these questions and replaced it with PERL syntax or something. So Mathies, please, be kind.
Re:pi vs. /dev/urandom (Score:3)
If it's really low, could we even use /dev/urandom as a seed for the digit choice? Or vice versa?
Re:Also depend on compression scheme... (Score:2)
A previous poster gave a good counter example, but it is very easy to see that if, in base 10, your random numbers are generated by an algorithm which only ever produces digits in the 0-4 range, you can see that there is some scope for compression.
Perhaps it is more easily seen if in base 0xff, you only produce digits in the range 0x0 -> 0xf...so all your random numbers will be of the form:
0? 0? 0? 0?
proof that this is compressible is left as an exercise
Re:Evenly distributed digits (Score:2)
Re:Evenly distributed digits (Score:2)
Evenly distributed digits (Score:4)
I have a way to compute the nth binary digit of PI (Score:3)
involves coin flipping.
Re:Nanocentury (Score:2)
It's a quote by Tom Duff of Bell Labs, who knew he
was using humor to illustrate a point not about Pi, but about the problem of converting time units.
http://users.erols.com/blilly/programming/Progr
Another (this one working) link. (Score:3)
Re:pi vs. /dev/urandom (Score:2)
As long as all the probabilities are greater than 0, even if they vary wildly, all the digits would still appear equally in an infinite set. They would all be infinite.
You can look pretty foolish speaking about the infinite, if you don't know what you're talking about.
Re:Here is the article (Score:2)
You know, this sounds a lot like a certain RPG I was in...
Re:nth digit of pi (Score:2)
http://www.mathsoft.com/asolve/plouffe/plouffe.ht
or for goatse.cx aware:
http://www.mathsoft.com/asolve/plouffe/plouffe.ht
Last I heard, the algorithm only worked in base 16, but that may have changed now.
Re:Biblical precidence (Score:2)
Now clearly, a part of my ignorance is due to my not reading Hebrew. If I did, then I would have a better idea of whether they were able to copy the specs from their contractors without error. But the evidence provided so far doesn't show that.
Caution: Now approaching the (technological) singularity.
Re:Hmmm (Score:2)
Caution: Now approaching the (technological) singularity.
Re:Pi is hardly random. (Score:3)
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.
Re:Cool Application! (Score:2)
It might be better suited as just a commonly known hash. Given some piece of data, such as your login password, reduce it to a number and index into pi that many bits in, and generate N bits of hash. Somehow I doubt it will be as fast (especially for large numbers) as say MD5. But it could be interesting because it can be extended quite easily to as many bits as you want.
Now if that algorithm were faster than MD5 for indexes through 2^128, or faster than SHA1 and RIPEMD160 for indexes through 2^160, then I think we might have a winner.
Re:Hmmm (Score:2)
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:Hmmm (Score:2)
prominent examples are
- three body problem
- weather (all see Lorentz (sp?) equations)
- mandelbrodt set
etc.
Alle this problems have in common that a very small modification to the input may lead to drastic changes on the output.
For instance the three body problem descibes the motion of three bodies (sic!) under mutual gravitational force. Algorithms which want to "predict" the motion of these three bodies have to be very precise, i.e. you have to calculate with something like 100 decimal digits.
Now to the question of randomness. Well, it really isn't easy to find and your believe that it doesn't exist was actually shared by Laplace (mathematican/physician) end of 19th century (I believe). He said something like:
"Give me the state/position of all particles in the universe at one time and I can calculate the state/position at any time in the future or past."
But - later on quantum mechanics was discovered/developed, and still today every scientist belives that there lies real randomness.
This is for instance deductible from Heisenbergs uncertainty principle (sp?).
It's fundamentally _impossible_ to precisely predict speed and position of a given electron. It's fundamentelly impossible to predict when and in which direction an alpha particle will be emitted from a collapsing atom nucleus.
That's why there is the notion of half-life period, thats just the time when the probability is 50% that the alpha particle has been emitted.
Re:Hmmm (Score:2)
This is always the question with scientific theories. I used some sort of shortcut with the word fundamental, read this as "fundamental following the state of todays physics".
Your "lack of information" is called hidden variables and is in itself subject to some theories. And a general consensus is that, yes, that "fundamental" is fundamental.
I did a quick search on google for:
hidden variables quantum mechanics
and found the following nice and short thread which deals with this theme:
http://www2.abc.net.au/science/k2/stn/february2
If you want to read more, just peruse google, there are a lot of nice essays out there - but don't believe everything you read one the internet
Oh, btw., in the light of this laplace citatiton, when I think of the consequences this would have on such nice ideas as "free will", I'm really positive that I like the uncertainty of quantum mechanics more.
Pi is hardly random. (Score:5)
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
--
Neumann is most likely correct (Score:2)
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 (Score:3)
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
--
Re:nth digit of pi (Score:2)
Aren't 'trancendental' and 'non-algebraic' the same thing? I thought they both mean 'not a root of any polynomial with integer coefficients'?
Re:To Random or not To Random (Score:2)
Look at it this way. Let's say you have a conversation between two people. One person (A) is the "generator" of the sequence. Now you seem to have the point of view of (B) where the digits are allegedly "random". But (A) is simply generating digits with a 90% chance of a 0, 10% chance of 1. Is that random?? Of course not. Your definition of random is confusing at best, and let's be straight -- you are redefining "random".
Any mathematically random data cannot be compressed.
Re:To Random or not To Random (Score:2)
If indeed one number had a higher frequency (leading to compression), Pi would cease being "random" in the sense that we have been using it.
Re:Pi is great as a random source. (Score:2)
I though that you could construct Taylor series for functions like arctan(x) and arctan(1) = 1/4*pi, so pi = 4*(ArcTanTaylorSeries(1)).
Prediction, not compression (Score:2)
If we can predict a previously unknown nth decimal of pi, then pi cannot be random.
This is where compression kicks in.... we have compressed pi to the formulae that we use to predict the value of the nth decimal.
I say lets use this algorithm to predict the 2000 billionth decimal, and then get a few beowulf clusters working... if the two values match, then pi cannot be random
Just my £0.02 worth
Re:Why? There are only 3 digits. (Score:2)
Moderation Totals:Troll=1, Total=1.
This moderation brought to you by the Friends of George (FOG)
- - - - -
Randomness of Pi and randomness of its digits (Score:2)
Well, Pi is not random: it's Pi!
Also, the digits of Pi are not "random". It I want to compute the 1024th digit of Pi, I can. So, it's not a random number.
The word "random" might not be the most appropriate here. The question is whether any "substring" of Pi (expressed in any base) appears exactly as frequently as any other substring of the same length.
Re:Not Texas, Indiana (Score:3)
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
Re:Students Discover Pattern in Pi Digits: (Score:2)
Either ally with Him or don't. But don't think that you'll win a fight with God.
Re:Biblical precidence (Score:2)
Numerology can be used to prove anything whatsoever. The fact that some idiot or liar can manufacture the ratio 333/106 from a random biblical verse is not particularly surprising or compelling. Also, one wonders why God in his infinite wisdom didn't encode 355/113, which is a far better approximation to pi.
Incidentally, the website you mentioned (ldolphin.org) is a goldmine for skeptics who wish to discredit Christianity. It is filled with some of the most credulous pseudoscientific bilge that I have ever encountered. He makes Art Bell look like James Randi.
Re:I suspect... (Score:2)
http://www.angio.net/pi/bigpi.cgi?UsrQuery=424242
Searching for a 6-digit, not an 8-digit, string...
Explanation: "random" vs "normal" (Score:2)
--LP
Re:Pi is hardly random. (Score:2)
Re:Bible is more accurate than that actually (Score:2)
And I also found a brief article [straightdope.com] (from a non-religious website) describing how a Jewish rabbi named Nehemiah in ~150 AD first made the argument that the diameter of the tub was 10 cubits from outer rim to outer rim, whereas the 30 cubit circumference was measured around the inner rim.
I wouldn't consider these "proofs," just provocative re-examinations.
--LP
Bible is more accurate than that actually (Score:4)
If the circumference measurement is from inside the brim (or something like that), you get a value for pi that is 0.073% accurate, [teleport.com] well within the significant figures used by Hebrews for measuring at that time.
Not that the bible is a Mathematics text...
--LP
Partly old news (Score:5)
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]
Re:Of course they're not random! (Score:2)
Re:I suspect... (Score:2)
Re:True story. (Score:2)
In Europe, we put the day of the month before the month. I.e. this would be the 11th of May [bbc.co.uk].
True story. (Score:4)
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:What do the mean random. (Score:2)
Let's say you have a string s of length |s|. If the smallest possible Turing machine that can output s has size > |s|, then s is a random string.
On the other hand, if the smallest Turing machine that can output s has size some Turing machine exists that can write down s and yet is smaller than |s|. Thus pi isn't random.
NB: for the other poster who was trying to use information theory to prove pi isn't random, please not that the probability that the nth digit takes on a certain value is now known to be a deterministic function... this may change your results.
Re:formula for nth digit != random? (Score:2)
Supress it as a DMCA violation! (Score:2)
Not Texas, Indiana (Score:5)
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 [straightdope.com].
Of course they're not random! (Score:2)
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.
Re:Students Discover Pattern in Pi Digits: (Score:3)
And they'll be hearing from God's lawyers. This "formula" is clearly a circunvention device.
--
Re:memory much? (Score:2)
Re:Why does this matter? (Score:2)
Random or Non-Linear or Non-Cyclic (Score:2)
If Pi was "random," as apparently the poster of this story is far from anything you would consider a Mathematician or even a "Math intelligent" person, then each time you derived Pi the numbers would be different. e.g. 3.14159... 3.204845... 2.09284...1.38485... You have confused the word "Random" with something it truly is not. The question you are looking for is each time I derive a "new" digit of Pi, will it be predictable, will it be cyclic? That has nothing to do with Pi being random. Because each time you want to derive that certain Nth digit of Pi, it will be the same. That proves Pi is not random, just not cyclic, as of yet.
Re:pi randomness and algorithmic information theor (Score:2)
In the "1,2,3,4" case you are using information about the likely source of the digits to predict the next one (would you still say 5 if you knew the digits were generated by rolling a die?)
All sequences provide no information about the next digit in the sequence unless you know something about the likely method used to generate that sequence.
Re:Pi is great as a random source. (Score:2)
pi = 4 * (1 - (1/3) + (1/5) - (1/7) + (1/9) - (1/11) ... ) doesn't count?
--
Re:Why does this matter? (Score:3)
Re:Why does this matter? (Score:5)
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.
Re:This is a clear violation of the DMCA (Score:3)
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.
Re:Here is the article (Score:2)
Isn't that supposed to be ln(2)?
--
Re:Students Discover Pattern in Pi Digits: (Score:2)
lalala (Score:2)
Peace,
Amit
ICQ 77863057
More info on the Algorithm (Score:5)
I couldn't get the link in the story to work, and found this while searching for the story.
Re:To Random or not To Random (Score:2)
To do valid compression with huffman coding, you first need to determine frequency of occurance. But, the frequency of occurance is all you want in this case - why finish the job of building the tree?
Actually, arithmatic compression is much better. If you're not familiar with it, it is a probabilistic way of storing bits, where, the better you know the probabilities, the better you can do. Worst case, its compression is equivalent to huffman coding. Best case, the sky is the limit, it depends on your knowledge. I have an interesting application I want to try some time using huffman coding to store MDCT blocks
Any signal compression algorithms already use arithmatic encoding? Anyone know?
-= rei =-
Re:Cool Application! (Score:2)
Also the range of characters used is often very limited - simply decoding a few characters with every sequence, and see whether it would give you any characters outside the expected set would let you throw away a huge number of starting points very quickly.
This problem is easy enough to solve. Just gzip before you encrypt. Then they might look for the gzip magic number, but you can exclude that too. The only real problem would be if gzip uses a "dictionary". They might be able to pick words out of that. So, gzip might not be the ideal choice but I'm sure there must be some compression method that produces statisticly random results, even in the early part of the file.
Re:Biblical precidence (Score:5)
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".
Re:This is a clear violation of the DMCA (Score:4)
Cool Application! (Score:5)
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.
from the article (Score:2)
I thought this was not only extremely difficult, but actually impossible. Pi is proven to be irrational many years ago now. I thought it had also been proven (also many years ago) that you cannot ever know the Nth digit of a irrational number without computing the N-1 first. I also remember an earlier slashdot discussion when some 20 year old had calculated the trillionth digit of pi using some distributed scheme. Naturally, some poster wanted to know whether he had calculated the trillion-1 digits before that one also, and he got instaniously drenched by replys claiming and proving that such a feat is impossible, so at least I'm not the only one having heard this.
Could some math grad with knowledge about this help clear it up?
Re:Students Discover Pattern in Pi Digits: (Score:2)
I can't win with God? Guess I'll just have to fight without him, then
Encryption II (Score:2)
But...
With using pi, the fun part comes when you tell someone that the encrypted data they're trying to break has just been xor'd with pi at different starting points a few times, and that you don't feel like telling them the starting points
Even better - the starting points could be taken as a integer equivalent of say an MD5 hash of each of three thirds or four quarters of the password you used
I'd personally hate to be the cryptographer trying to break into your data when the keyspace is potentially infinite depending on password length
...All I want for Christmass (3042) is the look on their face when they hit the last 2048bit key and still can't get to my pr0n...
Re:Students Discover Pattern in Pi Digits: (Score:2)
Sorry for the inconvenience
Re:True story. (Score:2)
1337 indeed.
Re:No! No! No! (Score:2)
Anyone who wants a good source of xor'ing digits for their encryption program. Just carve them into groups of 8 (or 16 or whatever you need).
TWW
Re:No! No! No! (Score:2)
TWW
Site Slashdotted, Alternate link! (Score:3)
Re:Why? There are only 3 digits. (Score:3)
Biblical precidence (Score:4)
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.
Students Discover Pattern in Pi Digits: (Score:4)
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:True story. (Score:5)
Wow, Pi is Leet!
Here is the article (Score:4)
===
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
What do the mean random. (Score:3)
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 ... (Score:5)
(John Von Neumann, 1951 )
This is a clear violation of the DMCA (Score:5)
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
Why does this matter? (Score:3)
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?
Why Curisoty Based Research? (Score:4)
Robert Moody from the Department Mathematical Sciences, University of Alberta illustrates the importance of curiosity based research in his paper [math.mun.ca] 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.
Pi is great as a random source. (Score:5)
Here's the output of John Walker's ent [fourmilab.ch] 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.
Re:Cool Application! (Score:3)
For instance, if I were looking for JPEG or Word files, I could look for common headers by:
1) Making an assumption about the maxium size of the key (the starting point in the Pi sequence), and 2) Take X bytes of known header information from each of a set of file formats, 3) Find every starting point in the Pi sequence that when XOR'd with the characters in the known headers produced the same data as in the start of your encrypted file, 4) proceed to see if I get valid data from continuing onwards from the starting points identified.
Even if it's an unstructured file format like plain text, I still believe that you'd be able to do "interesting" analysis of the file based on statistical facts about plain text - the occurence of characters have clear statistical properties and patterns in different languages.
Also the range of characters used is often very limited - simply decoding a few characters with every sequence, and see whether it would give you any characters outside the expected set would let you throw away a huge number of starting points very quickly.
And since XOR'ing a non-random sequence with a "random" sequence of digits gives the result non-random properties. XOR'ing it again with another random sequence may obscure that (but it also poses a certain chance of actually totally reversing your initial operation), but not totally, and it may also weaken your initial operation for whole or parts of the file.
Actually in that respect, you could have taken any good pseudo random number generator, and done almost the same thing as you suggest: The "starting point" is essentially just a seed.
I'm not a cryptographer (not even on hobby basis) nor a mathematician (haven't touched a math book since my first term in University, thank you). When there's weaknesses obvious enough that I can see it like that, then I'm sure that someone who actually knows anything about cryptography can find a lot more problems with it.
--
Remove Trash+ to reach my actual inbox
Algorithm sources and other stuff (Score:3)
http://www.nersc.gov/~dhbailey/ [nersc.gov]
Check out the piqp.c in the middle of the page.
memory much? (Score:3)
Where do they find these guys? He memorizes pi, i play snake on my cellphone. eh
|---------------|