May
11
Mandelbrot集(4)：算法分析
（yanlb2000, 2007.05.11, yanlb2000.blogcn.com）
继续讨论Mandelbrot集。
今天，来进一步分析一下绘制M集的算法。分析，是为了更多地了解掌握此算法。而且，在此基础上，更可探讨如何优化算法。
绘制M集，其实就是找出屏幕上每个绘图点对应的复数C，然后计算其对应的颜色就可以了。而这个颜色，又是由该绘图点所对应的复数所需要的迭代运算次数来决定的。
前面已经提到，这个迭代式是：
Z := Z*Z + C
其中C是需要考察（计算的）复数点，对于每个绘图点来说，C就是是常数。而变量Z的初始值是0。
我们需要考察每次迭代之后Z的绝对值，看是否大于某常数（可以取为2)。
先分析绘图不同的绘图区域的特点。
对于远离原点的点，比如在以原点为圆心，半径为2的园之外的点，无须迭代，其绝对值就大于2了。不妨称这个区域为NM。
对于接近原点的点，大部分来说，无论迭代多少次，Z的绝对值都不会大于2。它们就是M集上的点了。这里也是最耗费时间的区域，如何设置迭代次数的上限，关系到整体的运算量。这个区域就直接称呼为M吧。
而对于介于以上二者之间的点，或者说是处于M集边缘的那些区域，则需要细细考察。如果一定次数之后绝对值超过2,它们仍不属于M集，但其颜色取决于对应的迭代次数，不同的迭代次数，将绘制出变化多端的图案。当然也有可能超过指定次数后绝对值仍不超过2,那就认为（但不一定全部是！）它们属于M集，仍绘制成黑色。我们将这个区域称为EM。
以上，区域NM和M是"平凡"的，因为结果很明显，要么属于M集，要么不属于M集（NM区域）。复杂的在于第三种情况，EM区域。这里，就算相邻"很近"的两个点，它们对应的运算结果就可能是很不同的（在最终绘图结果上，将表现为不同的像素颜色）。而这，也正是混沌现象的基本特征之一。很微小的初始条件的差别，或者说是对系统初始状态的很小的一点"扰动"，就可能使系统的后续发展最后朝完全不同的方向进行，得到截然不同的结果。这也就是所谓的"蝴蝶效应"。
但同时，任何两个点之间，即使相邻很近，它们之间也是没有"联系"的。每个点最后的结果，只与自己对应的复数值有关，不受任何其他点的影响。这样，我们就可以同时进行多个点的运算，而不用担心点与点之间有因果、先后关系。这是一个非常重要的特性，使我们可以在电脑上实现并行运算！
继续分析。
对于每个点，都需要进行多次的迭代运算。显然，在这个算法中，最多用到的，就是复数的平方、加法、取绝对值等，而这些运算在电脑上最终都可以归结为浮点数的加法和乘法。判定复数绝对值不超过2,等价于判定其平方不超过4。 所以，这是一个典型的运算密集型的算法，程序运行的大部分时间，将花费在这些浮点数运算上。所以，如何提高浮点数运算速度，将对优化算法有决定性作用。当然，从另一方面来说，如何用最少的计算量，达到同样的效果，也是需要考虑的地方。
总结一下，该算法主要有两大特点：
1, 典型的浮点数计算密集型算法。
出于这一点，提高浮点数处理速度，降低运算量，是优化算法的两大内容。
2, 非常适合于并行运算。
可以从CPU硬件、指令集、编译器、源代码等多方面考虑提高并行度。
以上两点，为优化该算法指明了方向。
Tags: Mandelbrot, 分形, 混沌, 算法
