At 3:19 AM 1/5/96, jim bell wrote:
But BTW, isn't it interesting, that news item from a few weeks ago, on an algorithm for determining individual bits in Pi, regardless of whether you've calculated all the previous ones. Only problem is, it only works in hexadecimal (and, obviously, binary, etc, not decimal. ^^^^^^^^^^^
??? I didn't see this result you mention, but it surprises me. The part about how it works in some bases, but not in decimal. The "hand-waving" (motivational/informal) explanation for why I am surprised is that "Nature doesn't care about bipeds with 10 digits vs. bipeds, or whatever, with 2 digits or 16 digits." That is, results applicable in base 16, hexadecimal, should be easily applicable in base 10. And there is are interesting properties about the distribution of digits in "random" numbers. Pi is of course not random by many definitions, but shares certain important properties with random numbers. (Or sequences, if you wish.) One of these is properties is that of _regularity_, the frequency of digits. A regular number is one whose expansion has in the limit the same frequency for all digits, and this is so in any base. Thus, a regular number has an equal frequency (in the limit, blah blah) of 0s, 1s, 2s, 3s, etc. And switching to another base will not change this. I recollect that pi has been proved to me regular, i.e., that pi has an equal frequency of all digits, in the limit, in all bases. (This is the sense in which we can argue that pi is "random." in the sense that there are no correlations, no dependence of the n+1th digit on the nth digit, and "no apparent order." Furthermore, there is no effective compression of pi, except by some tricks, such as _naming_ it (a dictionary compression, of sorts) or by specifying a program which computes it. Lots of interesting issues about the real meaning of randomness and compressability, about the "logical depth" of certain computations, etc. I recommend "The Universal Turing Machine" (ed. by Haken, as I recall) for a nice set of articles on these fascinating issues.) In summary, I would be surprised to find that a method for calculating the Nth digit of pi works for base N but not for base M (modulo some minor efficiency factors related to machine architecture, etc.). Any pointers to this result would be appreciated. --Tim May (By the way, randomness and regularity, real or only apparent, are some of my favorite topics. Numbers which _appear_ to be regular, but which actually aren't, are said to be "cryptoregular" (hidden regular). The connection with cryptography is more than tangential: a text block or number which _appears_ to be random or regular (the same frequency definition applies to letters as well as digits) may be transformed by application of a key to a nonrandom or nonregular thing. The connection with entropy and randomness is right there, of course, and is left for the interested folks to think about.) We got computers, we're tapping phone lines, we know that that ain't allowed. ---------:---------:---------:---------:---------:---------:---------:---- Timothy C. May | Crypto Anarchy: encryption, digital money, tcmay@got.net 408-728-0152 | anonymous networks, digital pseudonyms, zero W.A.S.T.E.: Corralitos, CA | knowledge, reputations, information markets, Higher Power: 2^756839 - 1 | black markets, collapse of governments. "National borders aren't even speed bumps on the information superhighway."