🚀 go-pugleaf

rms@cs.tu-berlin.de (Michael R. Ganss) writes:

>Does anyone out there know how FractalWitchcraft achieves its speed?

Steve Stoft explained the algorithm in a recent edition of Rollo Silver's
Amyglyda. The idea is that for very deep zooms, orbits of close points
are parallel. You can track the orbits of four points, and when their
original rectangular formation distorts, subdivide. For the iterations
when the orbits track each other, the orbity of the points inside the
rectangle don't have to be computed, resulting in a big savings.

The nature of this is that it is most effective at deep zooms, and the
technique is dependent on the function iterated. The Fractint team looked
at it for a while with some success, but we were distracted by other issues.
The main  implementation problem is the algorithm used to detect deformation
and the algorithm used to interpolate once deformation is detected. The more
liberal the deformation criterion, the longer the calculation can go without
interpolating, but then errors may be introduced. In my limited experiments 
orbits of points in Steve's example deformed rapidly after  10 or 20 iterations
rather than the 500 or 1000 iterations I was hoping for. The results
indicated some promise, but we were far from duplicating his results when
we moved on to other issues. 

My opinion is that this is an excellent bit of work. I hope he publishes
his technique more fully. It would be useful for explorations involving very 
deep zooms. Note, however, that his example is a deep zoom right at
the limit of double precision resolution. The speed gains are very much less 
at more moderate depths, and in fact is much slower than Fractint at moderate
depths. This limitation does not, IMHO, detract from the significance of
the algorithm.

--
Tim Wegner     Fractint co-author
Internet: twegner@mwunix.mitre.org  Compuserve: 71320.675@compuserve.com