圆周率π以及圆周率π的计算.doc

圆周率π以及圆周率π的计算为什么要算PI?计算机最原始的用途就是进行人类无法完成的复杂运算,算PI就是这样的运算之一。虽然算PI本身没有多大的实际意义,但是对于计算机爱好者来说作为一种编程的挑战,还是很有意思的。算PI看似简单,其实它还牵涉到一些有用的数学知识。第一类算法:arctan的级数展开PI/4=4arctan(1/5)-arctan(1/239)(1)arctan(x)=x-x3/3+x5/5-x7/7+....(2)很容易想到,要得到超高精度的PI值,实数在计算机中必须以数组的形式进行存取,数组的大小跟所需的有效位数成正比。在这个算法中,PI的有效位数n随(2)的求和项数线性增加。而为计算(2)中的每一项,需要进行超高精度实数除以小整数(52,2392,2k+1)的循环,循环所需次数也跟n成正比。所以,这个算法总的时间复杂度为O(n2)。这个算法的优点是简单,而且只需要进行整数运算。下面给出我写的算PI程序。在程序中,我采用了一些提高速度的措施:超高精度实数以数组的形式进行存取,数组元素的类型为64位整数(longlong),每个元素储存12个十进制位;对xk(x=1/5,1/239)的头部和尾部的0的数量进行估计,只对非0的部分进行计算。   回复人:swordd 回复时间:2005-12-314:32:00/*++源程序*/#plex>#;template<classT>plex<T>*array,intsize_log_2,boolpositive){    complex<T>swap;    for(inti=0;i<(1<<size_log_2);i++)    {        intreverse=0;        for(intj=0;j<size_log_2;j++)reverse^=(i&1<<j)>>j<<size_log_2-j-1;        if(reverse>i)        {            swap=array[reverse];            array[reverse]=array[i];            array[i]=swap;        }    }    complex<T>ca,cb;    for(ints=0;s<size_log_2;s++)    {        complex<T>w=plex<T>(0,(positive?-1:1)*PI/(1<<s)));        for(inta=0;a<(1<<size_log_2-s-1);a++)        {            complex<T>m=1;            for(intb=0;b<(1<<s);b++)            {                ca=array[a*(1<<s+1)+b];                cb=array[((a<<1)+1)*(1<<s)+b]*m;                array[a*(1<<s+1)+b]=ca+cb;                array[((a<<1)+1)*(1<<s)+b]=ca-cb;                m*=w;            }        }    }    if(!positive)for(intc=0;c<(1<<size_log_2);c++)array[c]/=(1<<size_log_2);}template<classT>plex<T>*array,intsize,boolpositive,intstep=1){    intN1,N2,m1,m2,k1,k2;    if(step==1)    {        intinter=size;        while(true)        {            if(inter%2==0)inter=inter/2;            elseif(inter%3==0)inter=inter/3;            elseif(inter%5==0)inter=inter/5;            elseif(inter%7==0)inter=inter/7;            elsebreak;        }        if(inter!=1)return-1;    }    if(size%2==0)N1=2;    elseif(size%3==0)N1=3;    elseif(size%