π值算法分析

《π值算法分析》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、关于“π”值计算的算法分析研究电子科技大学电子工程学院LawrenceXu一、简介圆周率，一般以π来表示，是一个在数学及物理学中普遍存在的数学常数。它定义为圆形之周长与直径之比。它也等于圆形之面积与半径平方之比。是精确计算圆周长、圆面积、球体积等几何形状的关键值。在分析学里，π可以严格地定义为满足sinx=0的最小正实数x。π在很多数学领域里都有很大的作用：Leibniz定理：概率论：设我们有一个以平行且等距木纹铺成地板，随意抛一支长度比木纹之间距离小的针，求针和其中一条木纹相交的概率。这就是布丰投针问题。1777年布丰自己解决了这个问题——这个

2、概率值是1/π。定义圆周率不一定要用到几何概念，比如，我们可以定义π为满足sinx=0的最小正实数x。这里的正弦函数定义为幂级数从而，从古到今，计算π的值成为了一个流行于世界数学界的问题。现在利用计算机可以将π值计算到小数点后数亿位。学完算法分析与设计后，觉得可以用几种不同的算法来计算的值。二、具体算法及C语言实现1.Leibniz定理：C代码为：DefineN10000000#includeintmain(){intj;doublei,pai=1;for(i=3,j=-1;i

3、;}printf("π=%lf",4*pai);return0;}运行结果：3.141592，发现N=10000000时才能与真实值温和到7位，N=1000000，则结果为3.141591。2.级数算法C代码:(这是我在网上看到的代码，算到了800位，觉得很神奇后面有我自己对这个算法的一点分析)#includelonga=10000,b,c=28000,d,e,f[28010],g;voidmain(){for(;b-c;)f[b++]=a/5;for(;d=0,g=c*2;c-=14,printf("%.4d",e+d/a),

4、e=d%a)for(b=c;d+=f[b]*a,f[b]=d%--g,d/=g--,--b;d*=b);}结果为：因为是网上看到的算法，看了半天才懂，觉得很妙，下面给出几点分析：一、算法1、这个算法用到的π的计算公式（级数中的一种0π/2=1+1!/3!!+2!/5!!+3!/7!!+...+k!/(2*k+1)!!+...2、公式的程序实现（数组存储余数）把上面的公式做一下展开和调整π/2 = 1 + 1!/3!! + 2!/5!! + 3!/7!! + ... + k!/(2*k+1)!!= 1 + 1/3 + (1*2)/(3*5) + (

5、1*2*3)/(3*5*7) + ... + (1*2*...*k)/(3*5*...*(2k+1))= 1 + 1/3 + (1/3)*(2/5) + (1/3)*(2/5)*(3/7) + ... + (1/3)*(2/5)*...*(k/(2k+1))= (1/3)*(2/5)*...*(k/(2k+1)) + ... + (1/3)*(2/5)*(3/7) + (1/3)*(2/5) + 1/3 + 1= (k/(2k+1))*...*(2/5)*(1/3) + ... + (3/7)*(2/5)*(1/3) + (2/5)*(1/3) 

6、+ 1/3 + 1= (((((k/(2k+1)+1)*((k-1)/(2(k-1)+1)+1)*...)*3/7+1)*2/5+1)*1/3+1)/1= (((((1/(2k+1)*k+1)/(2(k-1)+1)*(k-1)+1)/...)/7*3+1)/5*2+1)/3*1+1)/1我们要做的就是做除法、做乘法、加1，做除法、做乘法、加1，...，这样直到做除法除以1。那么我们就可以在一个循环中完成它，用一个计数器i，1除以2i+1、乘以i、加1，循环。但是我们要输出800位小数，就只能用大数除法的办法了：分为n趟执行，这一趟把公式中每一次除

7、法的余数保存下来，把商累计后输出；下一趟把保存的余数提高精度再做除法，把余数保存下来，把商累计后输出，以此类推。根据数学运算，当k=2800时，可以精确到小数点后800位（实际上是精确到小数点后844位），那么我们就设定一个2800的数组，全部初始化为1（也就是设定余数为1，就是公式中加的1），然后在循环中不断的做除法、乘法、加余数，过程中还要保存余数，和手工除法一样。提高精度的办法，比如f[2800]，初始值为1，除以5601、乘以2800，把商的整数部分加1放到下一项的运算中，余数保存下来，在下一趟乘以10，再除以5601、乘以2800，得到

8、的商的整数部分就是上一趟运算结果的后一位数字。我们如果要每次输出4位数字，那么就要乘以10000，得到的商的整数部分不会超过4位数，就是