From: jim bell <jimbell@pacifier.com>
Date: Sat, 6 Jan 1996 05:13:17 +0800
To: tcmay@got.net (Timothy C. May)
Subject: Re: Representations of Pi, etc.
Message-ID: <m0tYICf-00090EC@pacifier.com>
MIME-Version: 1.0
Content-Type: text/plain


At 11:45 PM 1/4/96 -0800, you wrote:
>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.

And practically everybody else, I'm sure!  It was  written up in Science
News magazine, BTW.

>The part about how it works in some bases, but not in decimal.

Well, by definition if it works in hex, it'll work in octal, "quadal" (?),
binary, etc.  That's ASSUMED, since they would be subsets (co-sets?) of each
other.

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

Yeah, well, I understand your frustration, but to me the really amazing part
is that the elephant flies at all, and not how well he flies (<G>)  (In
other words, the amazing thing is that there is a predictable relationship
in ANY base system)  Chances are the thing WON'T work in base
3,5,6,7,9,10,11,12,13,14,15, and any other non 2**n base.  Or, at least, it
will take a DIFFERENT equation to work in those other bases, if they work at
all.


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

Not "regular," you used the wrong term.  As a mathematician's term of art,
this is called "normal." In other words, equal numbers of digits 0-9, equal
numbers of digit pairs 00-through 99, equal number of digit triplets
000-999, etc.  A series of random numbers, by definition, must be "normal."
But "Normal" numbers do not necessarily have to be random.  As you might
expect, however, testing for "normality" is a good first test of "randomness." 

(I'm not a mathematician, and I don't play one on TV.  Don't be overly
impressed with the preceeding knowledge; I'm sure there are dozens if a
hundred people reading cypherpunks who know more math than I do. I only got
a 780 on the math portion of my SAT, 20 years ago...  790's and 800's
weren't all that uncommon.) 

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

Yes, pi is apparently "normal."  (at least four the first 4 billion or so
digits...)

>(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.)

Of course, I'm not sure of the ramifications of this new discovery
(individual-digit computability of pi) on the facts you list...  (for
example, inter-digit dependence)   However, if the digital representations
of the digits of pi were indeed still individually "random" and they could
be individually computed rapidly enough, at least hypothetically you could
use the digits of pi as a "one-time-pad".  Obviously, everyone would know
(at least, conceptually) the ENTIRE CONTENT of the pad; the only issue would
be the location where you started.  If the starting point was the key, and
could be defined by a number of at least, say, 256-bits long, it might be a
replacement for IDEA whose current length is fixed at 128 bits. 

I suppose the problem with this technique will probably be that it would
take too long to calculate the (a number somewhere around 2**256) bit of pi,
and for an n-bit message you'd have to do this n times.  

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

I'm sure somebody else will have seen it.  It was in Science News in the
last couple of months, as I recall.  Some kind soul will probably type it
in.  Maybe I can even retrieve my copy from my sister.