《π值算法分析.doc》由会员分享，可在线阅读，更多相关《π值算法分析.doc（9页珍藏版）》请在金锄头文库上搜索。
1、关于“”值计算的算法分析研究电子科技大学 电子工程学院 Lawrence Xu一、简介 圆周率，一般以来表示，是一个在数学及物理学中普遍存在的数学常数。它定义为圆形之周长与直径之比。它也等于圆形之面积与半径平方之比。是精确计算圆周长、圆面积、球体积等几何形状的关键值。 在分析学里，可以严格地定义为满足sin x = 0的最小正实数x。在很多数学领域里都有很大的作用：Leibniz定理：概率论：设我们有一个以平行且等距木纹铺成地板，随意抛一支长度比木纹之间距离小的针，求针和其中一条木纹相交的概率。这就是布丰投针问题。1777 年布丰自己解决了这个问题这个概率值是 1/。定义圆周率不一定要用到几何
2、概念，比如，我们可以定义为满足sin x = 0的最小正实数x。这里的正弦函数定义为幂级数从而，从古到今，计算的值成为了一个流行于世界数学界的问题。现在利用计算机可以将值计算到小数点后数亿位。学完算法分析与设计后，觉得可以用几种不同的算法来计算的值。二、 具体算法及C语言实现1. Leibniz定理：C代码为：Define N 10000000#includeint main() int j; double i,pai=1; for(i=3,j=-1;iN;i=i+2,j*=-1) pai+=1/i*j; printf(=%lf,4*pai); return 0;运行结果：3.141592，发
3、现N=10000000时才能与真实值温和到7位，N=1000000，则结果为3.141591。2. 级数算法C代码:(这是我在网上看到的代码，算到了800位，觉得很神奇后面有我自己对这个算法的一点分析)#include long a=10000,b,c=28000,d,e,f28010,g; void main() for(;b-c;) fb+=a/5; for(;d=0,g=c*2;c-=14,printf(%.4d,e+d/a),e=d%a) for(b=c;d+=fb*a,fb=d%-g,d/=g-,-b;d*=b); 结果为：因为是网上看到的算法，看了半天才懂，觉得很妙，下面给出几点分
4、析：一、算法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)+(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)+
5、(1/3)*(2/5)+1/3+1=(k/(2k+1)*.*(2/5)*(1/3)+.+(3/7)*(2/5)*(1/3)+(2/5)*(1/3)+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位小数，就只
6、能用大数除法的办法了：分为n趟执行，这一趟把公式中每一次除法的余数保存下来，把商累计后输出；下一趟把保存的余数提高精度再做除法，把余数保存下来，把商累计后输出，以此类推。根据数学运算，当k=2800时，可以精确到小数点后800位（实际上是精确到小数点后844位），那么我们就设定一个2800的数组，全部初始化为1（也就是设定余数为1，就是公式中加的1），然后在循环中不断的做除法、乘法、加余数，过程中还要保存余数，和手工除法一样。提高精度的办法，比如f2800，初始值为1，除以5601、乘以2800，把商的整数部分加1放到下一项的运算中，余数保存下来，在下一趟乘以10，再除以5601、乘以2800
7、，得到的商的整数部分就是上一趟运算结果的后一位数字。我们如果要每次输出4位数字，那么就要乘以10000，得到的商的整数部分不会超过4位数，就是上一趟运算结果的后四位数字。注意到上述公式的结果是/2，那么我们就把数组都初始化为2，由于要一次输出4位，所以扩大10000倍。二、错误1、数组初始化for(;b-c;)fb+=a/5;这一行代码把数组f0至f2799设置为2000，f2800没有初始化，还是0，那么在实际运算中这一项是没有起到作用的，由于这一项的结果实在太小了。但是从计算逻辑上，却有很大的混淆作用，实际上f0是从来没有用到的，所以初始化应该是把f1至f2800初始化为2000，这样精度
8、在小数点后848位才出现变化，由于结果是精确到第844位，所以这点精度实际上是没有意义的，但是算法却正确了。也就是for(;b-c;)f+b=a/5;三、其他1、输出结果（printf）代码中的d就是每趟运算中商的累计，就是要输出的结果，由公式及我们的算法处理可知，d不会超过8位，而且其左4位与前次余数e的和也不会超过8位，所以我们用printf(%.4d,e+d/10000)把左4位输出，把d的右4位保存在e中e=d%10000。printf(%.4d,)输出4位整数，且显示最左面的0，就是那个.的作用了。2、c的作用在第二个for循环中用c-=14来控制循环次数，实际上的影响在于第三个fo
9、r循环的初始化部分b=c，上面分析过这样的处理（错误）对精度几乎没有影响。实际上c-=14没有特殊的含义，只是因为2800/(800/4)=14，我们完全可以用计数器来替代，就像我们的代码中一样。3、g的作用g就是公式中的2k+1，在我们的程序中完全可以用2*b+1来替代。仅仅三行的代码完成了这么复杂的计算，让我佩服的同时也感觉到了算法的精妙。希望以后还能继续学习算法的相关知识写出更多高质量的代码。3、 割圆术这是我国古代数学家祖冲之的算法，他穷尽一生把圆周率计算到了3.1415926和3.1416927之间，直到15世纪才有外国科学家追上。C代码：# include# includeint main() long double a,b,r,s,n; long int c; scanf(%ld,&c); s=30000*sqrt(3.0); n=0; r=200.0; b=sqrt(30000.0); a=r-sqrt(r*r-b*b); do s=s+a*b*3.0*pow(2,n); n=n+1; b=0.5*sqrt(a*a+b*b); a=r-sqrt(r*r-b*b); while(n=c); printf(%33.20llf,25*s); scanf(%ld,&c); return 0;结果：输入1000时，结果为但输入值超过1023时，结果溢出为IND了。
