编程计算Pi(π)的N种方法 |
您所在的位置:网站首页 › pi的推特 › 编程计算Pi(π)的N种方法 |
•矩形法则的数值积分方法估算Pi的值-原理
tan (pi/4) = 1 pi/4 = arctan 1 pi = 4arctan 1 积分其导数并固定在一点上的值给出反三角函数作为定积分的表达式: 当 x 等于 1 时,在有极限的域上的积分是瑕积分,但仍是良好定义的。
一个看起来很牛的计算Pi的程序: int a=10000,b,c=2800,d,e,f[2801],g; main() { for(;b-c;) f[b++]=a/5; for(;d=0,g=c*2;c -=14,printf("%.4d",e+d/a),e=d%a) for(b=c; d+=f[b]*a,f[b]=d%--g,d/=g--,--b; d*=b); } 这还不是最牛的,源码所在的这个网站里牛程序多的是: http://numbers.computation.free.fr/Constants/TinyPrograms/tinycodes.html
下面是用C写的Pi计算程序: The following tiny C code computes digits of p. Boris Gourevitch kindly sent me the information that this program is from Dik T. Winter (cwi institute, Holland). int a=10000,b,c=8400,d,e,f[8401],g;main(){ for(;b-c;)f[b++]=a/5; for(;d=0,g=c*2;c-=14,printf("%.4d",e+d/a),e=d%a) for(b=c;d+=f[b]*a,f[b]=d%--g,d/=g--,--b;d*=b);}The program has 158 characters long. Finding the algorithm used is not so easy. Sebastian Wedeniws worked hard to find a shorter program (142 characters) : main(){int a=1e4,c=3e3,b=c,d=0,e=0,f[3000],g=1,h=0; for(;b;!--b?printf("%04d",e+d/a),e=d%a,h=b=c-=15:f[b]= (d=d/g*b+a*(h?f[b]:2e3))%(g=b*2-1));}Jean-Charles Meyrignac pointed me out a tiny code from the page http://www.isr.umd.edu/~jasonp/pigjerr. The program is by Gjerrit Meinsma, of 141 characters long, and computes 1000 digits of pi. long k=4e3,p,a[337],q,t=1e3; main(j){for(;a[j=q=0]+=2,--k;) for(p=1+2*k;j2?:printf("%.3d",a[j-2]%t+q/p/t);}
二、矩阵拟合法计算Pi - 可用OpenMP并行 Sequetial Version: #include #include void main () { time_t start, finish; static long num_steps = 1000000000; double step; int i; double x, pi, sum = 0.0; step = 1.0/(double) num_steps; start = clock(); for (i=0;i < num_steps; i++) { x = (i+0.5)*step; sum = sum + 4.0/(1.0+x*x); } pi = step * sum; finish = clock(); printf( "Pi = %16.15f (%d steps), %ld ms\n ", pi, num_steps, finish-start ); return; } -------------------------------------------------------------------------------------------- Parallel Version: #include #include #include void main () { time_t start, finish; static long num_steps = 1000000000; double step; int i; double x, pi, sum = 0.0; step = 1.0/(double) num_steps; start = clock(); #pragma omp parallel for reduction(+:sum) private(x) /*只加了这一句,其他不变*/ for (i=0;i < num_steps; i++) { x = (i+0.5)*step; sum = sum + 4.0/(1.0+x*x); } pi = step * sum; finish = clock(); printf( "Pi = %16.15f (%d steps), %ld ms\n ", pi, num_steps, finish-start ); return; } result: Sequential version: Pi = 3.141592653589792 (1000000000 steps), 13900000 ms Parallel version for 8 threads: Pi = 3.141592653589794 (1000000000 steps), 1820000 ms 从结果可以看到8线程的speedup=7.64,接近线性。因为这个程序本身具有良好的并发性,循环间几乎没有数据依赖,除了sum,但是用reduction(+:sum)把对于sum的相关也消除了。而且实验平台本身就有8个处理器核。
三、概率方法 Name: 蒙特卡罗法求解 pi Description: 边长为r的正方形,内接1/4圆周,半径也为r. 正方形面积s1 = r*r 1/4圆周面积s2 = pi*r*r / 4 假设在正方形中随机选择许多点,那么这些点中有一部分也落在1/4圆周内。 如果所选择的点是均匀分布的,那么我们可以期望落于1/4圆周内的点的概率是: f = s2 / s1 = pi / 4 因此,通过测定f , 就可以计算出 pi = 4*f . 程序如下: #include #define for if(0);else for static long int seed = 1L; static long int const a =16807L, m = 2147483647L, q = 127773L, r = 2836L; double Rondom() { seed = a*(seed%q) - r*(seed/q); if( seed < 0 ) seed += m; return (double) seed / (double) m; } double Pi(unsigned int trials) { unsigned int hits = 0; for(unsigned int i=0;i const ARRSIZE=1010, DISPCNT=1000; //定义数组大小,显示位数 char x[ARRSIZE], z[ARRSIZE]; //x[0] x[1] . x[2] x[3] x[4] .... x[ARRSIZE-1] int a=1, b=3, c, d, Run=1, Cnt=0; memset(x,0,ARRSIZE); memset(z,0,ARRSIZE); x[1] = 2; z[1] = 2; while(Run && (++Cnt c = z[i]*a + d; z[i] = c % 10; d = c / 10; } //z/=b; d = 0; for(int i=0; i c = x[i] + z[i]; x[i] = c%10; x[i-1] += c/10; Run |= z[i]; } a++; b+=2; } Memo1->Text = AnsiString().sprintf("计算了 %d 次\r\n",Cnt); Memo1->Text = Memo1->Text + AnsiString().sprintf("Pi=%d%d.\r\n", x[0],x[1]); for(int i=0; i |
CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |