代码

如果在Google Code Search里搜索fuck……

/ 9 条评论

    Ben orenstein尝试在Goolge Code Search里输入脏话，在众多的开源软件中找到了一些非常牛B的代码：

gdb-6.4.50.20060515:
/* OK, now set up the filehdr...  */

/*   We will NOT put a fucking timestamp in the header here. Every time you
     put it back, I will come in and take it out again.  I’m sorry.  This
     field does not belong here.  We fill it with a 0 so it compares the
     same but is not a reasonable time. — gnu@cygnus.com  */

Siesta-0.66:
    # This job would be great if it wasn’t for the fucking customers.

CGI-FormBuilder-3.0202:
        # Get field from radio buttons or checkboxes
        # Must cycle through all again to see which is checked. yeesh.
        # However, this only works if there are MULTIPLE checkboxes!
        # The fucking JS DOM *changes* based on one or multiple boxes!?!?!
        # Damn damn damn I hate the JavaScript DOM so damn much!!!!!!

DJabberd-0.81:
    # Trillian, again, is fucking stupid and crashes on just
    # about anything its homemade XML parser doesn’t like.

gift-0.11.5:
void list_lock_insert_sorted (ListLock *lock, CompareFunc func, void *data)
{
    if (lock->locked)
    {
        /* TODO: this is obviously not right ... this whole fucking module
         * sucks anyway */
        list_lock_prepend (lock, data);
        return;
    }

    lock->list = list_insert_sorted (lock->list, func, data);
}

bh-asia-03-grugq:
    /* if we get here, there are massive fucking problems, for a start
     * our stack is fucked up, and we can’t return(). Just crash out. */

trunk:
    /* FIXME: please god, when will the hurting stop? Thus function is so
              fucking broken it’s not even funny. */

SQL-Abstract-1.20:
    # Note to self: I have no idea what this does anymore
    # It looks like a cool fucking segment of code though!
    # I just wish I remembered writing it… :-

mendax_linux:
for(i = 0 ; i < pktcount; i++) {
    from.sin_port = htons(ntohs(from.sin_port) + 1);
    pktlen = gen_tcp_pak(&pak, &from, dst, ip_id++,
                     seq_num, 0L, 0, flags);
    seq_num += 64000;

    /* don't fire dem packets too fucking fast */
    usleep(1000);

    send_pak((char *) &pak, pktlen, ether);
    putchar('.');
}

SugarOS-for-Microsoft-Full-4.5.0h:
    /*   Outlook can’t fucking follow RFC if someone PAID them to do it…
        oh wait, someone paid them NOT to do it. */

AfterStep-2.2.5:
    /* No we fucking don’t! DB entries should be stored in the same order
       as they are in the file ! I can’t belive I was so fucking stupid !  */

gallery-2.0.4/modules/core/classes/GalleryStorage:
else if ($affectedRows > 1) {
   /* Holy shit, we just updated more than one row!  What do we do now? */
   return GalleryStatus::error(ERROR_STORAGE_FAILURE, __FILE__, __LINE__,
                        "$query (" . implode('|', $data) . ") $affectedRows");
}

linux-2.4.34.1/arch/sparc/lib/checksum.S:
        /* Sun, you just can’t beat me, you just can’t.  Stop trying,
         * give up.  I’m serious, I am going to kick the living shit
         * out of you, game over, lights out. */

linux-2.6.1/arch/mips/kernel/sysirix.c:
    /* 2,191 lines of complete and utter shit coming up… */

nfs-utils-1.1.0/utils/statd/misc.c:
    if (!(ptr = malloc (size)))
            /* SHIT!  SHIT!  SHIT! */
            die (”malloc failed”);

dada-2_10_12:
    # code below replaces code above - any problems?
    # yeah, it doesn’t fucking work.

旧闻一则：神秘的0x5f3759df 不可思议的Quake III源码

/ 35 条评论

    Quake III公开源码后，有人在game/code/q_math.c里发现了这样一段代码。它的作用是将一个数开平方并取倒，经测试这段代码比(float)(1.0/sqrt(x))快4倍：
float Q_rsqrt( float number )
{
  long i;
  float x2, y;
  const float threehalfs = 1.5F;

  x2 = number * 0.5F;
  y  = number;
  i  = * ( long * ) &y;  // evil floating point bit level hacking
  i  = 0x5f3759df - ( i >> 1 ); // what the fuck?
  y  = * ( float * ) &i;
  y  = y * ( threehalfs - ( x2 * y * y ) ); // 1st iteration
  // y  = y * ( threehalfs - ( x2 * y * y ) ); // 2nd iteration, this can be removed

  #ifndef Q3_VM
  #ifdef __linux__
    assert( !isnan(y) ); // bk010122 - FPE?
  #endif
  #endif
  return y;
}

    code/common/cm_trace.c中也出现了这样一段解释sqrt(x)的函数，与上面的代码唯一不同的就是这个函数返回的是number*y：
/*
================
SquareRootFloat
================
*/
float SquareRootFloat(float number) {
    long i;
    float x, y;
    const float f = 1.5F;

    x = number * 0.5F;
    y  = number;
    i  = * ( long * ) &y;
    i  = 0x5f3759df - ( i >> 1 );
    y  = * ( float * ) &i;
    y  = y * ( f - ( x * y * y ) );
    y  = y * ( f - ( x * y * y ) );
    return number * y;
}

    这样的代码速度肯定飞快，我就不用多说了；但算法的原理是什么呢？其实说穿了也不是很神，程序首先猜测了一个接近1/sqrt(number)的值，然后两次使用牛顿迭代法进行迭代。根号a的倒数实际上就是方程1/x^2 – a = 0的一个正实根，它的导数是-2/x^3。运用牛顿迭代公式x' = x – f(x)/f'(x)，式子化简为x' = x * (1.5 – 0.5a * x^2)。迭代几次后，x的值将趋于1/sqrt(a)。
    但这段代码真正牛B的是那个神秘的0x5f3759df，因为0x5f3759df – (i >> 1)出人意料地接近根号y的倒数。人们都不知道这个神秘的常数是怎么来的，只能把它当作神来膜拜。这个富有传奇色彩的常数到底咋回事，很少有人说得清楚。这篇论文比较科学地解释了这个常数。

Linux下的数学工具Maxima 简明教程（下）

/ 6 条评论

三角运算
(%i1) trigexpand(sin(10*x+y));
(%o1)                 cos(10 x) sin(y) + sin(10 x) cos(y)
(%i2) trigexpand(sin(2*x));
(%o2)                           2 cos(x) sin(x)
(%i3) trigsimp(2*cos(x)^2+sin(x)^2);
                                     2
(%o3)                             cos (x) + 1
(%i4) trigreduce(-sin(x)^2+3*cos(x)^2+x);
                      cos(2 x)      cos(2 x)   1        1
(%o4)                 -------- + 3 (-------- + -) + x - -
                         2             2       2        2

代数推理
(%i1) assume(x>0,y<-1,z>=0);
(%o1)                      [x > 0, y < - 1, z >= 0]
(%i2) assume(a<b and b<c);
(%o2)                           [b > a, c > b]
(%i3) facts();
(%o3)               [x > 0, - 1 > y, z >= 0, b > a, c > b]
(%i4) is(a>c);
(%o4)                                false
(%i5) is(z-y>0);
(%o5)                                true
(%i6) is(z-x>0);

Maxima was unable to evaluate the predicate:
z - x > 0
-- an error.  Quitting.  To debug this try debugmode(true);
(%i7) prederror:false;
(%o7)                                false
(%i8) is(z-x>0);
(%o8)                               unknown
(%i9) forget(a<b);
(%o9)                               [b > a]
(%i10) is(a>c);
(%o10)                              unknown

级数计算
(%i1) sum(i,i,1,5);
(%o1)                                 15
(%i2) sum(i^2,i,1,5);
(%o2)                                 55
(%i3) sum(1/2^i,i,1,inf);
                                   inf
                                   ====
                                        1
(%o3)                               >    --
                                   /      i
                                   ====  2
                                   i = 1
(%i4) sum(1/2^i,i,1,inf),simpsum;
(%o4)                                  1
(%i5) sum(1/i^2,i,1,inf),simpsum;
                                        2
                                     %pi
(%o5)                                ----
                                      6
(%i6) sum(1/i,i,1,inf),simpsum;
(%o6)                                 inf

微积分
(%i1) limit(1/x,x,inf);
(%o1)                                  0
(%i2) limit(sin(x)/x,x,0);
(%o2)                                  1
(%i3) limit(sin(x),x,inf);
(%o3)                            &n
bsp;    ind
(%i4) diff(3*x^2+x+5/x,x);
                                       5
(%o4)                            6 x - -- + 1
                                        2
                                       x
(%i5) diff(sin(x)*tan(x),x);
                                           2
(%o5)                   cos(x) tan(x) + sec (x) sin(x)
(%i6) diff(%e^(a*x),x);
                                        a x
(%o6)                               a %e
(%i7) integrate(sin(x)^3,x);
                                  3
                               cos (x)
(%o7)                          ------- - cos(x)
                                  3
(%i8) integrate(x^3,x,1,3);
(%o8)                                 20
(%i9) taylor(%e^x,x,0,3);
                                     2    3
                                    x    x
(%o9)/T/                    1 + x + -- + -- + . . .
                                    2    6
(%i10) taylor(sin(x),x,0,5);
                                  3    5
                                 x    x
(%o10)/T/                    x - -- + --- + . . .
                                 6    120
(%i11) taylor(sqrt(x+1),x,1,3);
                                                     2                  3
                    sqrt(2) (x - 1)   sqrt(2) (x - 1)    sqrt(2) (x - 1)
(%o11)/T/ sqrt(2) + --------------- - ---------------- + ----------------
                           4                 32                128
                                                                        + . . .
(%i12) ratsimp(%);
                      3              2
             sqrt(2) x  - 7 sqrt(2) x  + 43 sqrt(2) x + 91 sqrt(2)
(%o12)       -----------------------------------------------------
                                      128

矩阵运算
(%i1) f[i,j]:=i+j;
(%o1)                           f     := i + j
                                 i, j
(%i2) genmatrix(f,3,3);
                                  [ 2  3  4 ]
                                  [         ]
(%o2)                       &nbs
p;     [ 3  4  5 ]
                                  [         ]
                                  [ 4  5  6 ]
(%i3) g[i,j]:=i-2^j;
                                              j
(%o3)                           g     := i - 2
                                 i, j
(%i4) genmatrix(g,3,3);
                               [ - 1  - 3  - 7 ]
                               [               ]
(%o4)                          [  0   - 2  - 6 ]
                               [               ]
                               [  1   - 1  - 5 ]
(%i5) %o2+%o4;
                                 [ 1  0  - 3 ]
                                 [           ]
(%o5)                            [ 3  2  - 1 ]
                                 [           ]
                                 [ 5  4   1  ]
(%i6) %o2.%o4;
                               [ 2  - 16  - 52 ]
                               [               ]
(%o6)                          [ 2  - 22  - 70 ]
                               [               ]
                               [ 2  - 28  - 88 ]
(%i7) %o2^^3;
                               [ 360  474  588 ]
                               [               ]
(%o7)                          [ 474  624  774 ]
                               [               ]
                               [ 588  774  960 ]
(%i8) x:matrix([17, 3],[-8, 11]);
                                  [ 17   3  ]
(%o8)                             [         ]
                                  [ - 8  11 ]
(%i9) x^^-1;
                                [ 11      3  ]
                                [ ---  - --- ]
                                [ 211    211 ]
(%o9)                           [            ]
                                [  8    17   ]
            &n
bsp;                   [ ---   ---  ]
                                [ 211   211  ]

想了解更多请阅读官方文档：
http://maxima.sourceforge.net/docs/manual/en/maxima.html

做人要厚道
转贴请注明出处

Linux下的数学工具Maxima 简明教程（上）

/ 25 条评论

    这个Blog里曾经多次提到过超强数学软件Mathematica，但目前为止我还没发现它的Linux版，Wine似乎也没有用。其实，在Linux下也有很多类似于Mathematica的数学软件，其中Maxima是我用的最多的一个。这里简单介绍一下Maxima的各个函数供大家参考，也方便我自己今后查询。

安装：sudo apt-get install maxima maxima-share
运行：maxima
退出：quit();

基本运算
(%i1) 2+3;
(%o1)                                  5
(%i2) 5*6;
(%o2)                                 30
(%i3) %+2;
(%o3)                                 32
(%i4) %o1*%o3;
(%o4)                                 160
(%i5) 4/7+3/4;
                                      37
(%o5)                                 --
                                      28
(%i6) float(%);
(%o6)                          1.321428571428571
(%i7) 2^32;
(%o7)                             4294967296
(%i8) 30!;
(%o8)                  265252859812191058636308480000000
(%i9) float(sqrt(2));
(%o9)                          1.414213562373095

三角函数和对数函数
(%i1) float(sin(1));
(%o1)                           0.8414709848079
(%i2) sin(%pi/2);
(%o2)                                  1
(%i3) sin(%pi/2)+cos(%pi/3);
                                       3
(%o3)                                  -
                                       2
(%i4) float(sec(%pi/3)+csc(%pi/3));
(%o4)                          3.154700538379252
(%i5) log(1);
(%o5)                                  0
(%i6) float(log(10));
(%o6)                          2.302585092994046
(%i7) log(%e);
(%o7)                                  1
(%i8) log(2^a);
(%o8)                              log(2) a
(%i9) %e^log(2);
(%o9)                                 2

变量操作
(%i1) a^2-b^2;
                                     2    2
(%o1)                               a  - b
(%i2) a:3;
(%o2)                                  3
(%i3) a^2-b^2;
                                         2
(%o3)                               9 - b
(%i4) b:2;
(%o4)                                  2
(%i5) a^2-b^2;
(%o5)                                  5
(%i6) kill(a);
(%o6)                                done
(%i7) kill(b);
(%o7)                                done
(%i8) a^2-b^2;
                                     2    2
(%o8)                      &nb
sp;        a  - b

函数操作
(%i1) f(x):=x^2-1;
                                         2
(%o1)                           f(x) := x  - 1
(%i2) f(2);
(%o2)                                  3
(%i3) f(100);
(%o3)                                9999
(%i4) float(f(2/3));
(%o4)                         - 0.55555555555556
(%i5) a:4/5;
                                       4
(%o5)                                  -
                                       5
(%i6) f(a);
                                       9
(%o6)                                - --
                                       25

多项式运算（展开、合并、化简和消元）
(%i1) expand((a+b)^3);
                            3        2      2      3
(%o1)                      b  + 3 a b  + 3 a  b + a
(%i2) factor(a^2-b^2);
(%o2)                          - (b - a) (b + a)
(%i3) ratsimp((x^2-1)/(x+1));
(%o3)                                x - 1
(%i4) eliminate([x^2+x*y+z=0,3*x+5*y+z=0,x-y-2*z^2=1],[y,z]);
                             4      3       2
(%o4)               [- x (8 x  - 2 x  + 19 x  - 50 x + 25)]

解方程
(%i1) solve(x^2-3*x+4/x=5,x);
                         sqrt(5) + 1      sqrt(5) - 1
(%o1)             [x = - -----------, x = -----------, x = 4]
                              2                2
(%i2) funcsolve(f(n)*(n+1)+2*n=1-f(n)/n,f(n));
                                      n (2 n - 1)
(%o2)                        f(n) = - -----------
                                       2
                                      n  + n + 1
(%i3) solve([x+3*y=10,1/x+x*y=4],[x,y]);
                              sqrt(69) - 9      4 sqrt(3) sqrt(23) - 34
(%o3) [[x = 1, y = 3], [x = - ------------, y = -----------------------],
                                   2            9 sqrt(3) sqrt(23) - 75
                                    sqrt(69) + 9      4 sqrt(3) sqrt(23) + 34
                               [x = ------------, y = -----------------------]]
                                         2            9 sqrt(3) sqrt(23) + 75
(%i4) solve(x^2+b*x+c=0,x);
                           2                       2
                     sqrt(b  - 4 c) + b      sqrt(b  - 4 c) - b
(%o4)         [x = - ------------------, x = ------------------]
                      &nbs
p;      2                       2
(%i5) find_root(x^x=2,x,1,2);
(%o5)                          1.559610469462369
(%i6) find_root(sin(x)=x/2,x,0.1,%pi);
(%o6)                          1.895494267033981

数论相关
(%i1) mod(100,7);
(%o1)                                  2
(%i2) primep(3214567);
(%o2)                                true
(%i3) next_prime(200);
(%o3)                                 211
(%i4) factor(1001);
(%o4)                               7 11 13
(%i5) factor(30!);
                        26  14  7  4   2   2
(%o5)                  2   3   5  7  11  13  17 19 23 29
(%i6) gcd(200,780);
(%o6)                                 20
(%i7) binomial(7,4);
(%o7)                                 35
(%i8) fib(7);
(%o8)                                 13

画函数图像
(%i1) plot2d(x^3+2*x^2-3,[x,-2,2]);
*** X11 output driver not found, switching to dumb terminal!
*** If you want to use the X11 output, please install the gnuplot-x11 package

  14 ++-------+--------+--------+--------+-------+--------+--------+-------++
     +        +        +        +        +       +       x^3+2*x^2-3 $$$$$$ $
  12 ++                                                                    $+
     |                                                                    $ |
  10 ++                                                                  $ ++
     |                                                                  $   |
     |                                                                  $   |
   8 ++                                                                $   ++
     |                                                                $     |
   6 ++                                                             $$     ++
     |                                                             $$       |
   4 ++                                                          $$        ++
     |                                                          $$          |
   2 ++   
                                                     $$          ++
     |                                                      $$$             |
     |                                                     $$               |
   0 ++                                                 $$$                ++
     |                                               $$$$                   |
  -2 ++$$$$$$$$$$$$$$$$$$$$$$$$$$               $$$$$                      ++
     $$       +        +        $$$$$$$$$$$$$$$$ +        +        +        +
  -4 ++-------+--------+--------+--------+-------+--------+--------+-------++
    -2      -1.5      -1      -0.5       0      0.5       1       1.5       2

(%o1)

你可以通过安装gnuplot-x11让maxima在X上画图，安装方法是：
sudo apt-get install gnuplot-x11
maxima也可以画3D图像，比如执行下面代码可以画出sin(x)cos(y)的图像，我就不贴图了，大家自己试试。
plot3d(sin(x)*cos(y),[x,-2,2],[y,-2,2]);

做人要厚道
转贴请注明出处

神奇的分形艺术（四）：Julia集和Mandelbrot集

/ 44 条评论

    考虑函数f(z)=z^2-0.75。固定z0的值后，我们可以通过不断地迭代算出一系列的z值：z1=f(z0), z2=f(z1), z3=f(z2), …。比如，当z0 = 1时，我们可以依次迭代出：

z1 = f(1.0) = 1.0^2 – 0.75 = 0.25
z2 = f(0.25) = 0.25^2 – 0.75 = -0.6875
z3 = f(-0.6875) = (-0.6875)^2 – 0.75 = -0.2773
z4 = f(-0.2773) = (-0.2773)^2 – 0.75 = -0.6731
z5 = f(-0.6731) = (-0.6731)^2 – 0.75 = -0.2970
…

    可以看出，z值始终在某一范围内，并将最终收敛到某一个值上。
    但当z0=2时，情况就不一样了。几次迭代后我们将立即发现z值最终会趋于无穷大：

z1 = f(2.0) = (2.0)^2 – 0.75 = 3.25
z2 = f(3.25) = (3.25)^2 – 0.75 = 9.8125
z3 = f(9.8125) = (9.8125)^2 – 0.75 = 95.535
z4 = f(95.535) = (95.535)^2 – 0.75 = 9126.2
z5 = f(9126.2) = (9126.2)^2 – 0.75 = 83287819.2
…

    经过计算，我们可以得到如下结论：当z0属于[-1.5, 1.5]时，z值始终不会超出某个范围；而当z0小于-1.5或大于1.5后，z值最终将趋于无穷。
    现在，我们把这个函数扩展到整个复数范围。对于复数z0=x+iy，取不同的x值和y值，函数迭代的结果不一样：对于有些z0，函数值约束在某一范围内；而对于另一些z0，函数值则发散到无穷。由于复数对应平面上的点，因此我们可以用一个平面图形来表示，对于哪些z0函数值最终趋于无穷，对于哪些z0函数值最终不会趋于无穷。我们用深灰色表示不会使函数值趋于无穷的z0；对于其它的z0，我们用不同的颜色来区别不同的发散速度。由于当某个时候|z|>2时，函数值一定发散，因此这里定义发散速度为：使|z|大于2的迭代次数越少，则发散速度越快。这个图形可以编程画出。和上次一样，我用Pascal语言，因为我不会C的图形操作。某个MM要过生日了，我把这个自己编程画的图片送给她^_^

{$ASSERTIONS+}

uses graph;

type
   complex=record
      re:real;
      im:real;
   end;

operator * (a:complex; b:complex) c:complex;
begin
   c.re := a.re*b.re - a.im*b.im;
   c.im := a.im*b.re + a.re*b.im;
end;

operator + (a:complex; b:complex) c:complex;
begin
   c.re := a.re + b.re;
   c.im := a.im + b.im;
end;

var
   z,c:complex;
   gd,gm,i,j,k:integer;
begin
   gd:=D8bit;
   gm:=m640x480;
   InitGraph(gd,gm,'');
   Assert(graphResult=grOk);

   c.re:=-0.75;
   c.im:=0;
   for i:=-300 to 300 do
   for j:=-200 to 200 do
   begin
      z.re:=i/200;
      z.im:=j/200;
      for k:=0 to 200 do
      begin
         if sqrt(z.re*z.re + z.im*z.im) >2 then break
         else z:=(z*z)+c;
      end;
      PutPixel(i+300,j+200,k)
   end;

   readln;
   CloseGraph;
end.

    代码在Windows XP SP2，FPC 2.0下通过编译，麻烦大家帮忙报告一下程序运行是否正常（上次有人告诉我说我写的绘图程序不能编译）。在我这里，程序运行的结果如下：

    这个美丽的分形图形表现的就是f(z)=z^2-0.75时的Julia集。考虑复数函数f(z)=z^2+c，不同的复数c对应着不同的Julia集。也就是说，每取一个不同的c你都能得到一个不同的Julia集分形图形，并且令人吃惊的是每一个分形图形都是那么美丽。下面的六幅图片是取不同的c值得到的分形图形。你可能不相信这样一个简单的构造法则可以生成这么美丽的图形，这没什么，你可以改变上面程序代码中c变量的值来亲自验证。

c = 0.45, -0.1428
  

c = 0.285, 0.01
  

c = 0.285, 0
  

c = -0.8, 0.156
  

c = -0.835, -0.2321
  

c = -0.70176, -0.3842
  

    类似地，我们固定z0=0，那么对于不同的复数c，函数的迭代结果也不同。由于复数c对应平面上的点，因此我们可以用一个平面图形来表示，对于某个复数c，函数f(z)=z^2+c从z0=0开始迭代是否会发散到无穷。我们同样用不同颜色来表示不同的发散速度，最后得出的就是Mandelbrot集分形图形：
    

    前面说过，分形图形是可以无限递归下去的，它的复杂度不随尺度减小而消失。Mandelbrot集的神奇之处就在于，你可以对这个分形图形不断放大，不同的尺度下你所看到的景象可能完全不同。放大到一定时候，你可以看到更小规模的Mandelbrot集，这证明Mandelbrot集是自相似的。下面的15幅图演示了Mandelbrot集的一个放大过程，你可以在这个过程中看到不同样式的分形图形。

网上可以找到很多小程序实现Mandelbrot集的放大过程。把上面给出的代码改一改，你也可以写出一个这样的程序来。

Update：2011 年 8 月 31 日，我对这个话题做了更进一步的讨论 http://www.matrix67.com/blog/archives/4570