SuperFractalThing: Arbitrary precision mandelbrot set rendering in Java.

[Kalles Fraktaler]

Some members here have expressed their hopes that it would be possible to use only single precision float datatypes when rendering Mandelbrot fractals with this pertubation theory, in order to implement it in GPU, and I did investigations that showed that it was not possible.

However, I did some tests by changing the mantissa member of my floatexp class to be of float instead of double, and the locations I tried so far renders fine with that.
So, the problem using single precision float may not be the precision of the mantissa, which seems to be sufficient.
The problem may instead be that the pertubation calculations have intermediate steps that exceeds the exponent range of the float datatype, (10^-38 - 10^+38)

I hope those who wants to implement this in GPU can use this information and make an extremely fast unlimited Mandelbrot explorer!

[Roquen]

Have I every mentioned that squaring first drastically increases the bound on error?   Seriously...pull out a power of two scale factor.  Out of curiosity I'd assume that someone has tried comparing straight doubles vs. unevaluated sequences (double-double & quad-doubles are examples) for visual impact.  If they increase then the techniques behind can be used to create a computation sequence with performance somewhere in the middle of using straight doubles and a generic method.

[hapf]

So, the problem using single precision float may not be the precision of the mantissa, which seems to be sufficient.
The problem may instead be that the pertubation calculations have intermediate steps that exceeds the exponent range of the float datatype, (10^-38 - 10^+38)

I'm using long double which has a huge exponent range (-4932 - +4932). It does not stop the blobs/distortions from popping up. The mantissa is the problem here. For less demanding regions float might be fine with larger exponent range, but it will fail when zoomed deeper in long before long double will fail.
I see only two solutions to this problem.
- Use arbitrary precision also with formula (1)(no series approximation), with just enough bits to avoid the distortions. That robs the method of its superior hardware float speeds, but is still quite some faster than using full arbitrary precision with bits as required for the normal approach.
- Reliably detect the distortions and assign better suited references in these regions. How to do that automatically, reliably and fast is an open question to me. If any of you have the solution I'm all ears to hear about your approach.
Consider that series approximation approximates (1) and reliably keeping it under control not to deviate too much from (1) will not solve the problems with (1) itself coming from rounding errors summing up gradually to more or less visible corruptions of the image. The higher resolution your image the more different places can pop up that are corrupted and need to be addressed.

[Kalles Fraktaler]

I'm using long double which has a huge exponent range (-4932 - +4932). It does not stop the blobs/distortions from popping up.

I was not referring to the blobs, my previous test using float was not able to create images at all.
But with long double you would be able to zoom to e4932 without having to create any custom datatypes.
I wonder how performance is on the long double datatype compared to double in a 64-bit CPU, does anybody know? Also, is the float datatype really faster on a 64-bit CPU, I would imagine it would be faster on 32-bit but not on 64...?

- Use arbitrary precision also with formula (2), with just enough bits to avoid the distortions.

I don't think this will help, the series approximation just gives you iterations that can be skipped on formula (1), and it is still formula (1) that is used to calculate the pixels. If you would use arbitrary precision on formula (1) it might solve all blobs, you would only gain a little performance with series approximation on simple locations but loose performance on complex ones.

- Reliably detect the distortions and assign better suited references in these regions. How to do that automatically, reliably and fast is an open question to me. If any of you have the solution I'm all ears to hear about your approach. ... The higher resolution your image the more different places can pop up that are corrupted and need to be addressed.

Indeed there can be many blobs on the same image and more to appear when the resolution is increased, and I haven't found any reliable way to detect them all (Pauldebrot might?). I rely on the ability to eventually add references manually...
This one is particularly nasty:
http://www.fractalforums.com/images-showcase-(rate-my-fractal)/flake/

[hapf]

I meant arbitrary precision on formula 1, not 2. On 2 it's useless, of course. 

[Roquen]

Has anyone attempting seeing how equipotential lines are in the problem areas or the proximity of periodic points or how the gradient field looks, etc?

[hapf]

This one is particularly nasty:
http://www.fractalforums.com/images-showcase-(rate-my-fractal)/flake/

Is it looking correct on your image? Did you tweak that a lot? I get your image pretty much directly when rendering with the central minibrot. Does not look very problematic to me (at smaller sizes). Just kind of boring/blobby look when not enough colours are pumped into it.

[hapf]

Has anyone attempting seeing how equipotential lines are in the problem areas or the proximity of periodic points or how the gradient field looks, etc?

What problem areas? Areas where distortions happen? These areas are due to the reference point so they come and go with different reference points. What often happens is that the distance measure clips there too leaving blobs or dithered areas behind where there should be proper structure. So the gradients and equipotential lines get distorted.

[Roquen]

I was thinking long the lines of choosing reference points.

[hapf]

I was thinking long the lines of choosing reference points.

The solution must come from a better understanding why one reference point produces more rounding errors with a specific point than another. 2 main factors to look into:
- distance of reference point (generally the farer away from the region/picture/point the worse)
- dominant period of point and reference point and how well the 'jumping around patterns' are in harmony (to be defined clearly what in harmony means regarding to rounding errors)

[Kalles Fraktaler]

Is it looking correct on your image? Did you tweak that a lot? I get your image pretty much directly when rendering with the central minibrot. Does not look very problematic to me (at smaller sizes). Just kind of boring/blobby look when not enough colours are pumped into it.

There are a lot of small spirals in this flake image, and many references are needed to render them all...

[Kalles Fraktaler]

The solution must come from a better understanding why one reference point produces more rounding errors with a specific point than another. 2 main factors to look into:
- distance of reference point (generally the farer away from the region/picture/point the worse)
- dominant period of point and reference point and how well the 'jumping around patterns' are in harmony (to be defined clearly what in harmony means regarding to rounding errors)

From what I understand from Pauldebrot's explanation, and animation, of his solution is that he tried to narrow down areas where the iterations increase until it ends in a plateau with equal iterations - and that is where the blob is. But my experience is that the blobs also can occur in the middle of areas with decreasing iterations, or areas where the iterations increase and then a narrow surrounding of decreased iterations just around the blob. Or many other situations.
I think his approach is correct though, that the all blobs appear as a plateau on increasing iterations, but since our images are based on pixels, pixels may not be enough resolution to identify increasing iterations surrounding plateaus.
It's like a landscape with hills and valleys, and some of the hill-tops are chopped off - these are what we are to find. They usually have a round shape, but since they can be in the edge of an image, they can have any shape.

[hapf]

AIUI, Superfractalthing also has some method for determining when a second reference point is needed; I don't know about Kallesfractaler, though, or the methods either use. I've described mine in the hope that it may be helpful to either of their authors, and in the hope that someone might have a useful suggestion for speeding my own up.

I don't know about speed up potential but once you have a region located that contains a blob or is inside a blob and you look for the pixel with the highest iteration count to serve as a second reference you can instead of checking pixels simply compute the location of the period center of a minibrot in that region. A reasonable guess for a suitable period is the highest iteration count you have seen so far in that region minus one or two starting the computation from the pixel that had that count. If periods get very large though computation time gets quite long. Arbitrary precision is required. One can try to speed up the calculations by using PT again, but the benefits are unfortunately quite limited since rounding errors spoil the result quickly (e.g. endless loops and other anomalies).

[Kalles Fraktaler]

Beside that, how are things going with your long double SFT program?
I'm very interested in the long double datatype, and Microsoft's compiler does not support it.
I tried "Bloodshed Dev-C++" which supports the 12 byte long double datatype. However the Dev-C++ program had slower performance than my custom datatype.

It would be interesting if anyone could confirm my findings. Is the long double datatype very slow compared to double (some 20 times slower)? Or is Microsoft's compiler super optimized and superior to other compilers? Or did I do something else fundamentally wrong?

[hapf]

Beside that, how are things going with your long double SFT program?
I'm very interested in the long double datatype, and Microsoft's compiler does not support it.
I tried "Bloodshed Dev-C++" which supports the 12 byte long double datatype. However the Dev-C++ program had slower performance than my custom datatype.
It would be interesting if anyone could confirm my findings. Is the long double datatype very slow compared to double (some 20 times slower)? Or is Microsoft's compiler super optimized and superior to other compilers? Or did I do something else fundamentally wrong?

Long double on Linux is 16 bytes (8 significand, 15 bits exponent, 1 bit sign, rest unused). It is not much slower than double.
64 bit significand is not enough to avoid blobs/corruption, unfortunately. So I'm currently working on the blob fixing part of the program. Automatic reference point generation is done and works well. Quite cool to let the program zoom in automatically to a minibrot in the neighbourhood of a pixel jumping from E-20 to E-40 or E-100 to E-400.