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

Internet Message Format | 1993-01-22 | 4.6 KB

Path: sparky!uunet!mcsun!uknet!comlab.ox.ac.uk!imc
From: [e-mail] (Ian Collier)
Newsgroups: comp.programming
Subject: Re: how to calculate pi + how about PRIME numbers ?
Message-ID: <[e-mail]>
Date: 22 Jan 93 14:23:17 GMT
References: <peterd.727578786@tscc2> <[e-mail]> <[e-mail]> <[e-mail]> <[e-mail]>
Organization: Oxford University Computing Laboratory
Lines: 105
X-Local-Date: Friday, 22nd January 1993 at 2:22pm GMT
Originator: [e-mail]

OK, time for my 2p :-)

In article <peterd.727578786@tscc2>, [e-mail] wrote:
>Ok, I asked for an algorithm for PI (and got several responses - thank you)
>(Why am I asking for this ? I just want to give my poor suffering pc
>something to do in the background of OS/2, seeing as it's never switched
>off intentionally I should be able to just leave it running !)

OK, if you are using OS/2 then you should be able to use REXX (there, I said
it again) so that you don't need to write yourself an arbitrary precision
arithmetic library.  I sent out several examples to a couple of people by
mail last November, and I still have them.

>How about an efficent algorithm for PRIME numbers ?

The usual way to generate a list of primes is with the sieve of Eratosthenes:

 1. Write a list of all natural numbers except 0 and 1 in ascending order
 2. Remove the first element from the list and call it p
 3. Output p
 4. Cross off the list all multiples of p
 5. go to 2.

Obviously you will have to truncate the list you make in (1) and limit the
range of the prime numbers (unless you use a functional language with lazy
evaluation).

If you are more interested in obtaining a few large prime numbers than in
making a list, then there are more efficient methods than the above.

And now back to pi...

Message-ID: <[e-mail]>
From: [e-mail] (Philippe Guglielmetti)

>For a fast algorithm (using reals), I think you can use almost any serie.
>for example
>arcsin x = x + (1*x^3)/(2*3) + (1*3*x^5)/(2*4*5) + (1*3*5*x^7)/(2*4*6*7)
>If you want a precision algorithm, then it becomes really interesting

The above is fairly fast among simple summations for pi, but there are
iterative methods which can beat any summation.  As for your second point,
REXX contains its own precision arithmetic, making life much easier.

Message-ID: <[e-mail]>
From: [e-mail] (John Andrea)

>There is an iterative algorithm for Pi given in
>"Ramaujan & Pi"
>Scientific American, Feb. 1989
>The accuracy quadrouples at each iteration.

However, I find that the 4th root is so much slower to calculate than the
square root that a similar quadratic method can turn out faster than this
quartic.  A compromise, using cube roots and having cubic convergence, was
published in the October 1992 issue of "Notices of the AMS".

Message-ID: <[e-mail]>
From: [e-mail] (Andy Lowry)

>One of the coolest formulas I've seen in Gregory's formula:
>  pi/4 = 4*atan(1/5)-atan(1/239)
>It's one of those formulas that makes you want to know how in the
>world anybody ever stumbled across it.

Well... you know that tan(x+y) = (tan x + tan y)/(1 - tan x.tan y)  and
therefore that  atan p = atan x + atan[(p-x)/(1+px)] for any x.

If you guess at x=1/5 and use the above formula several times to make the
residue as small as possible, you get:

pi/4 = atan 1 = atan 1/5 + atan 2/3
              = atan 1/5 + atan 1/5 + atan 7/17
          = atan 1/5 + atan 1/5 + atan 1/5 + atan 9/46
          = atan 1/5 + atan 1/5 + atan 1/5 + atan 1/5 - atan 1/239

If you try this with several values of x, you will probably find that 1/5
comes out the best.

Message-ID: <[e-mail]>
From: [e-mail] (Diversion (Jeff Rogers))

>Why not just
>   pi/4=atan(1)?
>If your answer is in radians, this works too, but
>I think it requires prior knowledge of pi.
>Maybe this is the answer (to my question above), but I don't see why a
>taylor expansion would work for some values and not others.

If you don't know, it's perhaps best not to comment...

The taylor series for atan(x) is
  x - x3/3 + x5/5 - x7/7 + ...
(where x3 means x cubed, etc).  The result is in radians.  Now insert x=1
into that formula and see how long it takes you to calculate pi to 50
figures...

This taylor series converges for any x such that |x|<=1.  However the
convergence is faster for small values of x - hence 1/5 and 1/239 are
suitable values to use.  The series can be improved by applying certain
transformations to its argument, but it is never particularly brilliant on
an input of 1.

Ian Collier
[e-mail] | [e-mail]