韩亚银行北京分行:求圆周率的计算公式

不是吧

古人计算圆周率，一般是用割圆法。即用圆的内接或外切正多边形来逼近圆的周长。Archimedes用正96边形得到圆周率小数点后3位的精度；刘徽用正3072边形得到5位精度；Ludolph Van Ceulen用正262边形得到了35位精度。

第一类算法：arctan 的级数展开
PI/4 = 4 arctan(1/5) - arctan(1/239) (1)
arctan(x) = x - x3/3 + x5/5 - x7/7 + .... (2)
很容易想到，要得到超高精度的 PI 值，实数在计算机中必须以数组的形式进行存取，数组的大小跟所需的有效位数成正比。在这个算法中，PI 的有效位数 n 随 (2) 的求和项数线性增加。而为计算 (2) 中的每一项，需要进行超高精度实数除以小整数(52, 2392, 2k+1)的循环，循环所需次数也跟 n 成正比。所以，这个算法总的时间复杂度为 O(n2)。

这个算法的优点是简单，而且只需要进行整数运算。下面给出我写的算 PI 程序。在程序中，我采用了一些提高速度的措施：超高精度实数以数组的形式进行存取，数组元素的类型为 64 位整数(long long)，每个元素储存 12 个十进制位；对 xk (x = 1/5, 1/239) 的头部和尾部的 0 的数量进行估计，只对非 0 的部分进行计算。

pi.cpp C++ 源程序，在 Linux 下以 g++ pi.cpp -o pi -O2 编译
pi.s 在 g++ 生成的汇编程序的基础上进行修改，速度更快，在 Linux 下以 g++ pi.s -o pi 编译
另外，还有许多跟 (1) 类似的式子，但不常用。例如：

PI/4 = arctan(1/2) + arctan(1/3)
PI/4 = 8 arctan(1/10) - arctan(1/239) - 4 arctan(1/515)
第二类算法：与 1/PI 有关的级数
1/PI = (sqrt(8) / 9801) sumk=0~inf { [(4k)! (1103 + 26390k)] / [(k!)4 3964k] } (Ramanujan)
1/PI = (sqrt(10005) / 4270934400) sumk=0~inf { [(6k)! (13591409 + 545140134k)] / [(k!)3 (3k)! (-640320)3k] } (Chudnovsky)
以上两个级数(还有其它类似形式的级数，但不常用)比起 arctan 的泰勒级数要复杂得多。虽然仍然是线性收敛，总的时间复杂度也仍然是 O(n2)，但它们的收敛速度相当快， (Ramanujan) 每项可以增加 8 位有效数字， (Chudnovsky) 每项可以增加 14 位。

在这个算法中，除了要进行超高精度实数(数组形式)和小整数的运算外，还有一次超高精度实数的开方和倒数的运算，这需要用到 FFT(快速傅立叶变换)，在下文叙述。

第三类算法：算术几何平均值和迭代法
算术几何平均值(Arithmetic-Geometric Mean, AGM) M(a, b) 定义如下：

a0 = a, b0 = b
ak = (ak-1 + bk-1) / 2, bk = sqrt(ak-1 bk-1)
M(a, b) = limk->inf ak = limk->inf bk
然后，由椭圆积分的一系列理论(抱歉，过程我不懂)可以推导出如下公式：

a0 = 1, b0 = 1 / sqrt(2)
1/PI = { 1 - sumk=0~inf [2k (ak2 - bk2)] } / 2M(a0, b0)2 (AGM)
根据这条公式可以制定适当的迭代算法。在迭代过程中，有效位数随迭代次数按 2 的指数增加，即每迭代一次有效位数乘 2。算法中的超高精度实数的乘、除、开方等运算需要使用 FFT，在下文叙述。综合考虑 FFT 的时间复杂度，整个算法的时间复杂度约为 O(n log(n)2)。

除了 (AGM) 以外，还有其它的迭代序列，它们具有同样的时间复杂度。例如下面的这个序列将按 4 的指数收敛到 1/PI：

y0 = sqrt(2) - 1, a0 = 6 - 4 sqrt(2)
yk = [1 - sqrt(sqrt(1 - yk-14))] / [1 + sqrt(sqrt(1 - yk-14))], ak = (1 + yk)4 ak-1 - 22k+1 yk (1 + yk + yk2)
1/PI = limk->inf ak (Borwein)
FFT
如上所述，第二和第三类算法不可避免地要涉及超高精度实数(数组形式存取的多位数)的乘、除、开方等运算。多位数乘法如果按照常规方法来计算，逐位相乘然后相加，其时间复杂度将达到 O(n2)。使用 FFT 可大大减少计算量。

设有复数数组 a[k] 和 b[k] (k=0~n-1)，正向和反向的离散傅立叶变换(DFT)定义如下： (i = sqrt(-1))

b = FFTforward(a) : b[k] = sumj=0~n-1 ( a[j] e-i*j*2PI*k/n ) (3)
b = FFTbackward(a) : b[k] = (1/n) sumj=0~n-1 ( a[j] ei*j*2PI*k/n ) (4)
(3) 和 (4) 中的 (1/n) 可以放在任何一个式子中，也可以拆成 (1/sqrt(n)) 同时放在两个式子中，目的是保证正向和反向傅立叶变换以后不会相差一个因子。

当 n 的所有素因子均为小整数，尤其是当 n 为 2 的整数次幂的时候，使用适当的算法经过仔细的协调，可以避免多余的计算，使离散傅立叶变换 (3) 和 (4) 减少至 O(n log(n)) 的时间复杂度，即所谓的快速傅立叶变换(FFT)。具体的细节请查阅相关书籍。下面给出我写的一段 FFT 程序，仅供参考。另外也有已经开发的 FFT 函数库，例如 FFTW ，可以直接使用。

fft.cpp FFT 的 C++ 源程序
利用 FFT，要计算 n1 位和 n2 位的两个多位数乘法，可以这样进行：开辟两个长度为 n(n>=n1+n2，取 2m 最佳) 的复数数组，将两个多位数从低位到高位分别填入，高位补 0。对两个数组分别进行正向傅立叶变换。将得到的两个变换后的数组的对应项相乘，然后进行反向傅立叶变换，最后得到一个结果数组。由于傅立叶变换是在复数域中进行的，因此还要对结果数组进行取整和进位，才能得到最终的乘积。

值得留意的是傅立叶变换的精度问题。我们知道，在计算机中实数用单精度数或双精度数表示，它们会存在一定的误差。在计算多位数乘法时，n 往往是一个很大的数字，傅立叶变换过程中需要对数组的每一项进行求和，如何保证精度带来的误差不会因为求和而超出允许的范围？我的观点是必须使用双精度实数，而且由于统计特性，精度带来的误差在求和过程中不会很大，一般不会影响计算的正确性。如果需要保证计算的正确性，我想到两种检查方法。第一种是取模验算。例如，如果乘数和被乘数对 17 的模分别是 8 和 6，那么积对 17 的模就应该是 14。第二种是检查运算结果中浮点数偏离整数的最大值。如果偏差只有比如 10-3 量级，我们可以认为这个尺度的乘法运算很安全；如果偏差达到 0.5，说明运算已经出错了；如果偏差达到 0.1 量级，那也比较危险，也许换个别的乘数和被乘数就溢出了。

多位数的倒数和开方可以通过牛顿迭代求根法转化为乘法运算。例如，要计算 x = 1/a ，根据牛顿迭代法令 f(x) = 1/x - a ，可以得到以下迭代序列：

x0 ~= 1/a
xk = xk-1 - f(xk-1)/f'(xk-1) = 2xk-1 - axk-12 (5)
要计算 x = sqrt(a) ，可以先计算 x = 1 / sqrt(a) ，令 f(x) = 1/x2 - a ，可以得到以下迭代序列：

x0 ~= 1 / sqrt(a)
xk = xk-1 - f(xk-1)/f'(xk-1) = (3/2)xk-1 - (1/2)axk-13 (6)
(5) 和 (6) 均以 2 的指数收敛到所求结果。还存在其它更复杂一些的迭代序列，它们以更高的指数收敛，在此不提。不过需要提醒的是，跟 (AGM) 不同，这里 (5) 和 (6) 中的 x0 只是 1/a 和 1 / sqrt(a) 的约值，在前几次的迭代中不必进行满 n 位数的乘法运算，因而可以减少计算量。

示例程序
作为 AGM 和 FFT 算 PI 的完整过程演示，这里是我新写的算 PI 程序。很遗憾，我的程序比网上可以找到的其它算 PI 程序慢大约 100 倍，而且消耗更多的内存。:-( 目前还不清楚它的瓶颈所在。不管怎么说，它总算是我的第一个 AGM 和 FFT 算 PI 程序，祝贺！:-)

faint-pi-1.0.3.tar.gz C 源程序，在 Linux 下以 gcc -std=c99 *.c -o pi -lm -O3 编译
综述
以上介绍了三类算 PI 的算法。第一类算法的速度最慢，基本上已经过时。后两类算法的速度目前相差不大，最为常用。迭代法虽然在时间复杂度上有理论上的优势，但实现起来较为复杂，实际上也并不见得比 1/PI 级数法快。

限于作者水平，本文观点肯定存在有待指正的地方，欢迎讨论。(2004.12.31)

用极限的方法!在圆中用三角形进行分割!

操!没有那么复杂!355/113.;自己算!

∏=3.141592653589793238462643383279502884197169399375105820974944592307816406286208998628034825342117067982148086513282306647093844609550582231725359408128481117450284102701938521105559644622948954930381964428810975665933446128475648233786783165271201909145648566923460348610454326648213393607260249141273724587006606315588174881520920962829254091715364367892590360011330530548820466521384146951941511609433057270365759591953092186117381932611793105118548074462379962749567351885752724891227938183011949129833673362440656643086021394946395224737190702179860943702770539217176293176752384674818467669405132000568127145263560827785771342757789609173637178721468440901224953430146549585371050792279689258923542019956112129021960864034418159813629774771309960518707211349999998372978049951059731732816096318595024459455346908302642522308253344685035261931188171010003137838752886587533208381420617177669147303598253490428755468731159562863882353787593751957781857780532171226806613001927876611195909216420198938095257201065485863278865936153381827968230301952
03530185296899577362259941389124972177528347913151
55748572424541506959508295331168617278558890750983
81754637464939319255060400927701671139009848824012
85836160356370766010471018194295559619894676783744
94482553797747268471040475346462080466842590694912
93313677028989152104752162056966024058038150193511
25338243003558764024749647326391419927260426992279
67823547816360093417216412199245863150302861829745
55706749838505494588586926995690927210797509302955
32116534498720275596023648066549911988183479775356
63698074265425278625518184175746728909777727938000
81647060016145249192173217214772350141441973568548
16136115735255213347574184946843852332390739414333
45477624168625189835694855620992192221842725502542
56887671790494601653466804988627232791786085784383
82796797668145410095388378636095068006422512520511
73929848960841284886269456042419652850222106611863
06744278622039194945047123713786960956364371917287
46776465757396241389086583264599581339047802759009

94657640789512694683983525957098258226205224894077
26719478268482601476990902640136394437455305068203
49625245174939965143142980919065925093722169646151
57098583874105978859597729754989301617539284681382
68683868942774155991855925245953959431049972524680
84598727364469584865383673622262609912460805124388
43904512441365497627807977156914359977001296160894
41694868555848406353422072225828488648158456028506
01684273945226746767889525213852254995466672782398
64565961163548862305774564980355936345681743241125
15076069479451096596094025228879710893145669136867
22874894056010150330861792868092087476091782493858
90097149096759852613655497818931297848216829989487
22658804857564014270477555132379641451523746234364
54285844479526586782105114135473573952311342716610
21359695362314429524849371871101457654035902799344
03742007310578539062198387447808478489683321445713
86875194350643021845319104848100537061468067491927
81911979399520614196634287544406437451237181921799
98391015919561814675142691239748940907186494231961

56794520809514655022523160388193014209376213785595
66389377870830390697920773467221825625996615014215
03068038447734549202605414665925201497442850732518
66600213243408819071048633173464965145390579626856
10055081066587969981635747363840525714591028970641
40110971206280439039759515677157700420337869936007
23055876317635942187312514712053292819182618612586
73215791984148488291644706095752706957220917567116
72291098169091528017350671274858322287183520935396
57251210835791513698820914442100675103346711031412
67111369908658516398315019701651511685171437657618
35155650884909989859982387345528331635507647918535
89322618548963213293308985706420467525907091548141
65498594616371802709819943099244889575712828905923
23326097299712084433573265489382391193259746366730
58360414281388303203824903758985243744170291327656
18093773444030707469211201913020330380197621101100
44929321516084244485963766983895228684783123552658
21314495768572624334418930396864262434107732269780
28073189154411010446823252716201052652272111660396

66557309254711055785376346682065310989652691862056
47693125705863566201855810072936065987648611791045
33488503461136576867532494416680396265797877185560
84552965412665408530614344431858676975145661406800
70023787765913440171274947042056223053899456131407
11270004078547332699390814546646458807972708266830
63432858785698305235808933065757406795457163775254
20211495576158140025012622859413021647155097925923
09907965473761255176567513575178296664547791745011
29961489030463994713296210734043751895735961458901
93897131117904297828564750320319869151402870808599
04801094121472213179476477726224142548545403321571
85306142288137585043063321751829798662237172159160
77166925474873898665494945011465406284336639379003
97692656721463853067360965712091807638327166416274
88880078692560290228472104031721186082041900042296
61711963779213375751149595015660496318629472654736
42523081770367515906735023507283540567040386743513
62222477158915049530984448933309634087807693259939
78054193414473774418426312986080998886874132604721

56951623965864573021631598193195167353812974167729
47867242292465436680098067692823828068996400482435
40370141631496589794092432378969070697794223625082
21688957383798623001593776471651228935786015881617
55782973523344604281512627203734314653197777416031
99066554187639792933441952154134189948544473456738
31624993419131814809277771038638773431772075456545
32207770921201905166096280490926360197598828161332
31666365286193266863360627356763035447762803504507
77235547105859548702790814356240145171806246436267
94561275318134078330336254232783944975382437205835
31147711992606381334677687969597030983391307710987
04085913374641442822772634659470474587847787201927
71528073176790770715721344473060570073349243693113
83504931631284042512192565179806941135280131470130
47816437885185290928545201165839341965621349143415
95625865865570552690496520985803385072242648293972
85847831630577775606888764462482468579260395352773
48030480290058760758251047470916439613626760449256
27420420832085661190625454337213153595845068772460

29016187667952406163425225771954291629919306455377
99140373404328752628889639958794757291746426357455
25407909145135711136941091193932519107602082520261
87985318877058429725916778131496990090192116971737
27847684726860849003377024242916513005005168323364
35038951702989392233451722013812806965011784408745
19601212285993716231301711444846409038906449544400
61986907548516026327505298349187407866808818338510
22833450850486082503930213321971551843063545500766
82829493041377655279397517546139539846833936383047
46119966538581538420568533862186725233402830871123
28278921250771262946322956398989893582116745627010
21835646220134967151881909730381198004973407239610
36854066431939509790190699639552453005450580685501
95673022921913933918568034490398205955100226353536
19204199474553859381023439554495977837790237421617
27111723643435439478221818528624085140066604433258
88569867054315470696574745855033232334210730154594
05165537906866273337995851156257843229882737231989
87571415957811196358330059408730681216028764962867

44604774649159950549737425626901049037781986835938
14657412680492564879855614537234786733039046883834
36346553794986419270563872931748723320837601123029
91136793862708943879936201629515413371424892830722
01269014754668476535761647737946752004907571555278
19653621323926406160136358155907422020203187277605
27721900556148425551879253034351398442532234157623
36106425063904975008656271095359194658975141310348
22769306247435363256916078154781811528436679570611
08615331504452127473924544945423682886061340841486
37767009612071512491404302725386076482363414334623
51897576645216413767969031495019108575984423919862
91642193994907236234646844117394032659184044378051
33389452574239950829659122850855582157250310712570
12668302402929525220118726767562204154205161841634
84756516999811614101002996078386909291603028840026
91041407928862150784245167090870006992821206604183
71806535567252532567532861291042487761825829765157
95984703562226293486003415872298053498965022629174
87882027342092222453398562647669149055628425039127

57710284027998066365825488926488025456610172967026
64076559042909945681506526530537182941270336931378
51786090407086671149655834343476933857817113864558
73678123014587687126603489139095620099393610310291
61615288138437909904231747336394804575931493140529
76347574811935670911013775172100803155902485309066
92037671922033229094334676851422144773793937517034
43661991040337511173547191855046449026365512816228
82446257591633303910722538374218214088350865739177
15096828874782656995995744906617583441375223970968
34080053559849175417381883999446974867626551658276
58483588453142775687900290951702835297163445621296
40435231176006651012412006597558512761785838292041
97484423608007193045761893234922927965019875187212
72675079812554709589045563579212210333466974992356
30254947802490114195212382815309114079073860251522
74299581807247162591668545133312394804947079119153
26734302824418604142636395480004480026704962482017
92896476697583183271314251702969234889627668440323
26092752496035799646925650493681836090032380929345

95889706953653494060340216654437558900456328822505
45255640564482465151875471196218443965825337543885
69094113031509526179378002974120766514793942590298
96959469955657612186561967337862362561252163208628
69222103274889218654364802296780705765615144632046
92790682120738837781423356282360896320806822246801
22482611771858963814091839036736722208883215137556
00372798394004152970028783076670944474560134556417
25437090697939612257142989467154357846878861444581
23145935719849225284716050492212424701412147805734
55105008019086996033027634787081081754501193071412
23390866393833952942578690507643100638351983438934
15961318543475464955697810382930971646514384070070
73604112373599843452251610507027056235266012764848
30840761183013052793205427462865403603674532865105
70658748822569815793678976697422057505968344086973
50201410206723585020072452256326513410559240190274
21624843914035998953539459094407046912091409387001
26456001623742880210927645793106579229552498872758
46101264836999892256959688159205600101655256