Forgot your password?
typodupeerror
Science

Are The Digits of Pi Random? 478

Posted by Hemos
from the answering-the-age-old-question dept.
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. "
This discussion has been archived. No new comments can be posted.

Are The Digits of Pi Random?

Comments Filter:
  • by Anonymous Coward
    pi = 3
  • 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.

  • Okay, could someone clue me in as to where the floor() and pow() functions are, so I can compile this and try it out? According to the man pages (RedHat 7.0) they're in math.h, but they're not!
    --
  • 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.

  • Huh? For the sequence to be random, each subsequent outcome must have an equal probability of occurring. That is, each subsequent digit must have an equal likelihood of being a zero or a one.

    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):

    Of or relating to a type of circumstance or event that is described by a probability distribution.
    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.
  • We were using the sense of random that they had an even distribution.

    Ah, so there's the problem. You specifically said in your first post (and I quote):

    Any mathematically random data cannot be compressed.
    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.

  • Did anyone ever Huffman-code, winzip, run-length, or otherwise the first billion... digits of PI to see if they compressed at all?

    This guy [slashdot.org] sounds like he did something similar.

  • 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.
  • Here's a neat (albeit *extremely* slow) idea: whip up a small (lisp? scheme?) program to generate all correctly-formed C programs without any string constants and exactly one function putc(), smallest to larger, and compile them all, and see exactly which ones output your file.

    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.

    --

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

    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. ;-}

  • A pattern is also evidence that the compression could be better.
  • 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

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

  • How do we know the calculated values of pi are correct? The 56 millionth place, for instance...Who's checking this work? It can't be done by hand, only by another computer, right?

    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.

  • by boinger (4618) <boinger@nOsPaM.fuck-you.org> on Friday July 27, 2001 @07:02AM (#2189018) Homepage
    I understand that - I was asking as to the algorhythm used to generate /dev/urandom. Is this formula for binary digits of pi as low-resource intensive as the /dev/urandom formula?

    If it's really low, could we even use /dev/urandom as a seed for the digit choice? Or vice versa?

  • Even taking your result as valid, the assumption you make is that the random numbers occur all over your possible inputs.

    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 :-)
  • Er... I think that is what I was saying...
  • That was my guess. Looking back at it, I probably didn't write quite as clearly as I should have... Oh, well.
  • by cluening (6626) on Friday July 27, 2001 @06:37AM (#2189024) Homepage
    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...
  • by Leimy (6717) on Friday July 27, 2001 @07:51AM (#2189025)
    Its got a 50% chance of being correct though and
    involves coin flipping.


  • 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/Progra mm ing_Pearls.html
  • So, if you were to take an infinite number of digits of Pi, each of the digits would appear an equal number of times.

    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.

  • "It's like throwing a fair, ten-sided die forever and counting how often each side or combination of sides appears."

    You know, this sounds a lot like a certain RPG I was in...
  • 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.
  • Well, I don't read Hebrew, so I can't check on what he is saying. However even the appologist didn't translate it into a mathematical formula. He just did a bit of gematria and waved his hands. Now it's clearly true that the Babylonians at that time had a good understanding of PI (relatively), and that they did use the kind of fraction that you are implying the Hebrews used. And they were hired contractors on the job that is being written of. But even putting this all together, I can't make it say that the biblical scribes were able to cope with the Babylonian knowledge. The do seem to have caught on that certain numbers were important (the Babylonians started doing their math with balances, so they were whizes with rational fractions), but I can't see, from what has been said, that the Hebrews knew why the numbers were important, or even which number divided which (or what division meant).

    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.
  • OK. Use 0x00 or 0xff. Now it's a real world case.

    Caution: Now approaching the (technological) singularity.
  • by HiThere (15173) <charleshixsn@@@earthlink...net> on Friday July 27, 2001 @08:08AM (#2189040)
    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.
  • 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.


  • 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.
  • Deterministical Chaos is exactly that what you described, i.e. the outcome of a process depends in a non-continous manner from the input data.
    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.

  • But will it always be impossible? Or do we just think it is impossible because we lack information and understanding?

    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/february20 00 /posts/topic37229.shtm

    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 ;), this is an area which seems to have a strong attractivity for, hmm, exotic people and ideas.

    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.
  • by KFury (19522) on Friday July 27, 2001 @07:26AM (#2189052) Homepage
    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
    --
  • 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...
  • by PigleT (28894) on Friday July 27, 2001 @06:02AM (#2189063) Homepage
    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,
  • (I'm a geographic group theorist, not a number theorist :)

    Aren't 'trancendental' and 'non-algebraic' the same thing? I thought they both mean 'not a root of any polynomial with integer coefficients'?
  • Huh? For the sequence to be random, each subsequent outcome must have an equal probability of occurring. That is, each subsequent digit must have an equal likelihood of being a zero or a one.

    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.
  • You said something about Pi, that if one number had a higher frequency, it could be compressed while still being random. Well, the sense of random that we were using is a random probability distribution. The digits of Pi are not random in the sense that they are calculated by some random means. They can be calculated. We were using the sense of random that they had an even distribution.

    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.
  • 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 think all the compression people are missing the point.

    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

  • "With just one more execution, he'll be eligible for the governorship of Texas!"

    Moderation Totals:Troll=1, Total=1.

    This moderation brought to you by the Friends of George (FOG)



    - - - - -
  • Many posts are talking about Pi being random.
    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.
  • by Trailer Trash (60756) on Friday July 27, 2001 @08:10AM (#2189092) Homepage
    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
  • No. The true, message of god is "all your base are belong to us".

    Either ally with Him or don't. But don't think that you'll win a fight with God.
  • 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.

  • The corrected URL:

    http://www.angio.net/pi/bigpi.cgi?UsrQuery=424242& startpos=242423

    Searching for a 6-digit, not an 8-digit, string...
  • Technically, it's not conjectured to be "random"; it's conjectured to be "normal", which means that there's an even distribution of the digits 0-9 (in base 10) or 0 and 1 (in base 2).

    --LP
  • Yeah. The proper term is "normal", not "random", but if the Slashdot poster/editors said that, they'd probably have gotten a lot of blank stares from the number-theory-unfamiliar people. Ah well.
  • OK, more diligent searching turned up a couple variants of the "Bible's pi is actually more accurate than 3.0" from a non-Boatwright source, with a nice nice visual diagram [answersingenesis.org].

    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

  • You forgot verse 26: "It [the rim] was a handbreadth in thickness..."

    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

  • by LinuxParanoid (64467) on Friday July 27, 2001 @06:20AM (#2189104) Homepage Journal
    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]

  • The use of the word random when referring to Pi may be somewhat of a misnomer. It's not that the number Pi itself is random... it's the ratio of a circle's circumference to its diameter. The randomness (or random-like behavior) is in the digits, specifically, predicting the next one. There seems to be no pattern, much less a repeated pattern in the digits of Pi that is consistent throughout the number.

  • And the question would be What do you find at position 242424 of pi [angio.net]?
  • > I don't get it. What does "115" have to do with a spooky coincidence?

    In Europe, we put the day of the month before the month. I.e. this would be the 11th of May [bbc.co.uk].

  • by BlueUnderwear (73957) on Friday July 27, 2001 @06:27AM (#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...).

  • The meaning of randomness has to do with Kolmogorov complexity. While Kolmogorov was primarily a statistician, Kolmogorov complexity could actually be considered a topic in theoretical computer science.

    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.
  • It seems to me amazing how many people find this a difficult point. Yes, everybody knows that pi is not a random number. The question, "Are the digits of pi random?" is merely a short-hand way of asking, "Is there any way of distinguishing a sequence of digits from the expansion of pi from a random sequence of digits other than by comparing it to the digits of pi?"
  • If you look long enough, you should be able to find all the Metallica songs, every work of literature, decss and every movie ever made in pi. As such, this work should be suppressed as a DMCA violation!
  • by sg3000 (87992) <sg_public.mac@com> on Friday July 27, 2001 @07:05AM (#2189125)
    Although I wouldn't put it past Dubya to legislate pi to a particular value -- this is the guy that doesn't believe Social Security is a Federal program, and his party has been trying to legislate the story of biblical creation as science for decades -- it was actually Indiana where this happened.

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


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

  • And today, thanks to the hard work of a pair of students at Carnegie Mellon University, we can read that language.

    And they'll be hearing from God's lawyers. This "formula" is clearly a circunvention device.

    --

  • Hey I once derived the quadratic formula while sitting in calc @ class simply because the lecture was so boring, that the derivation was more interesting than anything els i could do at the time ( i had already gotten bored with doodling ;-)
  • in base pi, pi= 10. not exactly random. Therefore, pi is not random in all bases.

  • 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.
  • For an example, consider the sequence "1,2,3,4". Most people would predict the next digit to be "5".
    However if I was presented with the numbers "3, 1, 4, 1" and asked to predict the next number I would probably say "5".

    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.

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

    pi = 4 * (1 - (1/3) + (1/5) - (1/7) + (1/9) - (1/11) ... ) doesn't count?

    --

  • by Leto2 (113578) on Friday July 27, 2001 @08:12AM (#2189146) Homepage
    Does a base have to be an integer? If not, pi in base(pi) is 10 exactly.
  • by (void*) (113680) on Friday July 27, 2001 @07:55AM (#2189147)
    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?
    How is this insightful?

    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.
  • the natural logarithm of 2, often written "log(2)"

    Isn't that supposed to be ln(2)?

    --
  • Actually, "We apologise for the inconvenience."
  • 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
  • by regen (124808) on Friday July 27, 2001 @06:06AM (#2189162) Homepage Journal
    Can be found at http://www.lbl.gov/Science-Articles/Archive/pi-alg orithm.html [lbl.gov].

    I couldn't get the link in the story to work, and found this while searching for the story.

  • That would be pointless.

    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 :) Hey, you know the odds of a certain signal having various frequency components! And, you know the total amount of retained frequency in that block. Put the two together... you have very accurate probabilities :) You might get an extra 5% out of sound and 15% out of images (and even more out of video if it uses 3d transforms instead of layered 2d transforms).

    Any signal compression algorithms already use arithmatic encoding? Anyone know?

    -= rei =-
  • 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.

  • by istartedi (132515) on Friday July 27, 2001 @10:22AM (#2189168) Journal

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

  • Since pi predates the DMCA and everything 'protected' under it, pi must count as 'prior art', invalidating ALL copyright and patent claims.
  • by FreezerJam (138643) <smith@@@vex...net> on Friday July 27, 2001 @06:12AM (#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.

  • 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

    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?

  • > But don't think that you'll win a fight with God

    I can't win with God? Guess I'll just have to fight without him, then ;)
  • Any (irrational, nonrepeating) number which we can get the nth digit of by a straightforward, direct formula, that exhibits close-to-randomness would work for the purposes of encryption...

    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 :) Rubbing it in their faces that it's just xor'd with pi would just be icing on the cake :)

    ...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...
  • But I thought the message from God was

    Sorry for the inconvenience

  • Also to be noted, 31337 occurs at the palindromic position 12022021 [angio.net].

    1337 indeed.
  • Who cares what pi is in binary?

    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

  • The ability or otherwise to translate from the binary digits is of no impact to someone looking for random data for encryption; taking 8 digits and converting them to an ASCII value is clearly nothing to do with getting the decimal data, but it's still what you need for XORing plain text.

    TWW

  • by el_nino-2000 (200437) on Friday July 27, 2001 @06:14AM (#2189251)
    Lawrence Berkley lab has the orignial story their website [lbl.gov]
  • by L41N14L (205602) on Friday July 27, 2001 @06:13AM (#2189257)
    No-one did. They just rounded up his number of votes. It was easier that way.
  • by vslashg (209560) on Friday July 27, 2001 @06:18AM (#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

  • by tenzig_112 (213387) on Friday July 27, 2001 @06:01AM (#2189279) Homepage
    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:

  • by rabtech (223758) on Friday July 27, 2001 @06:17AM (#2189290) Homepage
    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
  • by bmongar (230600) on Friday July 27, 2001 @06:19AM (#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

  • "Anyone who considers arithmetical methods of producing random digits is, of course, in a state of sin."
    (John Von Neumann, 1951 )
  • by GMFTatsujin (239569) on Friday July 27, 2001 @07:19AM (#2189305) Homepage

    Consider:

    1. All computer code can be represented as a series of ons and offs, typically interpreted as 1's and 0's
    2. Any series of 1's and 0's can be interpreted as a base 2 form of some integer x
    3. Pi contains an infinitely variable series of digits which, in chunks, can be taken as integers
    4. Pi is infinite and non-repeating, and therefore contains every possible combination of every integer in the infinite set (some mathbrained guru can feel free to slap me down on this)

    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

  • by Bonker (243350) on Friday July 27, 2001 @06:09AM (#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?

  • by JohnDenver (246743) on Friday July 27, 2001 @07:04AM (#2189321) Homepage
    "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 [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.
  • 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.

  • by vidarh (309115) <vidar@hokstad.com> on Friday July 27, 2001 @07:17AM (#2189370) Homepage Journal
    It has the slight little weakness that you need to transmit the key in some form. Which means that the attacker can reasonably assume that the starting point won't be too high. If the attacker knows *anything* about the content being sent, the mechanism is also vulnerable to the attacker doing guesses about what to expect, and use that to verify whether or not he's achieving success.

    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

  • by Zarhan (415465) on Friday July 27, 2001 @06:09AM (#2189402)
    At the man's homepage.

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

    Check out the piqp.c in the middle of the page.
  • by emoeric (470708) on Friday July 27, 2001 @06:08AM (#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

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

You can measure a programmer's perspective by noting his attitude on the continuing viability of FORTRAN. -- Alan Perlis

Working...