探讨Mandelbrot算法，如何更快？
Mandelbrot算法是分形理论中的经典内容， 其葫芦形的图形几乎是分形的标志。该图形虽然及其复杂、有无限精细的结构，但描述它的算法又是极简单的，一般的程序语言只要几十上百行语句就行了。
我曾经用好几种语言写过这个算法。比如，用AutoLisp语言写的程序，充分利用了AutoCAD 的
3D功能。但这同时也是最慢的算法。 最快的算法当属用Turbo C编写的了，效率很高。而且经过我的"优化"， 速度得到进一步的提高。
该算法要对屏幕上的每个象素都做几十上百次的复数迭代运算，是个典型的浮点密集型的算法。最好是用Intel的CPU来计算，我曾在Cyrix 5x86 100Mhz上运行过，速度竟然仅与Intel 486DX66相仿。画整个屏幕总得几十秒甚至近一分钟（每个点的最大迭代上限是256）。记得在286上运行时(不但速度慢， 而且是没有浮点处理器的)，竟然要花2个多小时。
于是，想尽办法进行优化。其实很明白，对程序优化是没什么意义的，最大量的运行时间花在那个复数公式的迭代上，所以要从算法上优化。
观察整个图形和画图的过程，可以发现，在靠近原点的一大片地方都是同一种颜色的（在我的程序中被描为黑色），这其实就是所谓的组成Mandelbrot集合的点。这也是最花费时间的地方，因为该集合中每个点理论上经过无数次迭代都不会溢出，所以在程序中都要经过最多次（由程序常数决定）迭代。这块地方应该是最有潜力可挖的地方。因此，改一点一点地描为跳跃地前进。如果发现某点的下一点有相同的颜色值，那下
一次就尝试计算相隔2点的那点，如果还是有相同的值，就跳跃4点计算。如此，一直达到规定的最大跳跃值（我定义为16），在这个幅度上跳跃计算。在跳跃式计算中一旦发现计算值不同，就马上取消跳跃，恢复到一点一点式的计算。
经过这样的优化，中间黑色区域的计算时间大大地缩短。在变化比较缓慢的地方同样有很好的效果。程序总体的优化效果还是很明显的。
但是，我始终认为，这不是一个好的优化方法。这不但未从本质上优化算法，而且本身违背了分形算法。我甚至认为，对于Mandelbrot算法，本质上是没有什么优化方法的。因为，分形的中心思想之一，就是分形对象的无限精细的结构。只要初始值有及其细微的不同，就难以预半夜凉初透言以后的结果到底会是怎么样的，可能相差很大。所谓"失之毫厘，谬以千里"。我这种"局部地区相同"的优化思想是与之直接相悖的。
再考察一下我的"优化"，可以发现这样的缺陷，如果恰巧跳跃的两点值相同，但中间被跳过的点有不同的值，那么我的程序就不能发现。这特别容易出现在跳跃步数较大，而那地方又正好有个类似小"尖角"的地方。仔细观察图形，确实有这种情况。所以，还要做很多"技术"处理，明确地告诉程序，在大致什么范围内，是可以放心大胆地跳过去的，什么地方就要小心了。
我把我很不成功（但有明显的实际效果，呵呵）的所谓"优化"介绍给大家，还希望能看看众位高手的手段。对这个Mandelbrot算法，到底能不能有效地优化？
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
以上文字大概写于1997年吧。老文翻出来，贴在blog。
这么多年下来，PC的运算能力已经有极大的提高。网上也出现了很多能计算这种分形图形的软件，有的还相当不错，能够自定义很多分形公式，定义迭代计算的运算量，定义表现结果的调色板和渲染方式。所以，功能丰富，画面也很漂亮。
而且，得益于快速的CPU速度和高速显卡、DirectDraw等硬件、软件手段，计算和作图的速度也极大提高。有的软件已经能在G级别的CPU上做到接近实时漫游的效果（就是每秒钟能计算渲染出几十桢的画面），看上去效果真的很酷呀。
如果站在现在硬件软件的角度看如何优化这个算法，和当年就有很大不同了。提高速度的最有效算法，就是提高运算的并行度，多个区域、像素同时运算。显然，这个Mandelbrot算法中，每个点之间相互是没有先后和关联因果关系的，完全适用于并行运算。
Intel于1996年在Pentium CPU上推出MMX技术，就是为了加强CPU在处理多媒体数据时候的并行运算能力。但MMX针对的仅仅是整行数据，这对Mandelbrot算法不适用。而后来在Pentium III上出现的SSE指令扩展，就是对并行浮点数运算的支持。
所以，用SSE指令集来并行运算，将是有效提升运算速度的手段。
另外，近年来Intel的多线程技术(HT)，以及即将出现的多内核CPU技术，将从更高层次上提高PC的并行运算的能力，让原来在工作站、服务器上才有的多CPU架构能廉价地在普通PC上实现。如果配合真正支持多线程技术的操作系统（比如NT架构上的Windows2000/XP）和编译器，这类算法将能更快。
(yanlb2000, 2004.11.05)
