Cong Wang
25th November,2005


Institute of Post and Telecommunication, Xi'an, PRC China
Network Engineering Dep.


引言
  网上流传着一个怪异的求pi程序，虽然只有三行却能求出pi值连小数点前共800位。这个程序如下：

/*某年Obfuscated C Contest佳作选录:*/
#include < stdio.h>
long 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);
}

/* (本程式可算出pi值连小数点前共800位)
(本程式录自sci.math FAQ,原作者未详)*/

咋一看，这程序还挺吓人的。别慌，下面就告诉你它是如何做到的，并且告诉你写怪异C程序的一些技巧。^_^

展开化简
  我们知道，在C语言中，for循环和while循环可以互相代替。

  for(statement1;statement2;statement3){
    statements;
  }

上面的for语句可以用下面的while语句来代替：

  statement1;
  while(statement2){
    statements;
    statement3;
  }

而且要写怪异的C程序，逗号运算符无疑是一个好的助手，它的作用是：
从左到右依次计算各个表达式的值，并且返回最右边表达式的值。
把它嵌入for循环中是写怪异代码的常用技巧之一。所以，上面的程序可以展开为：
#include < stdio.h> /*1*/
/*2*/
long a=10000, b, c=2800, d, e, f[2801], g; /*3*/
main(){ /*4*/
  while(b-c!=0){ /*5*/
    f[b]=a/5; /*6*/
    b++; /*7*/
    } /*8*/
  d=0; /*9*/
  g=c*2; /*10*/
  while(g!=0){ /*11*/
    b=c; /*12*/
    d+=f[b]*a; /*13*/
    f[b]=d%--g; /*14*/
    d=d/g--; /*15*/
    --b; /*16*/
    while(b!=0){ /*17*/
        d=d*b+f[b]*a; /*18*/
        f[b]=d%--g; /*19*/
        d=d/g--; /*20*/
        --b; /*21*/
        } /*22*/
    c-=14; /*23*/
    printf("%.4d",e+d/a); /*24*/
    e=d%a; /*25*/
    d=0; /*26*/
    g=c*2; /*27*/
    } /*28*/
  } /*29*/

现在是不是好看一点了？

进一步化简
  你应该能注意到a的值始终是10000，所以我们可以把a都换成10000。再就是，仔细观察g，在外层循环中，每次循环用它做除法或取余时，它总是等于2*c-1，而b总是初始化为c。在内层循环中，b每次减少1，g每次减少2。你这时会想到了吧？用2*b-1代替g！代进去试试，没错！另外，我们还能做一点化简，第26行的d=0是多余的，我们把它合并到第13行中去，第13行可改写为： d=f[b]*a;　。所以程序可以改为：
#include < stdio.h>

long b, c=2800, d, e, f[2801];
main(){
  while(b-c!=0){
    f[b]=2000;
    b++;
    }

  while(c!=0){
    b=c;
    d=f[b]*10000;
    f[b]=d%(b*2-1);
    d=d/(b*2-1);
    --b;
    while(b!=0){
        d=d*b+f[b]*10000;
        f[b]=d%(b*2-1);
        d=d/(b*2-1);
        --b;
        }
    c-=14;
    printf("%.4d",e+d/10000);
    e=d%10000;
    }
  }

少了两个变量了!

深入分析
  好了，马上进入实质性的分析了。一定的数学知识是非常有必要的。首先,必须知道下面的公式可以用来求pi:
pi/2=1+1!/3!!+2!/5!!+3!/7!!+...+k!/(2*k+1)!!+...
只要项数足够多，pi就有足够的精度。至于为什么，我们留给数学家们来解决。
  写过高精度除法程序的人都知道如何用整数数组来进行除法用法，而避免小数。其实很简单，回想一下你是如何徒手做除法的。用除数除以被除数，把得数放入结果中，余数乘以10后继续做下一步除法，直到余数是零或达到了要求的位数。
  原程序使用的数学知识就那么多,之所以复杂难懂是因为它把算法非常巧妙地放到循环中去了。我们开始具体来分析程序。首先，我们从数学公式开始下手。我们求的是pi，而公式给出的是pi/2。所以，我们把公式两边同时乘以2得:

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

接着，我们把它改写成另一种形式,并展开：

  pi=2*1+2*1!/3!!+2*2!/5!!+2*3!/7!!+...+2*n!/(2*n+1)!!

  =2*(n-1)/(2*n-1)*(n-2)/(2*n-3)*(n-3)/(2*n-5)*...*3/7*2/5*1/3
            +2*(n-2)/(2*n-3)*(n-3)/(2*n-5)*...*3/7*2/5*1/3
                      +2*(n-3)/(2*n-5)*...*3/7*2/5*1/3
                                  +2*3/7*2/5*1/3
                                    +2*2/5*1/3
                                      +2*1/3
                                        +2*1
对着公式看看程序，可以看出，b对应公式中的n，2*b-1对应2*n-1。b是从2800开始的，也就是说n=2800。（至于为什么n=2800时,能保证pi的前800位准确不在此讨论范围。）看程序中的相应部分：
d=d*b+f[b]*10000;
f[b]=d%(b*2-1);
d=d/(b*2-1);

d用来存放除法结果的整数部分，它是累加的，所以最后的d将是我们要的整数部分。而f[b]用来存放计算到b为止的余数部分。
  到这里你可能还不明白。一是，为什么数组有2801个元素？很简单，因为作者想利用f[1]~f[2800]，而C语言的数组下标又是从0开始的，f[0]是用不到的。二是，为什么要把数组元素除了f[2800]都初始化为2000？10000有什么作用？这倒很有意思。因为从printf("%.4d",e+d/10000); 看出d/10000是取d的第4位以前的数字，而e=d%10000;　，e是d的后4位数字。而且，e和d差着一次循环。所以打印的结果恰好就是我们想要的pi的相应的某4位！开始时之所以把数组元素初始化为2000，是因为把pi放大1000倍才能保证整数部分有4位，而那个2就是我们公式中两边乘的2！所以是2000！注意，余数也要相应乘以10000而不是10！f[2800]之所以要为0是因为第一次乘的是n-1也就是2799而不是2800!每计算出4位，c都要相应减去 14，也就保证了一共能够打印出4*2800/14=800位。但是，这竟然不会影响结果的准确度！本人数学功底不高，无法给出确切答案。（要是哪位达人知道，请发email到xiyou.wangcong@gmail.com告诉我哦。）

  偶然在网上见到一个根据上面的程序改写的“准确”（这个准确是指没有漏掉f[]数组中的的任何一个元素。）打印2800位的程序，如下：
long b,c=2800,d,e,f[2801],g;
int main(int argc,char* argv[])
{
  for(b=0;b       f[b] = 2;
  e=0;
  while(c > 0)
  {
    d=0;
    for(b=c;b>0;b--)
    {
        d*=b;
        d+=f[b]*10;
        f[b]=d%(b*2-1);
        d/=(b*2-1);
    }
    c-=1;
    printf("%d",(e+d/10)%10);
    e=d%10;
  }
  return 0;
}

不妨试试把上面的程序压缩成3行。
结论
  以Knuth图灵演讲中的一句话结束全文：
We have seen that computer programming is an art, because it applies accumulated knowledge to the world, because it requires skill and ingenuity, and especially because it produces objects of beauty. A programmer who subconsciously views himself as an artist will enjoy what he does and will do it better.
与大家共勉！^_^

评论