Re: Pi: Less Random Than We Thought
At 03:55 PM 5/6/05 -0400, Tyler Durden wrote: Yes, but only provided the universe lasts long enough for those digits to be computed! -TD Actually, a few years ago someone discovered an algorithm for the Nth (hex) digit of Pi which doesn't require computing all the previous digits. Mind blowing.
Re: Pi: Less Random Than We Thought
http://cypherpunks.venona.com/date/1993/05/msg00213.html Back in the old days, Tim May would occasionally talk about the Kolmogorov-Chaitin theories about randomness - Kolmogorov complexity gives you a lot of deep explanations about this sort of problem. Alas, I never actually *read* those papers, but there's been a lot of mathematical thought about what randomness means.
Re: Pi: Less Random Than We Thought
http://cypherpunks.venona.com/date/1993/05/msg00213.html Back in the old days, Tim May would occasionally talk about the Kolmogorov-Chaitin theories about randomness - Kolmogorov complexity gives you a lot of deep explanations about this sort of problem. Alas, I never actually *read* those papers, but there's been a lot of mathematical thought about what randomness means.
Re: Pi: Less Random Than We Thought
--- Tyler Durden [EMAIL PROTECTED] wrote: Let us remember, of course, that the digits of pi are not random whatsoever: they are the digits of pi! Random is in the eye of the beholder. -TD Exactly. What an algorithm gives out is always deterministic. We try to see if there is some structure that allows us to cryptanalyze it. Sarad. __ Do you Yahoo!? Yahoo! Mail - Helps protect you from nasty viruses. http://promotions.yahoo.com/new_mail
Re: Pi: Less Random Than We Thought
hi, --- Gil Hamilton [EMAIL PROTECTED] wrote: For example, is this sequence of bits random: 01100100010? How about this one: 00? From a true random number generator, both are completely possible and equally valid. Random as in the sense guessable and thus posing a problem to the cryptosystem. Sarad. Yahoo! Mail Stay connected, organized, and protected. Take the tour: http://tour.mail.yahoo.com/mailtour.html
Re: Pi: Less Random Than We Thought
From: Sarad AV [EMAIL PROTECTED] Sent: May 5, 2005 8:43 AM To: [EMAIL PROTECTED] Cc: [EMAIL PROTECTED] Subject: Re: Pi: Less Random Than We Thought Well, if it were generated by a random process, we'd expect to see every n-bit substring in there somewhere, sooner or later, since the sequence never ends or repeats. Thus, the wonderful joke/idea about selling advertising space in the binary expansion of pi. Not only will your message last forever, but it will be seen by any advanced civilization that develops math and computers, even ones in other galaxies. --John
Re: Pi: Less Random Than We Thought
Yes, but only provided the universe lasts long enough for those digits to be computed! -TD From: John Kelsey [EMAIL PROTECTED] To: Sarad AV [EMAIL PROTECTED], [EMAIL PROTECTED] CC: [EMAIL PROTECTED] Subject: Re: Pi: Less Random Than We Thought Date: Fri, 6 May 2005 09:42:09 -0400 (GMT-04:00) From: Sarad AV [EMAIL PROTECTED] Sent: May 5, 2005 8:43 AM To: [EMAIL PROTECTED] Cc: [EMAIL PROTECTED] Subject: Re: Pi: Less Random Than We Thought Well, if it were generated by a random process, we'd expect to see every n-bit substring in there somewhere, sooner or later, since the sequence never ends or repeats. Thus, the wonderful joke/idea about selling advertising space in the binary expansion of pi. Not only will your message last forever, but it will be seen by any advanced civilization that develops math and computers, even ones in other galaxies. --John
Re: Pi: Less Random Than We Thought
--- Tyler Durden [EMAIL PROTECTED] wrote: Let us remember, of course, that the digits of pi are not random whatsoever: they are the digits of pi! Random is in the eye of the beholder. -TD Exactly. What an algorithm gives out is always deterministic. We try to see if there is some structure that allows us to cryptanalyze it. Sarad. __ Do you Yahoo!? Yahoo! Mail - Helps protect you from nasty viruses. http://promotions.yahoo.com/new_mail
Re: Pi: Less Random Than We Thought
From: Sarad AV [EMAIL PROTECTED] Sent: May 5, 2005 8:43 AM To: [EMAIL PROTECTED] Cc: [EMAIL PROTECTED] Subject: Re: Pi: Less Random Than We Thought Well, if it were generated by a random process, we'd expect to see every n-bit substring in there somewhere, sooner or later, since the sequence never ends or repeats. Thus, the wonderful joke/idea about selling advertising space in the binary expansion of pi. Not only will your message last forever, but it will be seen by any advanced civilization that develops math and computers, even ones in other galaxies. --John
Re: Pi: Less Random Than We Thought
hi, --- Gil Hamilton [EMAIL PROTECTED] wrote: For example, is this sequence of bits random: 01100100010? How about this one: 00? From a true random number generator, both are completely possible and equally valid. Random as in the sense guessable and thus posing a problem to the cryptosystem. Sarad. Yahoo! Mail Stay connected, organized, and protected. Take the tour: http://tour.mail.yahoo.com/mailtour.html
Re: Pi: Less Random Than We Thought
Yes, but only provided the universe lasts long enough for those digits to be computed! -TD From: John Kelsey [EMAIL PROTECTED] To: Sarad AV [EMAIL PROTECTED], [EMAIL PROTECTED] CC: [EMAIL PROTECTED] Subject: Re: Pi: Less Random Than We Thought Date: Fri, 6 May 2005 09:42:09 -0400 (GMT-04:00) From: Sarad AV [EMAIL PROTECTED] Sent: May 5, 2005 8:43 AM To: [EMAIL PROTECTED] Cc: [EMAIL PROTECTED] Subject: Re: Pi: Less Random Than We Thought Well, if it were generated by a random process, we'd expect to see every n-bit substring in there somewhere, sooner or later, since the sequence never ends or repeats. Thus, the wonderful joke/idea about selling advertising space in the binary expansion of pi. Not only will your message last forever, but it will be seen by any advanced civilization that develops math and computers, even ones in other galaxies. --John
Re: Pi: Less Random Than We Thought
hi, If you remember D.E Knuth's book on Semi-Numerical Algorithms he shows some annoying subsequences of pi in it which are far from random. Sarad. --- cypherpunk [EMAIL PROTECTED] wrote: This doesn't really make sense. Either the digits are random or they are not. You can't be a little bit random. Well, you can be, but the point is that you either pass the test or you don't. If pi's digits fail a test of randomness in a statistically significant way, that is big news. If they pass it, then there is no meaningful way to compare them with another RNG that also passes. It's just a statistical quirk due to random variation as to which will do better than another on any given test. The bottom line is still that either an RNG passes the tests acceptably or it does not. From what they say (or don't say), pi does pass. It doesn't make sense to say that other RNGs do better. CP Yahoo! Mail Stay connected, organized, and protected. Take the tour: http://tour.mail.yahoo.com/mailtour.html
Re: Pi: Less Random Than We Thought
Sarad writes: If you remember D.E Knuth's book on Semi-Numerical Algorithms he shows some annoying subsequences of pi in it which are far from random. I don't have Knuth's book handy to look at, but it's not really correct to speak of a particular sequence or subsequence of digits as being random or non-random. For example, is this sequence of bits random: 01100100010? How about this one: 00? From a true random number generator, both are completely possible and equally valid. (Furthermore, I would contend that the digits of pi are *non-random* by definition.) --- cypherpunk [EMAIL PROTECTED] wrote: This doesn't really make sense. Either the digits are random or they are not. You can't be a little bit random. Well, you can be, but the point is that you either pass the test or you don't. [snip] The bottom line is still that either an RNG passes the tests acceptably or it does not. From what they say (or don't say), pi does pass. It doesn't make sense to say that other RNGs do better. One can only do statistical analyses of sequences of digits to determine whether they *appear* to have a uniform distribution of individual digits and subsequences. Of course the result of such a test (positive *or* negative) doesn't positively confirm whether a given digit source is truly random. Wikipedia has a good article on randomness: http://en.wikipedia.org/wiki/Random GH _ Dont just search. Find. Check out the new MSN Search! http://search.msn.click-url.com/go/onm00200636ave/direct/01/
Re: Pi: Less Random Than We Thought
Cypherpunk: While I respect your forthrightness you are unfortunately wrong. Read the chapters on Randon Mumber generation from Numerical Recipes in C and you get just a small glimpse of how sticky the issue is, particularly when it comes to computers (which are innately non-random, by the way). As a very simple example, imagine that after 10 billion digits we found that the average value was actually 5.1. This would make it, in your book, not random at all, but I suspect that for almost many uses it would be random enough. And then, imagine that the cumulative average of the digits of pi oscillated around 5 (to one part in a zillion) with a period of 100 Billion...is this random enough for you? Let us remember, of course, that the digits of pi are not random whatsoever: they are the digits of pi! Random is in the eye of the beholder. I was hoping Cordian would grumpily reply...he's a number theorist or something. -TD From: Sarad AV [EMAIL PROTECTED] To: [EMAIL PROTECTED] CC: [EMAIL PROTECTED] Subject: Re: Pi: Less Random Than We Thought Date: Thu, 5 May 2005 05:43:35 -0700 (PDT) hi, If you remember D.E Knuth's book on Semi-Numerical Algorithms he shows some annoying subsequences of pi in it which are far from random. Sarad. --- cypherpunk [EMAIL PROTECTED] wrote: This doesn't really make sense. Either the digits are random or they are not. You can't be a little bit random. Well, you can be, but the point is that you either pass the test or you don't. If pi's digits fail a test of randomness in a statistically significant way, that is big news. If they pass it, then there is no meaningful way to compare them with another RNG that also passes. It's just a statistical quirk due to random variation as to which will do better than another on any given test. The bottom line is still that either an RNG passes the tests acceptably or it does not. From what they say (or don't say), pi does pass. It doesn't make sense to say that other RNGs do better. CP Yahoo! Mail Stay connected, organized, and protected. Take the tour: http://tour.mail.yahoo.com/mailtour.html
Re: Pi: Less Random Than We Thought
Cypherpunk: While I respect your forthrightness you are unfortunately wrong. Read the chapters on Randon Mumber generation from Numerical Recipes in C and you get just a small glimpse of how sticky the issue is, particularly when it comes to computers (which are innately non-random, by the way). As a very simple example, imagine that after 10 billion digits we found that the average value was actually 5.1. This would make it, in your book, not random at all, but I suspect that for almost many uses it would be random enough. And then, imagine that the cumulative average of the digits of pi oscillated around 5 (to one part in a zillion) with a period of 100 Billion...is this random enough for you? Let us remember, of course, that the digits of pi are not random whatsoever: they are the digits of pi! Random is in the eye of the beholder. I was hoping Cordian would grumpily reply...he's a number theorist or something. -TD From: Sarad AV [EMAIL PROTECTED] To: [EMAIL PROTECTED] CC: [EMAIL PROTECTED] Subject: Re: Pi: Less Random Than We Thought Date: Thu, 5 May 2005 05:43:35 -0700 (PDT) hi, If you remember D.E Knuth's book on Semi-Numerical Algorithms he shows some annoying subsequences of pi in it which are far from random. Sarad. --- cypherpunk [EMAIL PROTECTED] wrote: This doesn't really make sense. Either the digits are random or they are not. You can't be a little bit random. Well, you can be, but the point is that you either pass the test or you don't. If pi's digits fail a test of randomness in a statistically significant way, that is big news. If they pass it, then there is no meaningful way to compare them with another RNG that also passes. It's just a statistical quirk due to random variation as to which will do better than another on any given test. The bottom line is still that either an RNG passes the tests acceptably or it does not. From what they say (or don't say), pi does pass. It doesn't make sense to say that other RNGs do better. CP Yahoo! Mail Stay connected, organized, and protected. Take the tour: http://tour.mail.yahoo.com/mailtour.html
Re: Pi: Less Random Than We Thought
[1]Autoversicherung writes Physicists including Purdue's Ephraim Fischbach have completed a study [2]comparing the 'randomness' in pi to that produced by 30 software random-number generators and one chaos-generating physical machine. After conducting several tests, they have found that while sequences of digits from pi are indeed an acceptable source of randomness -- often an important factor in data encryption and in solving certain physics problems -- pi's digit string does not always produce randomness as effectively as manufactured generators do. 1. https://autoversicherung.einsurance.de/ 2. http://news.uns.purdue.edu/UNS/html4ever/2005/050426.Fischbach.pi.html This doesn't really make sense. Either the digits are random or they are not. You can't be a little bit random. Well, you can be, but the point is that you either pass the test or you don't. If pi's digits fail a test of randomness in a statistically significant way, that is big news. If they pass it, then there is no meaningful way to compare them with another RNG that also passes. It's just a statistical quirk due to random variation as to which will do better than another on any given test. The bottom line is still that either an RNG passes the tests acceptably or it does not. From what they say (or don't say), pi does pass. It doesn't make sense to say that other RNGs do better. CP
Re: Pi: Less Random Than We Thought
[1]Autoversicherung writes Physicists including Purdue's Ephraim Fischbach have completed a study [2]comparing the 'randomness' in pi to that produced by 30 software random-number generators and one chaos-generating physical machine. After conducting several tests, they have found that while sequences of digits from pi are indeed an acceptable source of randomness -- often an important factor in data encryption and in solving certain physics problems -- pi's digit string does not always produce randomness as effectively as manufactured generators do. 1. https://autoversicherung.einsurance.de/ 2. http://news.uns.purdue.edu/UNS/html4ever/2005/050426.Fischbach.pi.html This doesn't really make sense. Either the digits are random or they are not. You can't be a little bit random. Well, you can be, but the point is that you either pass the test or you don't. If pi's digits fail a test of randomness in a statistically significant way, that is big news. If they pass it, then there is no meaningful way to compare them with another RNG that also passes. It's just a statistical quirk due to random variation as to which will do better than another on any given test. The bottom line is still that either an RNG passes the tests acceptably or it does not. From what they say (or don't say), pi does pass. It doesn't make sense to say that other RNGs do better. CP
Re: Pi
At 11:34 AM 8/2/2001 -0700, Eric Cordian wrote: Interesting article recently posted on the Nature Web site about the normality of Pi. http://www.nature.com/nsu/010802/010802-9.html David Bailey of Lawrence Berkeley National Laboratory in California and Richard Crandall of Reed College in Portland, Oregon, present evidence that pi's decimal expansion contains every string of whole numbers. They also suggest that all strings of the same length appear in pi with the same frequency: 87,435 appears as often as 30,752, and 451 as often as 862, a property known as normality. Of cryptographic interest. While there may be no cosmic message lurking in pi's digits, if they are random they could be used to encrypt other messages as follows: Convert a message into zeros and ones, choose a string of digits somewhere in the decimal expansion of pi, and encode the message by adding the digits of pi to the digits of the message string, one after another. Only a person who knows the chosen starting point in pi's expansion will be able to decode the message. While there's presently no known formula which generates decimal digits of Pi starting from a particular point, there's a clever formula which can be used to generate HEX digits of Pi starting from anywhere, which Bailey et al discovered in 1996, using the PSLQ linear relation algorithm. I tried to something like this in the late '80s to allow efficient loss-less compression using conditioned PRNs which could generate suitable auto correlated streams. Unfortunately, I did not discover a similar method of locating the desired sequences. The search during the compression phase was to computationally difficult and I abandoned the effort. steve
Re: Pi
Phillip H. Zakas wrote: this is truly interesting...do you have a link to the original 1996 paper? do you know if anyone has incorporated this into a program? David Bailey has a brief explanation of the Pi digit algorithm on his Web page at NERSC... http://hpcf.nersc.gov/~dhbailey/pi-alg Also check out Recognizing Numerical Constants by David H. Bailey and Simon Plouffe at... http://www.cecm.sfu.ca/organics/papers/bailey/paper/html/paper.html and click on the link titled Formulas for Pi and Related Constants. More interesting stuff at... http://www.multimania.com/bgourevitch/ref/ottawaPi.pdf Where plouffe discusses some more of the math and reveals the 400 billionth binary digit of Pi. Lots more if you use a search engine. -- Eric Michael Cordian 0+ O:.T:.O:. Mathematical Munitions Division Do What Thou Wilt Shall Be The Whole Of The Law
RE: Pi
this is truly interesting...do you have a link to the original 1996 paper? do you know if anyone has incorporated this into a program? phillip -Original Message- From: [EMAIL PROTECTED] [mailto:[EMAIL PROTECTED]]On Behalf Of Eric Cordian Sent: Thursday, August 02, 2001 2:35 PM To: [EMAIL PROTECTED] Subject: Pi Interesting article recently posted on the Nature Web site about the normality of Pi. http://www.nature.com/nsu/010802/010802-9.html David Bailey of Lawrence Berkeley National Laboratory in California and Richard Crandall of Reed College in Portland, Oregon, present evidence that pi's decimal expansion contains every string of whole numbers. They also suggest that all strings of the same length appear in pi with the same frequency: 87,435 appears as often as 30,752, and 451 as often as 862, a property known as normality. Of cryptographic interest. While there may be no cosmic message lurking in pi's digits, if they are random they could be used to encrypt other messages as follows: Convert a message into zeros and ones, choose a string of digits somewhere in the decimal expansion of pi, and encode the message by adding the digits of pi to the digits of the message string, one after another. Only a person who knows the chosen starting point in pi's expansion will be able to decode the message. While there's presently no known formula which generates decimal digits of Pi starting from a particular point, there's a clever formula which can be used to generate HEX digits of Pi starting from anywhere, which Bailey et al discovered in 1996, using the PSLQ linear relation algorithm. If you sum the following series for k=0 to k=infinity, its limit is Pi. 1/16^k[4/(8k+1) - 2/(8k+4) - 1/(8k+5) - 1/(8k+6)] (Exercise: Prove this series sums to Pi) Since this is an expression for Pi in inverse powers of 16, it is easy to multiply this series by 16^d and take the fractional part, evaluating terms where dk by modular exponentiation, and evaluating a couple of terms where dk to get a digit's worth of precision, yielding the (d+1)th hexadecimal digit of Pi. Presumedly, if one could express PI as a series in inverse powers of 10, one could do the same trick to get decimal digits. Such a series has so far eluded researchers. -- Eric Michael Cordian 0+ O:.T:.O:. Mathematical Munitions Division Do What Thou Wilt Shall Be The Whole Of The Law
