From msuinfo!agate!usenet.ins.cwru.edu!news.ecn.bgu.edu!siemens!princeton!phoenix.Princeton.EDU!rwsayer Sun Oct 17 00:15:06 1993 Newsgroups: sci.crypt,sci.math Path: msuinfo!agate!usenet.ins.cwru.edu!news.ecn.bgu.edu!siemens!princeton!phoenix.Princeton.EDU!rwsayer From: rwsayer@phoenix.Princeton.EDU (Ronald Winston Sayer) Subject: Re: Digits of pi Message-ID: <1993Oct13.010448.20634@Princeton.EDU> Originator: news@nimaster Sender: Ron Sayer Nntp-Posting-Host: phoenix.princeton.edu Organization: Princeton University References: <29fg2e$55o@news.delphi.com> Date: Wed, 13 Oct 1993 01:04:48 GMT Lines: 30 Xref: msuinfo sci.crypt:20364 sci.math:54578 >Does someone have a simple formula for computing the digits of >pi that can be implemented using a basic language like C?? > >I know its a loaded question, but I'll take any help I can get. > >Tod Well, there's the venerable PI/4 = 1 - 1/3 +1/5 -1/7 +1/9 - ...... but that's rediculously wimpy. Try this PI/4 = 4*ATAN (1/5) - ATAN(1/239) where , ATAN(x) = x - (x^3)/3 + (x^5)/5 - (x^7)/7 + ..... This converges nicely, and will easily give you 10,000 didgits of PI on any reasonable workstation, or maybe even a PC. There are more complicated ways to calculate PI that converge much more rapidly, but this is one of my favorite due to its simplicity. Ron Sayer rwsayer@phoenix.princeton.edu From msuinfo!agate!usenet.ins.cwru.edu!magnus.acs.ohio-state.edu!math.ohio-state.edu!cs.utexas.edu!uunet!olivea!decwrl!pa.dec.com!e2big.mko.dec.com!peavax.mlo.dec.com!3d.enet.dec.com!roth Sun Oct 17 00:15:06 1993 Newsgroups: sci.crypt,sci.math Path: msuinfo!agate!usenet.ins.cwru.edu!magnus.acs.ohio-state.edu!math.ohio-state.edu!cs.utexas.edu!uunet!olivea!decwrl!pa.dec.com!e2big.mko.dec.com!peavax.mlo.dec.com!3d.enet.dec.com!roth From: roth@3d.enet.dec.com (Jim Roth) Subject: Re: Digits of pi Message-ID: <1993Oct13.162340.4373@peavax.mlo.dec.com> Sender: usenet@peavax.mlo.dec.com (USENET News System) Organization: Digital Equipment Corporation References: <29fg2e$55o@news.delphi.com> Date: Wed, 13 Oct 1993 17:26:35 GMT Lines: 51 Xref: msuinfo sci.crypt:20374 sci.math:54604 In article , Henrik.Johansson@nexus.comm.se (Henrik Johansson) writes... > >>Try this >> >>PI/4 = 4*ATAN (1/5) - ATAN(1/239) >>There are more complicated ways to calculate PI that converge >>much more rapidly, but this is one of my favorite due to its >>simplicity. >Do you happen to have online descriptions of those more rapidly >converging calculations? If so - please make them available in some >form! Either by email to me directly, or some math newsgroup. In the latest revision of Numerical Recipes, there is a Brent-Salamin AGM algorithm to compute PI, but I don't have it online. For just 10K digits of PI, a simple program like this will suffice. - Jim /* 1000 digits of PI */ /* 'Spigot' algorithm origionally due to Stanly Rabinowitz */ #include main() { int d = 4, r = 10000, n = 251, m = 3.322*n*d; int i, j, k, q; static int a[3340]; for (i = 0; i <= m; i++) a[i] = 2; a[m] = 4; for (i = 1; i <= n; i++) { q = 0; for (k = m; k > 0; k--) { a[k] = a[k]*r+q; q = a[k]/(2*k+1); a[k] -= (2*k+1)*q; q *= k; } a[0] = a[0]*r+q; q = a[0]/r; a[0] -= q*r; printf("%04d%s",q, i & 7 ? " " : "\n"); } } From msuinfo!uwm.edu!cs.utexas.edu!math.ohio-state.edu!darwin.sura.net!europa.eng.gtefsd.com!news.ans.net!malgudi.oar.net!witch!cyberg!fb Sun Oct 17 00:15:06 1993 Path: msuinfo!uwm.edu!cs.utexas.edu!math.ohio-state.edu!darwin.sura.net!europa.eng.gtefsd.com!news.ans.net!malgudi.oar.net!witch!cyberg!fb Newsgroups: sci.crypt,sci.math Message-ID: <14@cyberg.win.net> References: <29fg2e$55o@news.delphi.com> Reply-To: fb@cyberg.win.net (Francis Barrett) From: fb@cyberg.win.net (Francis Barrett) Date: Wed, 13 Oct 1993 15:33:06 GMT Subject: Re: Digits of pi Lines: 56 Xref: msuinfo sci.crypt:20379 sci.math:54608 In article <29fg2e$55o@news.delphi.com>, TODANIELS@DELPHI.COM (todaniel@news.delphi.com) writes: >Does someone have a simple formula for computing the digits of >pi that can be implemented using a basic language like C?? >I know its a loaded question, but I'll take any help I can get. Providing you have an efficient subroutine package for multiprecision arithmetic, there are a number of quickly convergent iterations which can be employed to calculate many digits of Pi. My favorite is a quartic iteration based on an elliptic function called the Singular Value Function of the Second Kind. It converges exponentially to 1/Pi as its argument increases. There is a rich set of "modular equations" which algebraically relate values of this function for different values of its argument. Repeating these formulas as iterations allows us to compute the value of this function for increasingly large arguments and consequently the value of Pi. This technique is based on the work of the eccentric Indian mathematician Srinivasa Ramanujan. The basic iteration goes like this... Y[N+1] = (1-(1-Y[N]^4)^0.25)/(1+(1-Y[N]^4)^0.25) A[N+1] = (1+Y[N+1])^4*A[N]-4^(N+1)*SQRT(R)*Y[N+1]*(1+Y[N+1]+Y[N+1]^2) This will compute approximately 45 million decimal digits of Pi in only 12 iterations with R = 4. This formula works for any positive R, but the initial values of the iteration, Y[0] and A[0] are dependent on the R chosen. A[0] should be the Singular Value Function of the Second Kind evaluated at R and Y[0] should be the square root of the another function, called the Singular Value Function of the First Kind, again evaluated at R. For instance, if we choose R = 2, the correct starting values turn out to be A[0] = SQRT(2)-1 and Y[0] = SQRT(SQRT(2)-1). Then the iteration looks like this... N Y[N] A[N] 1/A[N] 0 0.6435942530 0.414213562 2.41421356 1 0.0235239602 0.318310704 3.14158459 2 0.0000000383 0.318309886 3.14159265 As you can see, the convergence to Pi is quite rapid, and each iteration gives approximately four times the number of decimal places as the previous one. Using techniques like these, and an efficient multiprecision package, computation of Pi to millions of places is well within the computational power of the typical personal computer. --------------------------------------------------------------- Francis Barrett, F.R.C. | Thou canst not travel on the path | The Cybernetics Guild | before thou hast become the Path | fb@cyberg.win.net | itself. | --------------------------------------------------------------- From msuinfo!uwm.edu!spool.mu.edu!howland.reston.ans.net!europa.eng.gtefsd.com!news.ans.net!malgudi.oar.net!witch!cyberg!fb Sun Oct 17 00:15:06 1993 Path: msuinfo!uwm.edu!spool.mu.edu!howland.reston.ans.net!europa.eng.gtefsd.com!news.ans.net!malgudi.oar.net!witch!cyberg!fb Newsgroups: sci.crypt,sci.math Message-ID: <16@cyberg.win.net> References: <29fg2e$55o@news.delphi.com> <14@cyberg.win.net><29icje$3eu@news.delphi.com><15@cyberg.win.net> Reply-To: fb@cyberg.win.net (Francis Barrett) From: fb@cyberg.win.net (Francis Barrett) Date: Thu, 14 Oct 1993 19:55:32 GMT Subject: Re: Digits of pi Lines: 24 Xref: msuinfo sci.crypt:20427 sci.math:54715 In article <140722@bond.nexus.comm.se>, Henrik Johansson (Henrik.Johansson@nexus.comm.se) writes: >>Try this >>PI/4 = 4*ATAN (1/5) - ATAN(1/239) Before the latest approximations to Pi using modular equations were developed, Taylor series expansions of arctans were the state of the art. There are a huge number of these, all designed to make the denominators of the series terms grow as rapidly as possible. Besides the one above, the following are also popular... Pi = 20*arctan(1/7) + 8*arctan (3/79) Pi/4 = arctan(1/2) + arctan(1/5) + arctan(1/8) Pi/4 = 3*arctan(1/4) + arctan(1/20) + arctan(1/1985) Pi = 24*arctan(1/8) + 8*arctan(1/57) + 4*arctan(1/239) pi = 48*arctan(1/18) + 32*arctan(1/57) - 20*arctan(1/239) Pi has so far been computed to over a billion places and no pattern in the digits has been discovered, other than the obvious one. --------------------------------------------------------------- Francis Barrett, F.R.C. | Thou canst not travel on the path | The Cybernetics Guild | before thou hast become the Path | fb@cyberg.win.net | itself. | --------------------------------------------------------------- From msuinfo!agate!howland.reston.ans.net!pipex!sunic!kth.se!vana!TORDM Sun Oct 17 00:15:06 1993 Newsgroups: sci.crypt,sci.math Path: msuinfo!agate!howland.reston.ans.net!pipex!sunic!kth.se!vana!TORDM From: tordm@vana (Tord G.M. Malmgren) Subject: Re: Digits of pi Message-ID: <1993Oct16.104528.6972@kth.se> Sender: usenet@kth.se Nntp-Posting-Host: vana.physto.se Reply-To: TordM@VanA.PhySto.SE Organization: Department of Physics, University of Stockholm -- Sweden References: <29fg2e$55o@news.delphi.com> <14@cyberg.win.net><29icje$3eu@news.delphi.com><15@cyberg.win.net>,<16@cyberg.win.net> Date: Sat, 16 Oct 1993 10:45:28 GMT Lines: 27 Xref: msuinfo sci.crypt:20457 sci.math:54801 In article <16@cyberg.win.net>, fb@cyberg.win.net (Francis Barrett) writes: >Besides the one above, the following are also popular... > > Pi = 20*arctan(1/7) + 8*arctan (3/79) > Pi/4 = arctan(1/2) + arctan(1/5) + arctan(1/8) > Pi/4 = 3*arctan(1/4) + arctan(1/20) + arctan(1/1985) > Pi = 24*arctan(1/8) + 8*arctan(1/57) + 4*arctan(1/239) > pi = 48*arctan(1/18) + 32*arctan(1/57) - 20*arctan(1/239) and also two "faster" ones; pi/4 = 22*arctan(1/28)+2*arctan(1/443)-5*arctan(1/1393)-10*arctan(1/11018) pi/4 = 44*arctan(1/57)+7*arctan(1/239)-12*arctan(1/682)+24*arctan(1/12943) which someone posted before (don't remember who.) To get even better ones read "An Algorithm for The Calculation of \pi" by George Miel... (I think "Classroom Notes" October 1979.) ---------------+--------------------------------+---------------------------- Tord Malmgren | InterNet: TordM@VanA.PhySto.SE | These opinions are my OWN, | BITNet : TordM@SESUF51 | and NOT of this department! ---------------+--------------------------------+---------------------------- Department of Physics, University of Stockholm -- Sweden (Scandinavia)