How is pi calculated to many decimals ?<\/b><\/p>\n
There are essentially 3 different methods.<\/p>\n
1) One of the oldest is to use the power series expansion of atan(x) atan(x)=x-x^3\/3+x^5\/5-… together with formulas like pi=16*atan(1\/5)-4*atan(1\/239). This gives about 1.4 decimals per term.<\/p>\n
2) A second is to use formulas coming from Arithmetic-Geometric mean computations. A beautiful compendium of such formulas is given in the book of Borwein and Borwein: Pi and the AGM, Canadian Math. Soc. Series, John Wiley and Sons, New York, 1987. They have the advantage of converging quadratically, i.e. you double the number of decimals per iteration. For instance, to obtain 1 000 000 decimals, around 20 iterations are sufficient. The disadvantage is that you need FFT type multiplication to get a reasonable speed, and this is not so easy to program.<\/p>\n
3) A third one comes from the theory of complex multiplication of elliptic curves, and was discovered by S. Ramanujan. This gives a number of beautiful formulas, but the most useful was missed by Ramanujan and discovered by the Chudnovsky’s. It is the following (slightly modified for ease of programming):<\/p>\n
Set k1=545140134;k2=13591409;k3=640320;k4=100100025;k5=327843840;k6=53360;<\/i><\/p>\n
Then in AmsTeX notation<\/p>\n
$pi=frac{k6sqrt(k3)}{S}$, where<\/i><\/p>\n
$$S=sum_{n=0}^infty (-1)^nfrac{(6n)!(k2+nk1)}{n!^3(3n)!(8k4k5)^n}$$<\/i><\/p>\n
The great advantages of this formula are that<\/p>\n
1) It converges linearly, but very fast (more than 14 decimal digits per term).<\/p>\n
2) The way it is written, all operations to compute S can be programmed very simply since it only involves multiplication\/division by single precision numbers. This is why the constant 8k4k5 appearing in the denominator has been written this way instead of 262537412640768000.<\/p>\n
This is how the Chudnovsky’s have computed several billion decimals.<\/p>\n
Question: how can I get a C program which computes pi?<\/b><\/p>\n
Answer: if you are too lazy to use the hints above, you can use the following 160 character C program which computes pi to 800 decimal digits. If you want more, it is easy to modify, but you have to understand how it works first.<\/p>\n
int a=10000,b,c=2800,d,e,f[2801],g;main(){for(;b-c;)f[b++]=a\/5;
\n for(;d=0,g=c*2;c-=14,printf(“%.4d”,e+d\/a),e=d%a)for(b=c;d+=f[b]*a,
\n f[b]=d%–g,d\/=g–,–b;d*=b);}<\/i> <\/p>\n
References :<\/p>\n
J. M. Borwein, P. B. Borwein, and D. H. Bailey,
\n“Ramanujan,Modular Equations, and Approximations to Pi”,<\/i>
\nAmerican Mathematical Monthly, vol. 96, no. 3 (March 1989), p. 201 – 220.<\/p>\n
P. Beckman
\nA history of pi<\/i>
\nGolem Press, CO, 1971 (fourth edition 1977)<\/p>\n
J.M. Borwein and P.B. Borwein
\nThe arithmetic-geometric mean and fast computation of elementary functions<\/i>
\nSIAM Review, Vol. 26, 1984, pp. 351-366<\/p>\n
J.M. Borwein and P.B. Borwein
\nMore quadratically converging algorithms for pi<\/i>
\nMathematics of Computation, Vol. 46, 1986, pp. 247-253<\/p>\n
J.M. Borwein and P.B. Borwein
\nPi and the AGM – a study in analytic number theory and computational complexity<\/i>
\nWiley, New York, 1987<\/p>\n
Shlomo Breuer and Gideon Zwas
\nMathematical-educational aspects of the computation of pi<\/i>
\nInt. J. Math. Educ. Sci. Technol., Vol. 15, No. 2, 1984,
\npp. 231-244<\/p>\n
David Chudnovsky and Gregory Chudnovsky
\nThe computation of classical constants, Columbia University,<\/i>
\nProc. Natl. Acad. Sci. USA, Vol. 86, 1989.<\/p>\n
Y. Kanada and Y. Tamura
\nCalculation of pi to 10,013,395 decimal places based on the Gauss-Legendre algorithm and Gauss arctangent relation<\/i>
\nComputer Centre, University of Tokyo, 1983<\/p>\n
Morris Newman and Daniel Shanks
\nOn a sequence arising in series for pi<\/i>
\nMathematics of computation, Vol. 42, No. 165, Jan 1984,
\npp. 199-217<\/p>\n
E. Salamin
\nComputation of pi using arithmetic-geometric mean<\/i>
\nMathematics of Computation, Vol. 30, 1976, pp. 565-570<\/p>\n
D. Shanks and J.W. Wrench, Jr.
\nCalculation of pi to 100,000 decimals<\/i>
\nMathematics of Computation, Vol. 16, 1962, pp. 76-99<\/p>\n
Daniel Shanks
\nDihedral quartic approximations and series for pi<\/i>
\nJ. Number Theory, Vol. 14, 1982, pp.397-423<\/p>\n
David Singmaster
\nThe legal values of pi<\/i>
\nThe Mathematical Intelligencer, Vol. 7, No. 2, 1985<\/p>\n
Stan Wagon
\nIs pi normal?<\/i>
\nThe Mathematical Intelligencer, Vol. 7, No. 3, 1985<\/p>\n
J.W. Wrench, Jr.
\nThe evolution of extended decimal approximations to pi<\/i>
\nThe Mathematics Teacher, Vol. 53, 1960, pp. 644-650<\/p>\n","protected":false},"excerpt":{"rendered":"
How is pi calculated to many decimals ? There are essentially 3 different methods. 1) One of the oldest is to use the power series<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"chat","meta":{"footnotes":""},"categories":[],"tags":[55],"class_list":["post-221","post","type-post","status-publish","format-chat","hentry","tag-curious","post_format-post-format-chat"],"_links":{"self":[{"href":"https:\/\/delascabezas.com\/blog\/index.php\/wp-json\/wp\/v2\/posts\/221","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/delascabezas.com\/blog\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/delascabezas.com\/blog\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/delascabezas.com\/blog\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/delascabezas.com\/blog\/index.php\/wp-json\/wp\/v2\/comments?post=221"}],"version-history":[{"count":1,"href":"https:\/\/delascabezas.com\/blog\/index.php\/wp-json\/wp\/v2\/posts\/221\/revisions"}],"predecessor-version":[{"id":2794,"href":"https:\/\/delascabezas.com\/blog\/index.php\/wp-json\/wp\/v2\/posts\/221\/revisions\/2794"}],"wp:attachment":[{"href":"https:\/\/delascabezas.com\/blog\/index.php\/wp-json\/wp\/v2\/media?parent=221"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/delascabezas.com\/blog\/index.php\/wp-json\/wp\/v2\/categories?post=221"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/delascabezas.com\/blog\/index.php\/wp-json\/wp\/v2\/tags?post=221"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}