Physics 版 (精华区)

发信人: zjliu (秋天的萝卜), 信区: Physics
标  题: 关于Mandelbrote算法 /转载
发信站: 哈工大紫丁香 (Sat May 24 16:19:14 2003) , 转信

发信站: 飘渺水云间 (by lisi)


关于Mandelbrote算法

    Mandelbrote算法是分形理论中的经典内容， 其葫芦形的
图形几乎是分形的标志。该图形虽然及其复杂、有无限精细的
结构，但描述它的算法又是及简单的，一般的程序语言只要几
十上百行语句就行了。
    我曾经用好几种语言写过这个算法。比如，在共享软件版
中我贴了个用AutoLisp语言写的程序，充分利用了AutoCAD 的
3D功能。但这同时也是最慢的算法。 :(   最快的算法当属用
Turbo C编写的了，效率很高。而且经过我的“优化”， 速度
得到进一步的提高。可惜这程序在我的5.25英寸的软盘上，没
地方读出来了。:(((看来我得重新编写了。
    该算法要对屏幕上的每个象素都做几十上百次的复数迭代
运算，是个典型的浮点密集型的算法。最好是用Intel的CPU来
计算，我曾在5x86 100上运行过，速度竟然仅与Intel 486DX66
相仿。画整个屏幕总得几十秒甚至近一分钟（每个点的最大迭
代上限是256）。记得在286上运行时(不但速度慢， 而且是没
有浮点处理器的)，竟然要花2个多小时。机可忍， 我不可忍!
    于是，想尽办法进行优化。其实很明白，对程序优化是没
什么意义的，最大量的运行时间花在那个复数公式的迭代上，
所以要从算法上优化。
    观察整个图形和画图的过程，可以发现，在靠近原点的一
大片地方都是同一种颜色的（在我的程序中被描为黑色），这
其实就是所谓的组成Mandelbrote集合的点。这也是最花费时
间的地方，因为该集合中每个点理论上经过无数次迭代都不会
溢出，所以在程序中都要经过最多次（由程序常数决定）迭代。
这块地方应该是最有潜力可挖的地方。因此，改一点一点地描
为跳跃地前进。如果发现某点的下一点有相同的颜色值，那下
一次就尝试计算相隔2点的那点，如果还是有相同的值，就跳
跃4点计算。如此，一直达到规定的最大跳跃值（我定义为16），
在这个幅度上跳跃计算。在跳跃式计算中一旦发现计算值不同，
就马上取消跳跃，恢复到一点一点式的计算。
    经过这样的优化，中间黑色区域的计算时间大大地缩短。
在变化比较缓慢的地方同样有很好的效果。程序总体的优化效
果还是很明显的。

    但是，我始终认为，这不是一个好的优化方法。这不但未
从本质上优化算法，而且本身违背了分形算法。我甚至认为，
对于Mandelbrote算法，本质上是没有什么优化方法的。因为，
分形的中心思想之一，就是分形对象的无限精细的结构。只要
果还是很明显的。

    但是，我始终认为，这不是一个好的优化方法。这不但未
从本质上优化算法，而且本身违背了分形算法。我甚至认为，
对于Mandelbrote算法，本质上是没有什么优化方法的。因为，
分形的中心思想之一，就是分形对象的无限精细的结构。只要
初始值有及其细微的不同，就难以预言以后的结果到底会是怎
么样的，可能相差很大。所谓“失之毫厘，谬以千里”。我这
种“局部地区相同”的优化思想是与之直接相背的。
    再考察一下我的“优化”，可以发现这样的缺陷，如果恰
巧跳跃的两点值相同，但中间被跳过的点有不同的值，那么我
的程序就不能发现。这特别容易出现在跳跃步数较大，而那地
方又正好有个类似小“尖角”的地方。仔细观察图形，确实有
这种情况。所以，还要做很多“技术”处理，明确地告诉程序，
在大致什么范围内，是可以放心大胆地跳过去的，什么地方就
要小心了。
    我把我很不成功（但有明显的实际效果）的所谓“优化”
介绍给大家，还希望能看看众位高手的手段。对这个Mandel-
brote算法，到底能不能有效地优化？



--

※ 来源:．哈工大紫丁香 http://bbs.hit.edu.cn [FROM: 202.118.229.86]