Slashdot Mirror
Are The Digits of Pi Random?
Steve Hamlin writes "A researcher at Lawrence Berkeley National Laboratory, and his colleague at the Center for Advanced Computation at Reed College, have taken a major step toward answering the age-old question of whether the digits of pi and other math constants are "random."
In addition, a simple formula discovered makes it possible to calculate the Nth binary digit of Pi without computing any of the first N-1 digits, and do the computation with very little computing power.
"
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.
Don't think of it as a flame---it's more like an argument that does 3d6 fire damage
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!
--
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.
-----
Free P2P Backup, Windows & Linux
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 (the one that's explicitly labeled as the mathematical definition):
And then take a look at this list of probability distributions. 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.-----
Free P2P Backup, Windows & Linux
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.
-----
Free P2P Backup, Windows & Linux
This guy sounds like he did something similar.
-----
Free P2P Backup, Windows & Linux
I was wondering the same thing...BUT. I think we're looking at this the wrong way. the number are not, and have never been, and are in no danger or question of BEING, truly random. they're there, they're set, and it's done. the question is "is there a pattern"? and so, the formula does not automatically force there to be a pattern, just forces us to realize that they're static and predictable.- ----------
-----------------------------------
All that glitters has a high refractive index.
You see, without that little doohicky, the universe stops.
http://propheteer.org
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.
--
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.
Or maybe just rendering 5 min of Jar-Jar galumping around...Shiver
Novel theory: Modern Man evolved from psychopath
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.
Send your friends messages of love at fuck-you.org
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.
Send your friends messages of love at fuck-you.org
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...
Posted from the wireless couch.
That was my guess. Looking back at it, I probably didn't write quite as clearly as I should have... Oh, well.
Posted from the wireless couch.
I whipped up a little perl script earlier this summer that a friend and I used to informally prove to ourselves that the digits 0..9 are fairly evenly distributed in the first million digits of pi. I guess that doesn't really have anything to do with the randomness of their positions, but it didn't look like there are, for example, significantly more 5's than 8's in there...
Posted from the wireless couch.
Its got a 50% chance of being correct though and
involves coin flipping.
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
-fb Everything not expressly forbidden is now mandatory.
http://www.lbl.gov/Science-Articles/Archive/pi-ran dom.html
"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:
m l,
m l
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.
:wq!
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.
I think we've pushed this "anyone can grow up to be president" thing too far.
OK. Use 0x00 or 0xff. Now it's a real world case.
Caution: Now approaching the (technological) singularity.
I think we've pushed this "anyone can grow up to be president" thing too far.
Perhaps. But it's a nice tool to beef up your rot-13 substitution cypher.
:-)
What you want is, say, a 1 MB block of the digits of PI expressed in base 256. Then you pick a starting position, and for each byte that you transfer, you rot it by the value of the corresponding byte.
P.S.:
Caution: Now approaching the (technological) singularity.
I think we've pushed this "anyone can grow up to be president" thing too far.
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.
now we need to go OSS in diesel cars
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?
0 00 /posts/topic37229.shtm
;), this is an area which seems to have a strong attractivity for, hmm, exotic people and ideas.
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.
A lot of people are playing fast and loose with the word 'random' today. The value of Pi, in whole or of any one digit, isn't random at all. It's entirely deterministic, defined rigidly by a simple formula. No matter how many times or ways that formula is interpreted, the value of Pi is the same, and not random.
What can be said to be 'random' (really pseudorandom or, in the parlance of mathematicians, 'random enough') is an arbitrary digit or sequence of digits from pi, given that the starting decimal place N is also random, or at least non-repeating. The randomness of pi is that each succeeding digit of Pi has no correlation to the preceding digit.
Of course we all know this inherently, but it wouldn't hurt to be a little clearer in these posts about exactly what is random (or not) about Pi.
Kevin Fox
--
Kevin Fox
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...
[ Antti Rasinen ]
Yes, that's a good philosophical position..
.|` Clouds cross the black moonlight,
I'm just wondering, if there's a "formula" for the n'th bit of the thing, it *can't* be random, can it?
For values of `random' that mean `uncompressible' of course, it can probably rate pretty highly.
~Tim
--
~Tim
--
Rushing on down to the circle of the turn
(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'?
-- Help Digitise the Public Domain at DP.
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
Live today. Tomorrow will cost a lot more!
"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)
- - - - -
Napster-to-go says "Fill and refill your compatible MP3 player", which is a lie. It's not MP3. It's WMA with DRM.
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.
Another good reference is in Chapter 17 of "A History of PI" by Petr Beckman (ISBN 0-88029-418-3). Beckman goes so far as to include a reproduction of the bill.
The bill doesn't actually give any values for PI directly. Rather, it supposes to provide simple formulas for computing the value of PI based on enclosing squares. Here's part of section 1:
"It has been found that the cirular area is to the quadrant of the circumference, as the area of an equilateral rectable is to the square on one side."
And later in section 2:
"By taking the quadrant of the circle's circumference for the linear unit, we fulfill the requirements of both quadrature and rectification of the circle's circumference. Furthermore, it has revealed the ratio of the chord and arc of ninety degrees, which is as seven to eight, and also the ratio of the diagonal and one side of a square, which is as ten to seven, disclosing the fourth important fact, that the ratio of the diameter and circumference is as five-fourths to four, and because of these facts and the further fact that the fule in present use fails to work both ways mathematically, it should be discarded as wholly wanting and misleading in practical applications."
Now, there are about three different "values" for PI in there. Dr. Edwin Goodman, who came up with this tripe, was a "circle-squarer", one who thought PI could be computed, well, easily.
It's scary that the guy was a doctor given his profound misunderstanding of simple geometry, and seeming inability to do the simple measurements which would prove his theories wrong.
But this bill is much bigger in folklore than in real life. Some facts regarding it:
1. It was never passed in to law. Ever. It passed unanimously in the House, and was tabled in the Senate, and never voted on there.
2. It doesn't say that PI=3, PI=3.14, or that PI is equal to any other simple number. Rather, it gives a number of methods (all of which are grossly incorrect) that could be used to very easily calculate PI.
3. It never made it into any textbooks that I know of. That was the goal of Dr. Goodman.
4. It did happen in Indiana, 1897, House Bill No. 246
5. Dr. Goodman, in section 3 of the bill, also claims to have previously trisected an angle. The guy was either a fruitcake or a charlatan.
Michael
Do you have ESP?
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:
& startpos=242423
http://www.angio.net/pi/bigpi.cgi?UsrQuery=424242
Searching for a 6-digit, not an 8-digit, string...
.... um, i lost you after "0110100001101001".
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
And I also found a brief article (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
If the circumference measurement is from inside the brim (or something like that), you get a value for pi that is 0.073% accurate, well within the significant figures used by Hebrews for measuring at that time.
Not that the bible is a Mathematics text...
--LP
There was a distributed computing project called PiHex that lasted several years for computing the five trillionth, 40 trillionth, and the quadrillioth bit of Pi, using a variant of the Plouffe discovery, Bellard's formula.
A proof that digits of Pi are random would indeed be news, albeit not exactly a surprise; I'd comment on it but the article's link seems bad or swamped at the moment.
--LP
P.S. Google has a nice list of Pi links.
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.
"The best laid plans of mice and men gang oft agley..." - ROBERT BURNS
And the question would be What do you find at position 242424 of pi?
Say no to software patents.
In Europe, we put the day of the month before the month. I.e. this would be the 11th of May.
Say no to software patents.
For an even more spooky coincidence, click twice on Find Next, and carefully note the 3 last digits of the error message (start position...).
Say no to software patents.
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.
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!
I'm trying to teach myself to set people on fire with my mind... Is it hot in here?
in 1897 Representative T.I. Record introduced House Bill 246 suggesting three values for pi: 3.2, 4, and ~3.23. These three figures were based on the work of an amateur mathematician Edward Goodwin. The bill was quickly forwarded to the Committee on Swamp Lands (of course), which then forwarded it to the Committee on Education. This committee gave it a pass, where the House approved it unanimously. The bill made it to the Senate.
Before the Senate could make asses of themselves as well, a professor of mathematics at Purdue named C.A. Waldo, intervened, and it died an embarrassing death.
For a more humorous account, read Cecil Adam's account of this at the Straight Dope.
Insert simplistic political, ideological, or personal proselytization here.
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 they'll be hearing from God's lawyers. This "formula" is clearly a circunvention device.
--
--
Stay tuned for some shock and awe coming right up after this messages!
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.
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.
pi = 4 * (1 - (1/3) + (1/5) - (1/7) + (1/9) - (1/11) ... ) doesn't count?
--
Please consider making an automatic monthly recurring donation to the EFF
Does a base have to be an integer? If not, pi in base(pi) is 10 exactly.
<grub> Reading
Suppose there is some base b such that the digits of repeat. Then Pi * b * m = n where m and n is some integer. And so we would have Pi = n / b *m. But m and n are integers, as is b. So you've just shown that Pi is a rational number. It is not. Hence, no such base exists.
The value of the starting position for any useful work would be such a large number that simply expressing the number would in almost all cases take far more bytes than to store the work itself (barring some infinitesimally unlikely occurrence, which is just as unlikely as finding the work randomly occurring in any other form in nature, such as twigs falling from a tree and arranging, just by random luck, into letters and spelling a message). In fact, since the stream of digits of pi is infinitely long, not only can every work that has ever, does, and will ever exist be found in it, but every single work must lie buried an infinite number of times! For any work, you could come up with as many numbers as you want to describe its position.
Small numbers indicating a quantity cannot be copyrighted, but the numbers necessary to express these digit positions would be far beyond any useful quantity imaginable. Just as all digital data is reducible to a long number, these digit positions are encoded data, not useful quantities, and therefore would be protected by copyright as just a representation of the works they are "pointing" to in the digits of pi.
the natural logarithm of 2, often written "log(2)"
Isn't that supposed to be ln(2)?
--
Actually, "We apologise for the inconvenience."
Vintage computer games and RPG books available. Email me if you're interested.
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
[o]_O
I couldn't get the link in the story to work, and found this while searching for the story.
The Economics of Website Security
That would be pointless.
:) 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).
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 =-
"Well, then fire it up and show me what this..." (sigh)
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.
For all intensive purposes, "whom" is no longer a word. That begs the question, "who cares"?
Well, if you're going to be using "cubits", it's not like precision is really a concern to begin with. IIRC, The cubit was the distance from the elbow to the tip of the longest finger. Whoever was ruler at the time set the standard. It would be interesting to see how close we could come doing it by hand, or with a "cubit-stick".
For all intensive purposes, "whom" is no longer a word. That begs the question, "who cares"?
Since pi predates the DMCA and everything 'protected' under it, pi must count as 'prior art', invalidating ALL copyright and patent claims.
If it is possible to calculate digits of Pi starting at any point, then you could easily use Pi as a pseudo-random pad.
Once you know the starting digit location, you can easily decrypt something that has been XOR'd with the sequence from that point onward. But - given that each n-bit sequence occurs 1/n of all n-bit sequences, there are essentially an infinite number of options facing the code-breaker - even after each successful step!
If you are feeling particularly vicious that day, encrypt with two XOR sequences, based on two difference starting points.
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?
"If you think education is expensive, try ignorance" - Derek Bok
> 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
OtakuBooty.com: Smart, funny, sexy nerds.
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...
:)
:)
:) Rubbing it in their faces that it's just xor'd with pi would just be icing on the cake :)
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...
HelpGeeks - don't bother visiting, it's not worth it! Really!
Sorry for the inconvenience
I demand a million helicopters and a DOLLAR!
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
"Encyclopedia" is to "Wikipedia" what "Library" is to "Some people at a bus stop"
TWW
"Encyclopedia" is to "Wikipedia" what "Library" is to "Some people at a bus stop"
Ah, well, in that case it's all subjective. I think it's cool and you don't. Personally, I don't like Mozart but plently of people do. That's the trouble with sociology (and the other soft-sciences): no one is ever wrong (or right).
TWW
"Encyclopedia" is to "Wikipedia" what "Library" is to "Some people at a bus stop"
A few years ago, the Texas state legislature official rounded Pi to 3.14 because it was "easier". The have since undone that but just think about what that says about the man leading my country. I didn't vote for him.
---
Heh. "Pi"-racy.
--
I feel fantastic, and I'm still alive.
Can someone tell me some down to earth, real reasons that anyone should care what the 12,345th digit of Pi is? I mean really, who cares?Well for most general engineering purposes 5 to 10 places is enough. How many car parts are manufactured to a milli millimeter spec, for example? and to tell the truth, once you hit the quantum level further precision can get a little silly.
"It is a greater offense to steal men's labor, than their clothes"
there's also the problems that in order to store one bit of information you need a bit to store it in. so in order to store all the information in the universe, your computer has to be the universe. reading the results from this program would not only be impossible (since you'd have to also be part of the computer/universe) but would also not be very useful, since what you were trying to predict would aredy have happened.
Is that really the point? This is pure science for the science's sake. What's wrong with that? Besides, one day this knowledge may become useful, who knows? Perhaps, by studying the digits of pi, we'll be able to come up with theories about it's nature. Or, perhaps the pursuit of simplified equations/methods for calculating the digits of pi will lead to other mathematical revelations (just look at this situation... no one thought an equation like the one mentioned in this article was possible). There's no way to tell. I mean, think of all the things people have researched without thinking of practical applications ahead of time. Quantum mechanics, atomic theory, relativity, the myriad forms of pure mathematics such as number theory... and, I'll bet you, all along, people were saying "What's the point of all this? Who cares?" But, because of quantum mechanics, we have computers... because of number theory, we have encryption. So, please, think twice before making comments like this... you never know, one day, the theory behind the nature of Pi may drive the random number generator you use to encrypt your email.
Lawrence Berkley lab has the orignial story their website
In other words, all strings of random numbers have entropy of 1? Nope. Explain to me why I can get this out of a "perfect" random number generator:
000000000000000000000000....
Now, granted, the probability of that is *low*, but it's there just the same.
Now, your statement would work just fine if you were talking about the *complete* digits of PI. In fact, if you give me a stack of disks with a complete listing of all of the digits of PI, I'd be happy to compress it for you.
I could write a C program in those constraints to generate 256MB of PI digits that's a heckofalot smaller than 256MB. In fact, this little bit would find the *smallest* such program to do so.
Slow as hell, though ;-) Maybe if you had a quantumn computer and only a 720KB floppy to transfer files with...
Program must be primitive recursive. All non-deterministic programs to generate a specific sequence can be written out step by step, so this doesn't really remove anything from the bounds. Now, it does remove some *faster* programs, but certainly not any hope of compression.
I suppose this gets less and less useful as I add more and more constraints.
Wacko thought: I suppose there is one number theory statement X whose interpretation is that there are no general recursive algorithms shorter than X (using Godel numbering, smaller) that output X.
No-one did. They just rounded up his number of votes. It was easier that way.
And he made a molten sea, ten cubits from the one brim to the other: it was round all about, and his height was five cubits: and a line of thirty cubits did compass it round about.
In addition, a simple formula discovered makes it possible to calculate the Nth binary digit of Pi without computing any of the first N-1 digits, and do the computation with very little computing power.
In light of this article, the obvious method is now:
srand(time); #random enough, thank you
$nth_digit = random();
Duh!
"And like that
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:
Nope, that was Kansas. And once they were quietly taken aside and had it explained to them by a math professor, they withdrew the bill.
--
"Open source is good." - Steve Jobs
"Open source is evil." - Microsoft
Since the website seems to be /.ed, I give you the article:
===
Are the Digits of Pi Random? A Berkeley Lab Researcher May Hold the Key
A researcher at the Department of Energy's National Energy Research Scientific Computing Center (NERSC) at Lawrence Berkeley National Laboratory, and his colleague at the Center for Advanced Computation at Reed College, have taken a major step toward answering the age-old question of whether the digits of pi and other math constants are "random." Their results are reported in the Summer 2001 issue of Experimental Mathematics.
July 26--Pi, the ubiquitous number whose first few digits are 3.14159, is irrational, which means that its digits run on forever (by now they have been calculated to billions of places) and never repeat in a cyclical fashion. Numbers like pi are also thought to be "normal," which means that their digits are random in a certain statistical sense.
David Bailey
Describing the normality property, David H. Bailey, chief technologist at NERSC, explains that "in the familiar base 10 decimal number system, any single digit of a normal number occurs one tenth of the time, any two-digit combination occurs one one-hundredth of the time, and so on. It's like throwing a fair, ten-sided die forever and counting how often each side or combination of sides appears."
Pi certainly seems to behave this way. In the first six billion decimal places of pi, each of the digits from 0 through 9 shows up about six hundred million times. Yet such results, conceivably accidental, do not prove normality even in base 10, much less normality in other number bases.
In fact, not a single naturally occurring math constant has been proved normal in even one number base, to the chagrin of mathematicians. While many constants are believed to be normal--including pi, the square root of 2, and the natural logarithm of 2, often written "log(2)"--there are no proofs.
The determined attacks of Bailey and his colleague Richard Crandall, director of the Center for Advanced Computation at Reed College, Portland, Oregon, are beginning to illuminate this classic problem. Their results indicate that the normality of certain math constants is a consequence of a plausible conjecture in the field of chaotic dynamics, which states that sequences of a particular kind, as Bailey puts it, "uniformly dance in the limit between 0 and 1"--a conjecture that he and Crandall refer to as "Hypothesis A."
"If even one particular instance of Hypothesis A could be established," Bailey remarks, "the consequences would be remarkable"--for the normality (in base 2) of pi and log(2) and many other mathematical constants would follow.
A simple formula discovered with the integer-relation algorithm dubbed PSLQ makes it possible to calculate the Nth binary digit of Pi without computing any of the first N-1 digits, and do the computation with very little computing power.
This result derives directly from the discovery of an ingenious formula for pi that Bailey, together with Canadian mathematicians Peter Borwein and Simon Plouffe, found with a computer program in 1996. Named the BBP formula for its authors, it has the remarkable property that it permits one to calculate an arbitrary digit in the binary expansion of pi without needing to calculate any of the preceding digits. Prior to 1996, mathematicians did not believe this could be done.
The digit-calculation algorithm of the BBP formula yields just the kind of chaotic sequences described in Hypothesis A. Says Bailey, "These constant formulas give rise to sequences that we conjecture are uniformly distributed between 0 and 1--and if so, the constants are normal."
Bailey emphasizes that the new result he and Crandall have obtained does not constitute a proof that pi or log(2) is normal (since this is predicated on the unproven Hypothesis A). "What we have done is translate a heretofore unapproachable problem, namely the normality of pi and other constants, to a more tractable question in the field of chaotic processes."
He adds that "at the very least, we have shown why the digits of pi and log(2) appear to be random: because they are closely approximated by a type of generator associated with the field of chaotic dynamics."
For the two mathematicians, the path to their result has been a long one. Bailey memorized pi to more than 300 digits "as a diversion between classroom lectures" while still a graduate student at Stanford. In 1985 he tested NASA's new Cray-2 supercomputer by computing the first 29 million digits of pi. The program found bugs in the Cray-2 hardware, "much to the consternation of Seymour Cray."
Crandall, who researches scientific applications of computation, suggested the possible link between the digits of pi and the theory of chaotic dynamic sequences.
While other prominent mathematicians in the field fear that the crucial Hypothesis A may be too hard to prove, Bailey and Crandall remain sanguine. Crandall quotes the eminent mathematician Carl Ludwig Siegel: "One cannot guess the real difficulties of a problem before having solved it."
Among the numerous connections of Bailey's and Crandall's work with other areas of research is in the field of pseudorandom number generators, which has applications in cryptography.
"The connection to pseudorandom number generators is likely the best route to making further progress," Bailey adds. "Richard and I are pursuing this angle even as we speak."--by Paul Preuss
===
Enjoy.
-- russ
Natural != (nontoxic || beneficial)
Too bad I can't get to the article to see how they are defining random. I have studied random numbers quite a bit, and have worked on the assumption that any thing that can be calculated is not truely random. So under that definition no, it isn't random, and neither are any of the random number generator algorithms.
The comon test for randomness is the chi squared test which actually tests for dispersion of numbers. That is are number occuring in 'equal' frequencies in an order that isn't too similar to the order in other sections of the sample. Failing the chi squared tests shows you aren't 'Pseudo Random' passing it only proves your numbers are dispersed not random
As x approaches total apathy I couldn't care less.
"Anyone who considers arithmetical methods of producing random digits is, of course, in a state of sin."
(John Von Neumann, 1951 )
+++ UGUCAUCGUAUUUCU
Or is it slashdotted already??
There is no spork.
So the real question is, will this make an RFC 3091 protocol happen more rapidly?
Sig: Tell all your friends NOT to download the Advanced Ebook Processor:
LedgerSMB: Open source Accounting/ERP
One has to be careful with such humor on /. Many will fail to catch it and think you are serious.
As to RFC 1149, Maximum trasmission retry for TCP is 120 sec. So RFC 1149 is nearly useless except for some ICMP and UDP...
Sig: Tell all your friends NOT to download the Advanced Ebook Processor:
LedgerSMB: Open source Accounting/ERP
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
(and nobody has yet found a pattern in the continued fractions of Pi) Actually, if I understand you correctly, they have: Pi = 4 * (1/1 - 1/3 + 1/5 - 1/7 + 1/9 - 1/11 ...)
"Sorry for the inconvenience"
q:]
MadCow
I used to have a sig, but I set it free and it never came back.
Whithout being a flaming asshole, what applications are there for knowing if the digits of PI are random or not?
Also, since Pi is a ratio that we 'choose' to express in a base10 numerical system, would the fact that the digits are random in a decimal system mean that they would be random if we expressed Pi in a hexidecimal or octal system?
The next Slashdot story will be ready soon, but subscribers can beat the rush and slashdot the links early!
And does anyone know if that link is incorrect in some way? My DNS can't resolve it.
OK,
- B
--
http://www.bradheintz.com/
- updated
"It is a profound and necessary truth that the deep things in science are not found because they are useful; they are found because it was possible to find them." -Robert Oppenheimer
Robert Moody from the Department Mathematical Sciences, University of Alberta illustrates the importance of curiosity based research in his paper using lasers as an example of why curiosity based research is necessary.
Carl Sagan in his book, The Demon Haunted World, also stresses the importance of curiosity based research using James Clark Maxell's discoveries as an example of how it effects our lives today by providing the necessary building blocks for radio, television, computers, lasers, etc.
It may be a while before we can find any spectacular applications with this new knowledge of pi, or we may not find any spectacular applications before we dissapear in the cosmos.
The point is: We'll never know if there are any spectacular or even merely useful applications if it isn't shared, discussed and debated throughout the community.
"Communism is like having one [local] phone company " - Lenny Bruce
Sorry, that's not a continued fraction.
.5*(sqrt(5) + 1). Number theory is fascinating. But I'm straying out of my way now. Try to write the fraction on paper, and you'll understand what continued fractions are.
I can't find an expansion for Pi, but for the golden ratio (1.6180339...) they go like this:
Phi = 1+1/(1+1/(1+1/(1+1/(1+1/(1+...)))))
What's interesting, Phi can be wrote as
Join the NFSNET. Our prime goal is making little numbers out of big ones. http://www.nfsnet.org/
Here's the output of John Walker's ent program for 512 megabits of Pi:
For the entropy test, a completely random sample would have an entropy of 8.0 bits per byte, and the ideal Chi Square distribution would be 256.0 (considering there are 256 degrees of freedom in an 8-bit data structure, or 2**8 possibilities.) As you can see, that's about as random as you can get. And the larger the samples you feed it, the more it converges to the ideal values.I've also done some testing with other transcendental numbers, such as e (2.718281828...), and they all seem to show great randomness properties, in the information-theoretic sense at least. However, I have a feeling to "trust" Pi more than e, given that you can write e in form of continued fractions with repeating patterns, and nobody has yet found a pattern in the continued fractions of Pi.
As for my pseudo-random library project, my programming skills are quite bad, but if you have some knowledge of scientific computing (multiplication algorithms using FFTs, for example), you can contact me and I might revive the idea.
Join the NFSNET. Our prime goal is making little numbers out of big ones. http://www.nfsnet.org/
Uh huh, and here's another, with 50% better compression:
Liberty in your lifetime
since hex is a binary shorthand.
Base 16 (hex) is just another number system, like decimal or octal or binary or hands-n-toes (base 20). Any value could be converted into any of those.
___
___
The way to see by faith is to shut the eye of reason. --Ben Franklin
You can however not write a generic compression algorithm that can compress any and all inputs without further information (as this would allow you to pass the output back in to that algorithm and repeat, until it has been compressed to nothing - which is a clear paradox).
"random" in the context of the article should rather be "unpredictable based on previous digits". What that means is that it should be impossible to predict the next digit og Pi based on the previous digits without resorting to other information about Pi (such as how to recognize Pi, and find a formula to calculate it) - the number itself doesn't appear to include any discernable information that allows you to accurately predict the next digit.
For an example, consider the sequence "1,2,3,4". Most people would predict the next digit to be "5". And most likely you'd be correct, because you'd assume you were looking at a part of a sequence increasing with one per digit - there's a relationship between the digits that can be easily calculated.
Noone has found that with Pi, and this article is about trying to prove that no such relationship can be found.
Or for the benefit of non-mathematicians: It's "random".
(disclaimer: I'm certainly no mathematician, and I'm sure someone can find some silly flaw in the above :-)
--
Remove Trash+ to reach my actual inbox
Mmmmm... floor pi
Endless arguments over trivial contradictions in books written by ignorant savages to explain thunder in the dark.
try to compress the "random" string of numbers; if you can compress a string of random numbers, it isn't
Not really. Since pi is some constant, and not generated by a random process, the most meaningful description of its compressibility is its Kolmogorov complexity, which refers to the shortest program capable of re-generating the original string. Unfortunately, Kolmogorov complexity is not computable in general.
Toronto-area transit rider? Rate your ride.
if not, it could not be used as universal common point.
the famous "Golden Number" is more impressive, I think
It takes 40+ muscles to frown, but only four to extend your arm and bitchslap the motherfucker
At the man's homepage.
http://www.nersc.gov/~dhbailey/
Check out the piqp.c in the middle of the page.
er... couldn't we just make up our own extremely long numbers to do this? Seems to me that if there is so much of a thought about wheither Pi is random or not, that people could figure out a number just as big and random. I mean I could take a gigantic picture of my butt, convert it to ascii and that's random enough for me.
No, it was neither Texas nor Kansas (Kansas did do the 'evolution' thing, though).
There was, a year or so back, a hoax on the Internet about Alabama doing the same thing, but it was a hoax. The only factual evidence that anything of the sort ever happened was in Indiania, 1897, and it never even got close to passing: the Senators considered it to be a complete joke.
Where do they find these guys? He memorizes pi, i play snake on my cellphone. eh
|---------------|
|---------------|
practically an AC