For Timothy C. May and all the cypherists on this list: Here are three recent posts to usenet on the beautiful, and partly new results on getting digits far out in pi, without explicitly getting all the nearer to the heximal point digits.

From sci.math Wed Dec 20 05:16:17 1995 Path: panix!news.denver.eti.net!imci3!imci2!newsfeed.internetmci.com!uwm.edu!msunews!netnews.upenn.edu!red.seas.upenn.edu!jimmosk From: jimmosk@red.seas.upenn.edu (Jim J Moskowitz) Newsgroups: sci.math Subject: nth digit of pi calculable? Date: 18 Dec 1995 03:29:08 GMT Organization: University of Pennsylvania Lines: 29 Message-ID: <4b2n64$s27@netnews.upenn.edu> NNTP-Posting-Host: red.seas.upenn.edu Status: RO X-Status:

I've seen the recent reports about the discovery of a formula for pi of the form infinity ----- \ (- n) / 4 2 1 1 \ ) 16 (------- - ------- - ------- - ------- ) / \8 n + 1 8 n + 4 8 n + 5 8 n + 6 / ----- n = 0

which is said to tell you in a simple manner what the nth digit in the hexadecimal expansion of pi is. I don't see why. Yes, the ith term of this series does include 16^-i, which is the ith place in said expansion, but the term in parentheses (sorry; they look more like angle brackets) isn't an integer, so it's not giving you the value of the number in that ith place. Instead, it gives you several digits which are in places further along in pi, with no guarantee that other terms in this sigma won't also include digits in those places, forcing you to calculate and add up many terms....

Taking an incautious plunge into the world of computational math, Jim

-- ----------------------------------------------------------------------------- Jim Moskowitz (jimmosk@eniac.seas.upenn.edu) Visit the Unknown Composers Page: http://www.seas.upenn.edu/~jimmosk/TOC.html

...

From sci.math.pi Fri Jan 5 04:08:06 1996 From sci.math Wed Dec 20 05:16:57 1995 Path: panix!cmcl2!oitnews.harvard.edu!purdue!lerc.nasa.gov!magnus.acs.ohio-state.edu!math.ohio-state.edu!howland.reston.ans.net!newsfeed.internetmci.com!EU.net!peer-news.britain.eu.net!lyra.csx.cam.ac.uk!cet1 From: cet1@cus.cam.ac.uk (Chris Thompson) Newsgroups: sci.math Subject: Re: nth digit of pi calculable? Date: 18 Dec 1995 15:21:18 GMT Organization: University of Cambridge, England Lines: 46 Message-ID: <4b40te$r02@lyra.csx.cam.ac.uk> References: <4b2n64$s27@netnews.upenn.edu> NNTP-Posting-Host: grus.cus.cam.ac.uk Status: RO X-Status:

In article <4b2n64$s27@netnews.upenn.edu>, jimmosk@red.seas.upenn.edu (Jim J Moskowitz) writes: |> I've seen the recent reports about the discovery of a formula for pi |> of the form |> infinity |> ----- |> \ (- n) / 4 2 1 1 \ |> ) 16 (------- - ------- - ------- - ------- ) |> / \8 n + 1 8 n + 4 8 n + 5 8 n + 6 / |> ----- |> n = 0 |> |> which is said to tell you in a simple manner what the nth digit in the |> hexadecimal expansion of pi is. I don't see why. Yes, the ith term of |> this series does include 16^-i, which is the ith place in said expansion, |> but the term in parentheses (sorry; they look more like angle brackets) |> isn't an integer, so it's not giving you the value of the number in that |> ith place. Instead, it gives you several digits which are in places further |> along in pi, with no guarantee that other terms in this sigma won't also |> include digits in those places, forcing you to calculate and add up many |> terms....

You certainly have to add up a large number of terms. It is the ease with which these terms can be computed that has attracted interest to this and similar formulae.

Think in terms of trying to find the fractional part of 16^N * pi to reasonable accuracy, which is what is really meant by "finding the (N+1)'th hexadecmal digit" here -- you might always get unlucky and find only that this fractional part was between .2fffff and .300001, say. The terms with n >= N are of absolute value less than 1, and form a rapidly converging series, so their contribution is easy to compute. The term with n < N contribute terms of the form

fractional part ( 16^a(i) * b(i) / i )

where i < 8N, a(i) < N, and the b(i) are small integers. So it is sufficient to compute 16^a(i) mod i. If you don't already know, you can find out how to do this in time logarithmic in a(i) in, say, Knuth ACP Vol 2.

This is all explained in detail in the Borwein/Borwein/Plouffe paper, available from http://www.cecm.sfu.ca/~pborwein/PAPERS/P123.ps, which should be pretty comprehensible even by an amateur.

Chris Thompson Email: cet1@cam.ac.uk

...

From sci.math.pi Fri Jan 5 04:08:06 1996 From sci.math Wed Dec 20 05:17:20 1995 Path: panix!bloom-beacon.mit.edu!gatech!psuvax1!news.math.psu.edu!chi-news.cic.net!uwm.edu!lll-winken.llnl.gov!apple.com!apple.com!not-for-mail From: rjohnson@apple.com (Robert Johnson) Newsgroups: sci.math Subject: Re: nth digit of pi calculable? Date: 19 Dec 1995 13:01:28 -0800 Organization: Apple Computer, Inc., Cupertino, California Lines: 57 Message-ID: <4b7978$cj1@apple.com> References: <4b2n64$s27@netnews.upenn.edu> NNTP-Posting-Host: apple.com Status: RO X-Status:

In article <4b2n64$s27@netnews.upenn.edu>, Jim J Moskowitz <jimmosk@red.seas.upenn.edu> wrote:

...

I've seen the recent reports about the discovery of a formula for pi of the form infinity ----- \ (- n) / 4 2 1 1 \ ) 16 (------- - ------- - ------- - ------- ) / \8 n + 1 8 n + 4 8 n + 5 8 n + 6 / ----- n = 0

which is said to tell you in a simple manner what the nth digit in the hexadecimal expansion of pi is. I don't see why. Yes, the ith term of this series does include 16^-i, which is the ith place in said expansion, but the term in parentheses (sorry; they look more like angle brackets) isn't an integer, so it's not giving you the value of the number in that ith place. Instead, it gives you several digits which are in places further along in pi, with no guarantee that other terms in this sigma won't also include digits in those places, forcing you to calculate and add up many terms....

The full article can be found in PostScript form at

http://www.cecm.sfu.ca/personal/pborwein/PAPERS/P123.ps

and a text announcement can be found at

http://www.mathsoft.com/asolve/plouffe/scimath.txt

Yes indeed, you have to add up many terms. However, the amount of computation to find the n^th digit is on the order of n. Whereas, to compute n digits would require computation on the order of n^2.

The idea that drastically reduces the work here is that it is very easy to compute the n^th hex digit of 1/k. This is accomplished by raising 16 to the n-1^st power modulo k. Dividing the remainder by k gives the hex expansion of 1/k starting at the n^th hex digit. Raising 16 to the n-1^st power modulo k is done by squaring and multiplying based on the binary expansion of n-1 (the method of repeated squaring).

Thus, to get 16^{-k} 4/(8k+1) starting at the nth hex digit, compute 4*16^(n-1-k) mod 8k+1. Divide this remainder by 8k+1. For example, take n = 1000000000 and k = 1257894:

4*16^998742105 mod 10063153 = 4894450

and 4894450/10063153 = .7C82F7B089CCA729... (hex)

It will still entail around billion terms to compute the billionth digit of pi, but that's better than computing a quintillion digits.

Rob Johnson Apple Computer, Inc. rjohnson@apple.com