*Continued* SuperFractalThing: Arbitrary precision mandelbrot set rendering in Java.

[quaz0r]

ok, on a different note for a minute, i was thinking:  could one apply perturbation (or whatever) to the series approximation?  instead of using the series to compute the for each point, which gets progressively more costly at higher term counts and resolutions, could you instead do that for one or maybe two points, and then use some simpler formula to compute a difference in the deltas or something to more cheaply get the rest?  or something to that effect...

since the only thing changing the output of the series approximation is the , and if those differ by some increment of a constant distance between points, it just seems like maybe there might be some shortcut to perturbing these values of ... or is it not possible?

[quaz0r]

after more tinkering with the truncation error test condition, i have an apparent solution.  the previous suggestion was (max term minus the rest) of the derivative of the series:



this seemed close to a solution at first, but in fact is not, sometimes resulting in overskipping and sometimes resulting in underskipping.  i found that if we instead use the following test condition:



we skip exactly as much as we can without overskipping.  in fact, in testing at various locations, it seems the old test was often overskipping by 1 iteration, but now we always stop exactly at the iteration before overskipping would occur.  and no bogus fudging of or needed to try to correct for bad results.  i set my to the size of the image and to the size of a point.

also with this as before, the subtracting of some SA' terms from others still produces incorrect behavior.  in testing this new condition, simply adding all terms results in the correct behavior, as would seem more typical and intuitive.  i suspect perhaps the subtracting of terms and such was an experimental attempt to counter overskipping.

a few results from testing some of the locations used in this thread, @1280x720:


claude's location

min iter:  3554

old test, 8 terms:  3216,  Incorrect render
new test, 8 terms:  3215,  correct render

old test, 16 terms:  3298,  Incorrect render
new test, 16 terms:  3297,  correct render

old test, 32 terms:  3368,  correct render
new test, 32 terms:  3375,  correct render

old test, 64 terms:  3380,  ?
new test, 64 terms:  3379,  correct render



redshifter's light years away location

min iter:  313767

old test, 8 terms:  282752,  Incorrect render
new test, 8 terms:  282751,  correct render

old test, 16 terms:  282752,  correct render
new test, 16 terms:  300358,  correct render

old test, 32 terms:  282752,  correct render
new test, 32 terms:  313030,  correct render

old test, 64 terms:  282752,  correct render
new test, 64 terms:  313083,  correct render

[claude]

it seems the old test was often overskipping by 1 iteration

Are you sure that this isn't an off-by-one error in your code?  If the test fails, I roll back to the previous iteration (the last one that succeeded), instead of using the failing values.

Pseudo-code:

Code:

old values <- initialize
loop
  next values <- series approximation step (old values)
  ok <- check validity (next values)
  if ok
    old values <- next values
  else
    break
final values to use <- old values

[quaz0r]

Are you sure that this isn't an off-by-one error in your code?  If the test fails, I roll back to the previous iteration

its certainly always possible  

though i dont really follow your meaning either.  why would you suspect my code of being off if you are the one rolling back by one, and my new results are skipping the full amount possible without overskipping?  as ive previously stated it seems pretty obvious after more testing that the old test is no good, both overskipping and drastically underskipping, and this seems to have been the case for all of us whether we've realized it immediately or not.  recall at your test location you were overskipping by quite a bit, resulting in an incorrect render you didnt notice at first, and then you fudged your tmax by quite a bit until you got that particular location to seemingly render properly, even though it seems this was not actually the right solution to the right problem.

as my new test results show, there is more than a difference of 1  youll notice how the old test gets stuck at 282752 at the light years away location.  i believe when knighty was testing that location he indicated getting stuck there also.  i believe he has also indicated noticing in testing different skip amounts at various locations that his test was often overskipping by 1?  i now seem to be skipping the full amount possible in addition to not encountering any overskipping yet which would require rolling back or whatever.

that being said, i still wish the test condition could be arrived at through some sort of well-understood, well-defined process that yields a specific and proper answer to what exactly should go in that part of the formula, instead of having to play around by trial and error.  im not sure what the malfunction has been in that respect.  i guess knighty did say "the math is not easy."  fair enough    that means we need to keep testing, experimenting with new things, and verifying results.  it also means we should be careful not to blindly get married to the first thing he posts, considering he has shown a tendency to mistype things and mis-copypaste things in addition to possibly misconceiving of things.  perhaps the first question should be, is He off by 1?  or more  

[claude]

though i dont really follow your meaning either.  why would you suspect my code of being off if you are the one rolling back by one, and my new results are skipping the full amount without overskipping?  as ive previously stated it seems pretty obvious after more testing that the old test is no good, both overskipping and drastically underskipping, and this seems to have been the case for all of us whether we've realized it immediately or not.  recall at your test location you were overskipping by quite a bit, resulting in an incorrect render you didnt notice at first, and then you fudged your tmax by quite a bit until you got that particular location to seemingly render properly, even though it seems this was not actually the right solution to the right problem.

Rolling back to the last "ok" set of coefficients is the right thing to do, I'm pretty sure.

My old code was buggy, and had tmax set to a too-small value, so it's not surprising the output was buggy too, though I should have spotted it.  But that wasn't so much fudging as bug fixing (though the initial fix was a bit quick and dirty).  The latest code I posted in this thread should be correct, with tmax set to the maximum distance from the corners to the reference.

as my new tests show, there is more than a difference of 1  youll notice how the old test gets stuck at 282752 at the light years away location.  i believe when knighty was testing that location he indicated getting stuck there also.  i believe he also indicated noticing in testing different skip amounts that his test was often overskipping by 1.  i now seem to be skipping the full amount in addition to not encountering any overskipping yet which would require rolling back or whatever.

that being said, i still wish the test condition could be arrived at through some sort of well-understood, well-defined process that yields a specific and proper answer to what exactly should go in that part of the formula, instead of having to play around by trial and error.  im not sure what the malfunction has been in that respect.  i guess knighty did say "the math is not easy."  fair enough    that means we need to keep testing, experimenting with new things, and verifying results.

Indeed, thanks for your experiments, but as you say without theoretical grounding it's hard to know whether it's just luck that it works or really true everywhere...
(But even if the hardmaths gives a result that is valid for infinitely precise series approximation coefficients, there's the whole nother can of worms from reducing the precision to manageable levels...)

How are you calculating |z+SA(tmax)| and |SA'(tmax)|?  As the sum of the absolute values of the terms? (EDIT I implemented it like that, seems to work in a couple of small tests)

[quaz0r]

Rolling back to the last "ok" set of coefficients is the right thing to do

sure, if you find that your stop condition often stops 1 too late, rolling back by 1 is certainly what should happen if nothing else.

as you say without theoretical grounding it's hard to know whether it's just luck that it works or really true everywhere

indeed, though given that knighty's guesses at possible things to try for the test condition are exactly that, it seems like maybe we are still suffering from wanting to be married to his initial guesses.  in any case, im not trying to convince you of anything here, im simply reporting some results from some of my experiments, and trying to keep the dialog going.  these new results seem very promising to me.  if they do not interest you that is ok.

How are you calculating |z+SA(tmax)| and |SA'(tmax)|?  As the sum of the absolute values of the terms?

maybe i didnt write it right, i think i saw knighty write it like that    i was simply replicating pieces of the formula that he already came up with, this being |z+SA(tmax)|:



and this being |SA'(tmax)|:

(But even if the hardmaths gives a result that is valid for infinitely precise series approximation coefficients, there's the whole nother can of worms from reducing the precision to manageable levels...)

indeed  

[claude]

Cool, thanks!  I do find it interesting, will investigate further later today.  The implementation is as I suspected (I guess you miss a ^i in the first expression?), thanks for confirmation!

[quaz0r]

yes, fixed 

[claude]

Updated my example code with a runtime choice of stopping condition (either knighty or quaz0r), and automatic primary reference point finding with Newton's method (instead of simply using image center).

Example:

Code:

./a.out --width 1920 --height 1080 --maxiters 65536 --re -1.7490930547842157115735991351312021280767302886600874275176041515873173828 --im -0.000175618967275210134352664990246036215136914278796260509941399986977798 --radius 1e-47 --precision 100 --order 32 --stopping quaz0r --output out.ppm

[quaz0r]

neat.  i havent tried the root finding stuff yet.  i thought you had to have some starting information to work with like a derivative or such?  but you are using it to pick a good reference point before any other information is known?  i'll take a peek at your code here, thanks.

[claude]

The main thing you need is the period.  You can use the center of the image as an intial guess.  My example code has two ways of finding period, the first is better (works when zoomed out further from a nucleus) but can sometimes fail - usually this is when zooming off-center but not far enough in to detect the new reference, the fallback method can find the previous nucleus that has been zoomed far away (but not too far to be useful).  The second method always succeeds but in the unlikely worst case might give 0+0i or some other similarly unsuitable as reference - not sure what to do about this, interactive programs could re-use the reference from the previous view...

[quaz0r]

"but sometimes can fail"  this is exactly what i have envisioned regarding anything having to do with the period, which is why all things period-related have been at the very bottom of my todo list.  you cant rely on direct comparison of floating-point values, especially after thousands or millions of iterations of computation, and similarly i dont see how you can rely on a fuzzy comparison either.  what do you do after a million iterations, use a fuzz factor of a million times epsilon?  and of course i think properly analyzing the propagation of floating-point error would not be that simple either.  in any case, no matter what you might do it seems doomed to always be unreliable.

with regard to your example code, im not clear on the meaning of its console output.  i was going to try the light years away location with it, and doing a small test render it looks like im entering the right location information.

Code:

$ ./msa-v6 --width 320 --height 200 --maxiters 360000 --re -1.76904090125288168240284276810365472222460651367280300612031519864776551390840630119504817227707689276670981344397551593371805167279428144061799517560299280824 --im -0.00316054002725585687597452686360873344443505151775719080569769837935155069602621497041147081901473680485729761920491032720741888487688356001952853460889810026385 --radius 6e-140 --precision 156 --order 32 --output out.ppm

it says "series approximation iteration 12564."  is that supposed to be the skip amount?

[claude]

The period detection is based on properties of the Mandelbrot set, not comparison of floating point values - so there's no fuzz factor involved.  See http://www.mrob.com/pub/muency/period.html

it says "series approximation iteration 12564."  is that supposed to be the skip amount?

Yes, it counts up and the last value displayed (when the next line is output) is the skip count.  But 43113 iterations skipped is what I get with both --stopping methods at this location...

[quaz0r]

ah, i guess you are using fp exception stuff.  i had compiled with -Ofast, it works now with -O3, and says 43113 at that location.  43113 is still way too low for the light years away location.  maybe im not entering the location right.  is it reporting the skip amount as an amount past a multiple of the period or something?  it reports a period of 126210, (126210*2)+43113 is 295533, that would be more in the expected range for this location.

the period detection scheme you linked to is very intriguing!  can it be said to be perfectly reliable?

after another day of testing my stop condition, it still seems to be skipping the maximum, with no fails yet.  hopefully knighty has some additional insight for us  

[knighty]

That's because R overflows! One need to balance the exponents of the coefficients and Delta_t in the SA polynomial... or use a floatExp type like in kallesfraktaler.
(Edit: see the code attached here. It runs slowly at the beggining of SA computation because of denormals. This issue is solved now, I'll post the updated code ASAP (meaning probably not today))

@quasor: I never said that I was overskipping by one. The fact is that in claude's code n is initialized to 1 so it outputs the skipped number of iterations +1.
So far, the test that I have proposed always gives a skipped number of iterations less or equal to the optimum. I also output in the picture the per pixel error. It is quite cheap and gives you the ability to see immediately if the method fails.

Your formula is very interesting: It gives a skip number very close to the optimum but here it usually overskip (by a little amount). I gess you use bigger Tmax value... The question is why it works?