longpi.htm
来自「“常见程式演算”主要收集一些常见的程式练习题目」· HTM 代码 · 共 185 行
HTM
185 行
<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
<html>
<head>
<link rel="stylesheet" href="css/stdlayout.css" type="text/css">
<link rel="stylesheet" href="css/print.css" type="text/css">
<meta content="text/html; charset=gb2312" http-equiv="content-type">
<title>长 PI</title>
</head>
<body>
<h3><a href="http://caterpillar.onlyfun.net/GossipCN/index.html">From
Gossip@caterpillar</a></h3>
<h1><a href="AlgorithmGossip.htm">Algorithm Gossip: 长 PI</a></h1>
<h2>说明</h2>
圆周率后的小数位数是无止境的，如何使用电脑来计算这无止境的小数是一些数学家与程式设计师所感兴趣的，在这边介绍一个公式配合 <a href="BigNumber.htm">大数运算</a>，可以计算指定位数的圆周率。<br>
<h2>解法</h2>
首先介绍J.Marchin的圆周率公式：<br>
<div style="margin-left: 40px;"><span style="font-weight: bold; font-family: Courier New,Courier,monospace;">PI = [16/5 - 16 / (3*5<sup>3</sup>) + 16 / (5*5<sup>5</sup>) - 16 / (7*5<sup>7</sup>) + ......] -</span><br style="font-weight: bold; font-family: Courier New,Courier,monospace;">
<span style="font-weight: bold; font-family: Courier New,Courier,monospace;"> [4/239 - 4/(3*239<sup>3</sup>) + 4/(5*239<sup>5</sup>) - 4/(7*239<sup>7</sup>) + ......]</span><br>
</div>
<br>
可以将这个公式整理为：<br>
<div style="margin-left: 40px;"><span style="font-weight: bold; font-family: Courier New,Courier,monospace;">PI = [16/5 - 4/239] - [16/(5<sup>3</sup>) - 4/(239<sup>3</sup>)]/3+ [16/(5<sup>5</sup>) - 4/(239<sup>5</sup>)]/5 + ......</span><br>
</div>
<br>
也就是说第n项，若为奇数则为正数，为偶数则为负数，而项数表示方式为：<br>
<div style="margin-left: 40px;"><span style="font-weight: bold; font-family: Courier New,Courier,monospace;">[16/5<sup>2*n-1</sup> - 4/239<sup>2*n-1</sup>] / (2*n-1)</span><br>
</div>
<br>
如果我们要计算圆周率至10的负L次方，由于[16/5<sup>2*n-1</sup> - 4/239<sup>2*n-1</sup>]中16/5<sup>2*n-1</sup>比4/239<sup>2*n-1</sup>来的大，具有决定性，所以表示至少必须计算至第n项：<br>
<div style="margin-left: 40px;"><span style="font-weight: bold; font-family: Courier New,Courier,monospace;">[16/5<sup>2*n-1</sup> ] / (2*n-1) = 10<sup>-L</sup></span><br>
</div>
<br>
将上面的等式取log并经过化简，我们可以求得：<br>
<div style="margin-left: 40px;"><span style="font-weight: bold; font-family: Courier New,Courier,monospace;">n = L / (2log5) = L / 1.39794</span><br>
</div>
<br>
所以若要求精确度至小数后L位数，则只要求至公式的第n项，其中n等于：<br>
<div style="margin-left: 40px;"><span style="font-weight: bold; font-family: Courier New,Courier,monospace;">n = [L/1.39794] + 1</span><br>
</div>
<br>
在上式中[]为高斯符号，也就是取至整数（不大于L/1.39794的整数）；为了计简方便，可以在程式中使用下面这个公式来计简第n项：<br>
<div style="margin-left: 40px;"><span style="font-weight: bold; font-family: Courier New,Courier,monospace;">[</span><big style="font-weight: bold; font-family: Courier New,Courier,monospace;">W</big><span style="font-weight: bold; font-family: Courier New,Courier,monospace;"><sub>n</sub>-1/5</span><sup style="font-weight: bold; font-family: Courier New,Courier,monospace;">2</sup><span style="font-weight: bold; font-family: Courier New,Courier,monospace;">- </span><big style="font-weight: bold; font-family: Courier New,Courier,monospace;">V</big><span style="font-weight: bold; font-family: Courier New,Courier,monospace;"><sub>n</sub>-1 / (239</span><sup style="font-weight: bold; font-family: Courier New,Courier,monospace;">2</sup><span style="font-weight: bold; font-family: Courier New,Courier,monospace;">)] / (2*n-1)</span><br>
</div>
<br>
这个公式的演算法配合大数运算函式的演算法为：
<div style="margin-left: 40px; font-weight: bold;"><span style="font-family: Courier New,Courier,monospace;">div(w, 25, w); </span><br style="font-family: Courier New,Courier,monospace;">
<span style="font-family: Courier New,Courier,monospace;">
div(v, 239, v); </span><br style="font-family: Courier New,Courier,monospace;">
<span style="font-family: Courier New,Courier,monospace;">
div(v, 239, v); </span><br style="font-family: Courier New,Courier,monospace;">
<span style="font-family: Courier New,Courier,monospace;">
sub(w, v, q); </span><br style="font-family: Courier New,Courier,monospace;">
<span style="font-family: Courier New,Courier,monospace;">
div(q, 2*k-1, q) </span><br>
</div>
<br>
至于大数运算的演算法，请参考之前的文章，必须注意的是在输出时，由于是输出阵列中的整数值，如果阵列中整数位数不满四位，则必须补上0，在C语言中只要
使用格式指定字%04d，使得不足位数部份自动补上0再输出，至于Java的部份，使用 NumberFormat来作格式化。<br>
<br>
您可以参考 <a href="http://crd.lbl.gov/%7Edhbailey/">这个网站</a> 有关于另一个用公式求PI的说明，它的实作在 <a href="http://crd.lbl.gov/%7Edhbailey/piqp.c">这边</a>。<br>
<br>
<h2> 实作</h2>
<ul>
<li> C
</li>
</ul>
<pre>#include <stdio.h> <br>#define L 1000 <br>#define N L/4+1 <br><br>// L 为位数，N是array长度 <br><br>void add(int*, int*, int*); <br>void sub(int*, int*, int*); <br>void div(int*, int, int*); <br><br>int main(void) { <br> int s[N+3] = {0}; <br> int w[N+3] = {0}; <br> int v[N+3] = {0}; <br> int q[N+3] = {0}; <br> int n = (int)(L/1.39793 + 1); <br> int k; <br><br> w[0] = 16*5; <br> v[0] = 4*239; <br><br> for(k = 1; k <= n; k++) { <br> // 套用公式 <br> div(w, 25, w); <br> div(v, 239, v); <br> div(v, 239, v); <br> sub(w, v, q); <br> div(q, 2*k-1, q); <br><br> if(k%2) // 奇数项 <br> add(s, q, s); <br> else // 偶数项 <br> sub(s, q, s); <br> } <br><br> printf("%d.", s[0]); <br> for(k = 1; k < N; k++) <br> printf("%04d", s[k]); <br> <br> printf("\n"); <br><br> return 0; <br>} <br><br>void add(int *a, int *b, int *c) { <br> int i, carry = 0; <br><br> for(i = N+1; i >= 0; i--) { <br> c[i] = a[i] + b[i] + carry; <br> if(c[i] < 10000) <br> carry = 0; <br> else { // 进位 <br> c[i] = c[i] - 10000; <br> carry = 1; <br> } <br> } <br>} <br><br>void sub(int *a, int *b, int *c) { <br> int i, borrow = 0; <br><br> for(i = N+1; i >= 0; i--) { <br> c[i] = a[i] - b[i] - borrow; <br> if(c[i] >= 0) <br> borrow = 0; <br> else { // 借位 <br> c[i] = c[i] + 10000; <br> borrow = 1; <br> } <br> } <br>} <br><br>void div(int *a, int b, int *c) { // b 为除数 <br> int i, tmp, remain = 0; <br><br> for(i = 0; i <= N+1; i++) { <br> tmp = a[i] + remain; <br> c[i] = tmp / b; <br> remain = (tmp % b) * 10000; <br> } <br>} <br></pre>
<br>
<ul>
<li> Java
</li>
</ul>
<pre>import java.text.NumberFormat;<br><br>public class LongPI {<br> public static void main(String[] args) {<br> final int L = 1000;<br> final int N = L/4+1;<br> int[] s = new int[N+3];<br> int[] w = new int[N+3];<br> int[] v = new int[N+3];<br> int[] q = new int[N+3];<br><br> int n = (int)(L/1.39793 + 1); <br> <br> w[0] = 16*5; <br> v[0] = 4*239; <br> <br> for(int k = 1; k <= n; k++) { <br> // 套用公式 <br> w = BigNumber.div(w, 25); <br> v = BigNumber.div(v, 239); <br> v = BigNumber.div(v, 239);<br> q = BigNumber.sub(w, v); <br> q = BigNumber.div(q, 2*k-1); <br><br> if(k % 2 == 1) // 奇数项 <br> s = BigNumber.add(s, q); <br> else // 偶数项 <br> s = BigNumber.sub(s, q);<br> } <br> <br> NumberFormat nf = NumberFormat.getInstance();<br> nf.setMinimumIntegerDigits(4);<br> <br> System.out.print(s[0] + "."); <br> for(int k = 1; k < N; k++) <br> System.out.print(nf.format(s[k])); <br> <br> System.out.println(); <br> }<br>}</pre>
<br>
<br>
<br>
</body>
</html>
⌨️ 快捷键说明
复制代码Ctrl + C
搜索代码Ctrl + F
全屏模式F11
增大字号Ctrl + =
减小字号Ctrl + -
显示快捷键?