NetNews Usenet Archive 1993 #3/NN_1993_3.iso/spool/comp/programm/3539

Text File | 1993-01-21 | 3.2 KB | 67 lines

Newsgroups: comp.programming
Path: sparky!uunet!newsgate.watson.ibm.com!yktnews2.watson.ibm.com!yktnews!admin!flu!lowry
From: [e-mail] (Andy Lowry)
Subject: Re: how to calculate PI
Sender: [e-mail] (NNTP News Poster)
Message-ID: <[e-mail]>
In-Reply-To: [e-mail]'s message of Thu, 21 Jan 1993 11:29:25 GMT
Date: Thu, 21 Jan 1993 17:45:21 GMT
Disclaimer: This posting represents the poster's views, not necessarily those of IBM
References: <peterd.727508100@tscc2> <[e-mail]>
    <[e-mail]> <[e-mail]>
Nntp-Posting-Host: rotor.watson.ibm.com
Organization: IBM T.J. Watson Research Center
Lines: 51

In article <[e-mail]> [e-mail] (Bryan O'Sullivan) writes:
 > I've not looked at any analyses, but it seems that Gregory's
 > algorithm gets roughly exponentially slower with the number of
 > digits of precision required.  Or perhaps it's just the variant I
 > have.

A straightforward implementation does the following to compute
atan(1/x):

 1. Allocate two vectors of integers big enough to hold as many digits
    of pi as you need (multiple digits per integer), plus sufficient
    "slop" (it's possible to work out how much slop is sufficient).
    One is the "current term" vector and the other is the "sum"
    vector.
 2. Zero all elements of the current term vector except the first,
    which you set to the value x (the decimal point is assumed to lie
    between the first and second vector elements; thus this
    initialization sets the vector to represent the value x).  Zero
    all elements of the sum vector, thus initializing it to the value
    0.
 3. Set i=1
 4. Divide the current term vector by x^2, and then by 2i-1.  As long
    as i doesn't get too big, you can use a very simple algorithm to
    divide an extended-precision value by a scalar, in time linear in
    the size of your vector.
 5. If i is odd, add the current term vector into the sum; otherwise
    subtract the current term vector from the sum.  Both operations
    can be done in time linear in the size of the vectors.
 6. If the current term vector is not zero, increment i by 1 and loop
    back to step 4.  Otherwise terminate.

The number of iterations required is linear in the size of the
vectors, since each iteration will shrink the current term vector by
at least an order of magnitude as long as x^2 >= 10 (and in general, k
iterations will reduce the current term by at least an order of
magnitude as long as k >= 1/log_10(x^2)).  Thus the total running time
is O(n^2), where n is the number of digits you require.

The above works so long as the division by 2i-1 in step 4 never
requires larger integers than your machine can represent.  For
sufficiently small i, this will be the case, and on typical machines
you can go far enough to get a good nubmer of digits.  A more general
implementation would require that the division be carried out between
two extended-precision numbers, and that can be done in O(n^2) time so
the overall running time turns into O(n^3).

In any case, you should not be seeing exponential performance
degradation.
--
Andy Lowry, [e-mail], [phone]
IBM Research, P.O. Box 704, Yorktown Heights, NY  10598