Re: Representations of Pi, etc.

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

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.

I assume it really works only in binary, and
hexadecimal follows, not the other way around.

  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.

Sorry, but it is quite possible for this to be the
case. (I don't know for sure whether this is one
of them or not, though, having not seen the result
myself.) But assume for the moment that the
formula, or algorithm, or whatever it is, really
does tell you exactly the value of a contiguous
chunk of "bits", real honest-to-god binary digits.
You cannot translate these to a decimal
representation without knowing all of the bits
leading up to them. For example, you know the last
four bits of an eight bit string:
  XXXX0011

In Hex the last digit is 3. But what is the last
digit in decimal? If the 'X's are all 0, it is 3, but
if the last X is a 1 (making the number 00010011 = 19),
it is not 3 but 9. If only the first X is a one,
it is 1.

There are plenty of places in information theory
where a log base 2 shows up, so I don't doubt
that there might be an algorithm for determining
a particular "bit" of Pi. But just to prove I
have a more concrete example, suppose you have an
encrypted bank transfer, with the numbers
expressed in binary. Further suppose you know it
is encrypted with a one-time-pad (just to be
contraversial) where you know a particular n-bit
chunk of the pad. Given this you can recover the
corresponding n-bit chunk of the amount, but
unless this spans the entire number you can't
express this unambiguously in decimal digits.
This is a simple consequence of the fact that
log(2) and log(10) are not integer multiples of
each other (you know what I mean). The same goes
the other way, of course. Given a string of
decimal digits extracted from the middle of a
number, I can't unambiguously decide what string
of bits these would become without knowing the
rest of the number.

The result is fascinating, assuming it is real.

Greg.

Greg Rose               INTERNET: greg_rose@sydney.sterling.com  
Sterling Software       VOICE:  +61-2-9975 4777    FAX:  +61-2-9975 2921
28 Rodborough Rd.       http://www.sydney.sterling.com:8080/~ggr/
French's Forest         35 0A 79 7D 5E 21 8D 47  E3 53 75 66 AC FB D9 45
NSW 2086 Australia.     co-mod sci.crypt.research, USENIX Director.

Tim May writes:

> > [ individual bits of pi ]
>
> 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.

It's an open question as to whether there's a version that works
in base 10.  There's a nice summary at
"http://www.mathsoft.com/asolve/plouffe/plouffe.html".

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

It does seem strange, but radix conversion can be much more expensive
than the baseline algorithm.  I vaguely remember hearing that
the billion-digit pi computations done with AGM techniques haven't
dealt with base 10 recently.

Cheers,
Peter Monta   pmonta@qualcomm.com
Qualcomm, Inc./Globalstar