\( \newcommand{\ord}[1]{\mathcal{O}\left(#1\right)} \newcommand{\abs}[1]{\lvert #1 \rvert} \newcommand{\floor}[1]{\lfloor #1 \rfloor} \newcommand{\ceil}[1]{\lceil #1 \rceil} \newcommand{\opord}{\operatorname{\mathcal{O}}} \newcommand{\argmax}{\operatorname{arg\,max}} \newcommand{\str}[1]{\texttt{"#1"}} \)

2016年11月3日 星期四

[ Pi algorithms - John Machin's formula ] 梅欽公式計算圓周率

我們知道
$$\frac{\pi}{4}= \arctan 1$$
而$\arctan(x)$的泰勒展開式長這樣
$$\arctan(x)=x-\frac{x^3}{3}+\frac{x^5}{5}-\frac{x^7}{7}+\frac{x^9}{9}- \cdots \; (x \leq 1)$$
故可以求出莱布尼茨公式如下:
$$\frac{\pi}{4}= 1 \,-\, \frac{1}{3} \,+\, \frac{1}{5} \,-\, \frac{1}{7} \,+\, \frac{1}{9} \,-\, \cdots$$
但是這用來計算$\pi$到小數點後指定位數是非常困難的,因此有了以下的梅欽公式:
$$\frac{\pi}{4} = 4 \arctan \frac{1}{5} - \arctan \frac{1}{239}$$
再用泰勒展開,可以得到:
$$\pi=(\frac{16}{5} - \frac{16} {3*5^3} + \frac{16}{5 * 5^5} - \frac{16} {7 * 5^7} + \cdots) \\ - (\frac{4}{239} - \frac{4}{3 * 239^3} + \frac{4}{5 * 239^5} - \frac{4}{7 * 239^7} + \cdots)$$
可以將這個公式整理為:
$$\pi=\frac{\frac{16}{5} - \frac{4}{239}}{1} -\frac{\frac{16}{5^3} - \frac{4}{239^3}}{3} + \frac{\frac{16}{5^5} - \frac{4}{239^5}}{5} - \cdots$$
如果我們要計算圓周率至10的負$L$次方,由於$\frac{16}{5^{2*n-1}} - \frac{4}{239^{2*n-1}}$中$\frac{16}{5^{2*n-1}}$比$\frac{4}{239^{2*n-1}}$來的大,具有決定性,所以表示至少必須計算至第n項:
$$\frac{16}{(2*n-1)*5^{2*n-1}}=10^{-L}$$
將上面的等式取log並經過化簡,我們可以求得(誤差什麼得先不管它):
$$n =\frac{L}{2log_{10} 5} = \frac{L}{1.39794}$$
這樣就可以計算$\pi$到小數點後第$L$位了

這裡有其他可以快速算出圓周率的梅欽類公式
http://jeux-et-mathematiques.davalan.org/calc/formulespi.pdf