pi的任意精度求解 C++

用线性表实现 pi 的任意精度求解（内存域内）

先来看一下 pi 的普通求解方法，即根据下面的公式进行求解：

pi/2 = 1+1/3+1/3*2/5 + 1/3*2/5*3/7 + 1/3*2/5*3/7*4/9+...... ,进而得出

pi=2*(1+1/3+1/3*2/5 + 1/3*2/5*3/7 + 1/3*2/5*3/7*4/9+...... )

实现代码如下：

#include<iostream>
using namespace std;


// pi的计算公式： pi/2 = 1+1/3+1/3*2/5 + 1/3*2/5*3/7 + 1/3*2/5*3/7*4/9+......
double Calculate_Pi()
{
	double pi = 1;
	double temp = 1;
	int n = 1;
	int m = 3;
	
	while (temp > 1e-15)    //当每一项大于指定的精度时，才计算
	{
		temp = temp * n / m;
		pi += temp;
		n++;
		m += 2;
	}
	
	return 2 * pi;
}


int main()
{
	cout << Calculate_Pi() << endl;
	system("pause");
	return 0;
}

如上例所示，虽然能够根据公式很快的写出计算 pi 的小程序，但是由于使用单变量来保存结果，限于计算机硬件对变量的表示范围有限，因此，最多只能计算出pi值小数点后十多位。但需要得到一个更大位数的pi值时，就得考虑其他的算法。

我们采用这个公式计算pi： pi/2 = 1+1/3+1/3 * 2/5 + 1/3 * 2/5 * 3/7 + 1/3 * 2/5 * 3/7 *4/9+…

在计算上述公式的个分式值时，由于1/3这类的分数是无限循环小数，而使用单变量时，由于变量能表示的范围有限，因此，多余的部分将被舍去。为了提高精度，这时可以定义数组来逐位保存无限循环小数，例如：定义有20个元素的数组temp,每个元素保存一位数，则2/3的结果展示如下效果：

注：2/3 = 0.66666666…

元素下标	0	1	2	3	4	5	6	7	8	9	10	…
2/3结果	0	6	6	6	6	6	6	6	6	6	6	…

数组第0位存储分数的整数部分，数组第1位之后依次存储的是分数的小数部分

由于 pi= 2 + 2/3 + 2/3 * 2/5 + 2/3 * 2/5 * 3/7 + 2/3 * 2/5 * 3/7 * 4/9 +… 所以需要设置一个 temp 数组来保存其中的每一项的数值，计算的时候只需要将每一项累加到 pi 数组中即可。

按照数组方式存储小数的话，则 2/3 * 2/5 可以按以下方式进行计算：

• 1.由于此时temp中已经保存了 2/3，所以只需要将 temp 中的每一位都乘以 2后的结果保存在 result 中。进行乘法运算是从低位到高位的，结果如下：

  元素下标	0	1	2	3	4	5	6	7	8	9	10	…
  2/3结果	0	6	6	6	6	6	6	6	6	6	6	…
  result结果	0	12	12	12	12	12	12	12	12	12	12	…

• 2.由于result中有的值大于10，所以需要进行进位操作，进位后 的数值便是2/3 *2的结果，将其保存在temp中，其结果如下：

  元素下标	0	1	2	3	4	5	6	7	8	9	10	…
  2/3结果	0	6	6	6	6	6	6	6	6	6	6	…
  乘以2后result结果	0	12	12	12	12	12	12	12	12	12	12	…
  进位后temp结果	1	3	3	3	3	3	3	3	3	3	2	…

• 3.然后temp数组中每个元素除以5，并将结果保存在temp数组中。进行除法运算的时候，是从高位到低位进行运算的，，也就是从数组的低位（序号0）开始。首先用temp[0]的值除以5，即1/5，列出其除法竖式如下：

   　　 １
    5 [ 6
        5
        1
  

  得到的商为0，则将商保存在数组temp[0]中，接着将余数1乘以10累加到下一个元素temp[1]中，使temp[1]的值变为 3+1 * 10=13.

  用temp[1]的值13除以5，得到商为2，将商保存到temp[1]中，余数为3，将其乘以10累加到下一个元素 temp[2]中，使temp[2]的值变为 **3+3 * 10=33. **

  用temp[2]的值33除以5，得到商为6，将商保存到temp[2]中，余数为3，将其乘以10累加到下一个元素 temp[3]中，使temp[3]的值变为 3+3 * 10=33…,这样不断地重复，最后使temp数组变为如下形式：

  元素下标	0	1	2	3	4	5	6	7	8	9	10	…
  进位后temp结果	1	3	3	3	3	3	3	3	3	3	2	…
  除以5后temp结果	0	2	6	6	6	6	6	6	6	6	6	…

• 4.通过上面的操作，完成了一个数列，即一项的计算，并按位保存到数组temp中，再将temp数组中的值累加到pi数组中。

不断重复上述过程，即可得到指定位数的pi值。

提示：由于数列可以不断重复，什么时候终止循环哪？当数组temp中的值全为0,则表示已经没有余数需要处理；如果数组中的元素一直不为0,就需要设置另外的条件来终止循环，如规定循环处理的次数。

计算任意位数Pi值的程序代码：

#include<iostream>
using namespace std;


//计算pi的任意精度
void calculate_pi()
{
	int len;  //小数位数
	int count = 0;  //循环次数
	int flag = 1;  //循环结束的标志
	int numberaor = 1;  //分子
	int denominator = 3;  //分母
	char *pi;   //指向存放pi值的数组(采用char型节省内存，因为char，每个元素占1个字节，int占4个字节)
	char *temp;  //指向存放每一项的值的数组
	int result;  //存放未进位前的数据
	int carry;  //记录进位的位数

	cout << "请输入pi的精度(保留几位小数)：";
	cin >> len;
	len++;  //长度+1，用来保存整数部分的值


	if (!(pi = new char[len]))   //为存放pi值的数组分配内存
	{
		cout << "内存分配失败！" << endl;
		exit(0);
	}

	if (!(temp = new char[len]))		//为存放每一项值(临时值)的数组分配内存
	{
		cout << "内存分配失败！" << endl;
		exit(0);
	}

	//初始化数组
	for (int i = 0; i < len; i++)
	{
		pi[i] = 0;
		temp[i] = 0;
	}
	pi[0] = 2;   //给pi的第一项赋初值
	temp[0] = 2;

    //从 pi 的第二项开始循环计算
	while (flag && (++count < 2147483647))   //count是int型，而int的最大值为 2147483647
	{
		carry = 0;

		//从低位到高位依次相乘
		for (int i = len - 1; i >= 0; i--)    
		{
			result = temp[i] * numberaor + carry;   //每一位乘以分子后再加上进位
			temp[i] = result % 10;    //temp中只保留个位数
			carry = result / 10;     //记录进位数
		}

		carry = 0;   //将进位数清零

		//从高位到低位依次进行除法运算
		for (int i = 0; i < len; i++)
		{
			result = temp[i] + carry * 10;    //当前位 加上 前一位的余数*10
			temp[i] = result / denominator;		//temp中只保留当前位的整数部分
			carry = result % denominator;    //当前位的余数，累加到下一位进行运算
		}

		flag = 0;   //清除标志

		//从低位到高位依次将temp数组中的数据累加到pi数组中
		for (int i = len - 1; i >= 0; i--)
		{
			result = pi[i] + temp[i];  //存放两数组之和
			pi[i] = result % 10;    //保留个位数
            
            //将低位的进位累加到高位（下一次循环的时候result中记录的就是进位后的数据）
			pi[i - 1] += (result / 10);   
			flag = flag | temp[i];    //若temp中的值全为0，则退出循环
		}

		numberaor++;   //累加分子
		denominator += 2;  //累加分母
	}
	cout << endl;

	//输出数组
	cout << "计算了" << count << "次" << endl;
	cout << "\t-----第1-" << len - 1 << "位小数-----" << endl;
	cout << "pi = " << endl;

	cout << (int)pi[0] << ".";   //将char型强转为int型
	for (int i = 1; i < len; i++)
	{
		if ((i>1)&&(i-1) % 10 == 0)
		{
			cout << " ";
		}
		if ((i>1) && (i-1) % 50 == 0)
		{
			cout << endl;
		}
		cout << (int)pi[i];
	}
	cout << endl;
}


int main()
{
	calculate_pi();
	system("pause");
	return 0;
}

程序运行结果如下：

补充：对 flag = flag | temp[i]; 的理解

​ A|B，在C语言，意思是取A与B的各对应的二进位补码形式，只要对应的两个二进位有一个为1时，其结果位就为1。

按位或运算符“|”是双目运算符，其功能是参与运算的两数各对应的二进位相或。只要对应的两个二进位有一个为1时，结果位数就为1。参与运算的两个数均以补码出现。

例如：13|17可写成二进制如下: 00010011|00010111，结果为00010111，十进制为17。即 13|17=17。