J階梅欣公式及其算法分析

1、J階梅欽公式及其簡(jiǎn)式的算法分析與應(yīng)用吳敏金在諸多的反正切和式應(yīng)用于計(jì)算圓周率pi中，梅欽公式1占有特別重要的位置。本文將在作者2的基礎(chǔ)上，進(jìn)一步將梅欽公式加以拓廣，提出j階梅欽公式及其簡(jiǎn)式，它包含了日本人在1981年將圓周率pi計(jì)算到2*106位所采用的公式（即1階梅欽公式），導(dǎo)出其實(shí)現(xiàn)的算法，并給出基于萬進(jìn)制數(shù)的計(jì)算圓周率pi的應(yīng)用結(jié)果。一、 反正切和式的回顧所謂反正切和式2為關(guān)系式arctan 1/a=arctan 1/b+arctan 1/c(1)其中a,b,c為正實(shí)數(shù)。在應(yīng)用于計(jì)算圓周率pi時(shí)，要求a,b,c取正整數(shù)（或有理分?jǐn)?shù)）。簡(jiǎn)記為 a=b+c(2)可以證明2：a=(bc-1)/

2、(b+c)(3)1+a2=(b-a)(c-a)(4)反正切和式有多種形式，如：a=b-c表示arctan 1/a=arctan 1/b-arctan 1/c，此時(shí)，a=(bc+1)/(c-b)(5)。又如,a=n*b表示arctan 1/a=n*arctan 1/b。（注意：在 中，n,b不可交換。符號(hào)“*”不是算術(shù)乘“· ”，是n個(gè)反正切的和）。例如,梅欽公式:1=4*5-239，而日本人用的則是：1=8*10-4*515-239。其他的見2。為了采用反正切展開式而優(yōu)化計(jì)算圓周率pi，人們不斷探索新的反正切和式，文獻(xiàn)2借用式(3,4)導(dǎo)出了一系列新的反正切和式。如，因子分解法：已知

3、a，求b,c。將(1+a2)分解為m*n，那么b=m+a, c=n+a。本文將從梅欽公式:1=4*5-239出發(fā)，引進(jìn)j階梅欽公式。二、 j階梅欽公式【定理1】對(duì)于任意的正整數(shù)a，有a=2*(2a)-xx=4a3+3a.(2.0)【證明】：事實(shí)上,用式(6)，得a=(2a)2-1)/(4a)-x,即x=(2a)2-1)/(4a)-a。由式(5),得 x=4a3+3a。 【證畢】在梅欽公式:1=4*5-239中，取a=5,用定理1，有5=2*10-515 即得1=8*10-4*515-239(2.1)此稱為1階梅欽公式。進(jìn)而，在1階梅欽公式:1=8*10-4*5-239中，取a=10,用定理1，

4、有10=2*20-4030 即得1=16*20-8*4030-4*515-239(2.2)此稱為2階梅欽公式。在2階梅欽公式:1=16*20-8*4030-4*515-239中，取a=20,用定理1， 20=2*40-48120 即得1=32*40-16*48120-8*4030-4*515-239(2.3)此稱為3階梅欽公式。一般地，有【定理2】j階梅欽公式:1=（4·2j)*(5·2j)-(2(i+1)*xi)-239 。xi=5·2(i-1)·(5·2i)2+3)(2.4)其中，表示求和從i=1到j(luò)。【證明】用歸納法及定理1。留給讀者。綜

5、合上述，0階梅欽公式:1=4*5-2391階梅欽公式: 1=8*10-4*515-2392階梅欽公式：1=16*20-8*4030-4*515-2393階梅欽公式： 1=32*40-16*48120-8*4030-4*515-239及j階梅欽公式(2.4)。三、 j階梅欽公式的簡(jiǎn)式由上面的式(2.4)，可見j階梅欽公式由首項(xiàng)（4·2j）*（5·2j）,末項(xiàng)239及中間的許多過渡項(xiàng)組成。為加速運(yùn)算，可將其末項(xiàng)239及中間的許多過渡項(xiàng)合并成為1=(4·2j）*（5·2j）- wmj(3.1)此為j階梅欽公式簡(jiǎn)式，是一種廣義的梅欽公式（wu-machin）。j

6、階梅欽公式簡(jiǎn)式中的wmj（稱為wu-machin吳梅數(shù)），除了j=0外，通常不為整數(shù)。為pi的精確計(jì)算，mj不能用近似的有限小數(shù)表示，必須用分?jǐn)?shù)形式，其整數(shù)的的分子與分母記為wmj1與wmj2。即wmj=wmj1/wmj2。下面給出吳梅數(shù)wmj的數(shù)值及其迭代算法。首先，由于pi的計(jì)算要達(dá)到幾萬億位，計(jì)算機(jī)高級(jí)語言中的數(shù)據(jù)類型（如整型，長(zhǎng)整型等）已無能為力。對(duì)此，作者引入了新的數(shù)據(jù)類型-萬進(jìn)制數(shù)（是一種新的類與對(duì)象。萬進(jìn)制數(shù)的定義、結(jié)構(gòu)、運(yùn)算及其應(yīng)用另文闡述）。吳梅數(shù)mj將用萬進(jìn)制數(shù)表示。由式(3.1)wmj=(4·2j）*（5·2j）- 1(3.2)對(duì)于給定的j。算法如下：1， 令b=5·2j ;2， 迭代j次計(jì)算b=2*b，用的是迭代式b=(2b)2-1)/(2b)。3， 計(jì)算結(jié)果：wmj=b。j=1,2,3的吳梅數(shù)wmj的分子與分母用16位的萬進(jìn)制數(shù)表示如下(即64位的十進(jìn)制數(shù))：四、 j階梅欽公式及其簡(jiǎn)式應(yīng)用于圓周率的計(jì)算結(jié)果分析與實(shí)踐表明：基于萬進(jìn)制表示方法，借助反正切展開式，用j=0,1,2,3階梅欽公式及其簡(jiǎn)式（wu-machin公式）都能得到pi的正確運(yùn)行結(jié)果，其運(yùn)行的pi萬位數(shù)列于下表。有關(guān)它們的算法分析與比較（如精確位數(shù)N，迭代次數(shù)K，運(yùn)行時(shí)間T）以及