20CN网络安全小组论坛 - 编程破解

论坛: 编程破解标题: 简单算π程序

作者: bug_me [bug_me]

论坛用户

程序如下：

#include<stdio.h>
long a=10000,b=0,c=2800,d,e,f[2801],g;
void main()
{
for(;b!=c;)
{
f[b]=a/5;
b++;
}
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);
}

谁能解释一下这个程序的算法是……

地主发表时间: 04-07-08 13:52

回复: bug_me [bug_me]

论坛用户

PI=16arctg(1/5)-4arctg(1/239)
在展开成两个级数之和，然后整理得到：
PI=16x(1/5-1/(5^3/3)+1/(5^5/5)-1/(5^7/7)+...)-4x(1/239-1/(239^3/3)+1/(239^5/5)-1/(239^7/7)+...)
=4x(4x5/25-239/57121)/1-4x(4x5/25^2-239/57121^2)/3+4x(4x5/25^3-239/57121^3)/5-...
我对以上公式和推导一看就头疼，但根据它编出的程序却可以在4分钟内算出圆周率的小数点下8万位!（在P5/200上）想当年祖冲之算了一生才算到3.14159265，十九世纪英国人香克思用了一生才算到小数点下707位。
本程序的难点就是如何达到小数点下这么多位的精度，这个办法就是：在计算机中一个 WORD 可以表示0到65535，我们可以在内存定义一个字来表示五位数，如果要算到小数点下10000位，则定义2000个字来表示它，如计算239/57121时，可以用23900000/57121，得到小于五位的结果存到第一个字中，然后用余数乘以100000再除57121，得到小于五位的结果存到第二个字中，依此类推。为了计算时不至于溢出，本程序动用一个双字来表示五位数，再用一个段64K来表示一个高精度数，共可以表示（65536/4）*5 共有小数点下 81920 位。一共用到三个段，第一个段存储（4*4*5/25^n），第二个段存储（4*239/57121^n），第三个段存储最后的结果即 PI。

[此贴被石狮(bug_me) 在 07月09日12时06分编辑过]

B1层发表时间: 04-07-09 12:04

回复: ypy [ypy]

见习版主

#include <iostream.h>
#include <string.h>

int main()
{
const int SIZE=1010, CNT=1000; //定义数组大小，显示位数

char x[SIZE], z[SIZE];
int a=1, b=3, c, d, Run=1, Cnt=0;

memset(x,0,SIZE);
memset(z,0,SIZE);

x[1] = 2;
z[1] = 2;

while(Run && (++Cnt<200000000))
{
d = 0;
for(int i = SIZE-1; i>0; i--)
{
c = z[i]*a + d;
z[i] = c % 10;
d = c / 10;
}

d = 0;
for(int i=0; i<SIZE; i++)
{
c = z[i]+d*10;
z[i] = c / b;
d = c % b;
}

Run = 0;
for(int i=SIZE-1; i>0; i--)
{
c = x[i] + z[i];
x[i] = c%10;
x[i-1] += c/10;
Run |= z[i];
}
a++;
b+=2;
}

cout<<"pi = "<<(int)x[0]<<(int)x[1]<<"."<<endl;
for(int i=0; i<CNT; i++)
{
cout<<(int)x[i+2];
if(i%10 == 9) cout<<" ";
if(i>0 && i%50 == 49) cout<<" :"<<i+1<<endl;
}
}

B2层发表时间: 04-07-09 13:06

论坛: 编程破解