News: Visit the official fractalforums.com Youtube Channel

## The All New FractalForums is now in Public Beta Testing! Visit FractalForums.org and check it out!

 Pages: [1]   Go Down
 Author Topic: Does anyone know a trick to compute the derivative of Mandelbrot ?  (Read 2404 times) Description: Issue of precision 0 Members and 1 Guest are viewing this topic.
tit_toinou
Iterator

Posts: 192

 « on: March 25, 2012, 02:59:48 PM »

Hi everyone.
If our iteration formula is z->z^2+c, then d(z^2+c)/dc=2*z*(dz/dc)+1 so we have dz->2*z*dz+1 in our iteration loop.
Then we can compute the distance to the set thanks to |z|*ln|z|/|dz| (see http://www.iquilezles.org/www/articles/distancefractals/distancefractals.htm).

The fact is that the derivative grows very fast, and from the beginning (not just after |z|>2) for a point out of the set.

Does anyone know a trick so that with only a complex number represented by two double numbers, we can compute dz through more iterations ?

Thanks .
 Logged

David Makin
Global Moderator
Fractal Senior

Posts: 2286

 « Reply #1 on: March 25, 2012, 06:32:55 PM »

Mind if  I ask why ?
If you're close enough to the set to need more iterations for accuracy then dz will grow correspondingly more slowly because you are closer to the set - I see no reason to need a large number of iterations further (outside) from the set.......
To put it another way, if you take a point at distance 1 unit from the set and you use a bailout of b then for z^p+c the maximum magnitude of the final value of dz will be (approx.) |b^p|*ln(|b^p|) where p is the power in z^p+c.
So anywhere within 1 unit of the set then as long as you choose a bailout b such that |b^p|*ln(|b^p|) is within your storage limitations (e.g float, double, arbitrary) then the number of iterations is moot.

Of course if you want dz for an "inside" point on a given iteration that's another story.....
 « Last Edit: March 25, 2012, 06:52:08 PM by David Makin » Logged

The meaning and purpose of life is to give life purpose and meaning.

http://www.fractalgallery.co.uk/
"Makin' Magic Music" on Jango
fractower
Iterator

Posts: 173

 « Reply #2 on: March 25, 2012, 07:16:05 PM »

It is easy to construct the poly for skipping iterations. You have already done this for one iteration.

z1 = z^2 + c

2 iterations

z2 = z1^2 +c = z^4 + 2*z^2*c + c^2 +c

The order of the poly grows as 2^iteration which quickly becomes intractable. Also I think you have to renormalize the DE for higher powered polys.
 « Last Edit: March 25, 2012, 10:16:29 PM by fractower » Logged
tit_toinou
Iterator

Posts: 192

 « Reply #3 on: March 29, 2012, 08:15:28 PM »

@David Makin : I want to explore the new connected set discovered by fracmonk. While I can explore perfectly fine z->z^4+c, I have trouble with his formula of the same power (z-> (((zc-1)^2-1)^2-1) ).
And I want a DE so I can color in black the borders of the set.

Thanks for the maximum magnitude approx, I really thought |dz| exploded way before |z| explodes. I was wrong.
How did you find this formula ?

I want more iterations After the dwell limit so that I can get a good approximation of the distance (the formula is supposed to be true at infinity).

And yes it is for points outside.

@fractower:Why would I want to skip iterations?
And I agree I should do something like a normalization, like computing dz/2^n instead of dz. But that wouldn't be continuous anymore since n the number of iterations breaks the continuity.
I have the feeling that precision of dz doesnt matter as much as its scale but I have no idea what to do..
May be I can keep track of ln(dz) instead lf dz since when |z| explode we have dz~=2×z×dz so ln(dz)~=ln2+ln(z)+ln(dz)...
But maybe we do loose the information of the distance to the set by making this approximation.
 « Last Edit: March 29, 2012, 08:19:53 PM by tit_toinou » Logged

David Makin
Global Moderator
Fractal Senior

Posts: 2286

 « Reply #4 on: March 29, 2012, 11:00:41 PM »

<snip>
How did you find this formula ?

You mean this: "To put it another way, if you take a point at distance 1 unit from the set and you use a bailout of b then for z^p+c the maximum magnitude of the final value of dz will be (approx.) |b^p|*ln(|b^p|) where p is the power in z^p+c." ?

That's pretty simple, though I did miss something

Assuming that the standard formula for analytical DE is (at least approximately) correct then we have:

DE = |z|*ln|z|/|dz|

So if the DE is 1 then |dz| = |z|*ln|z| and if DE is d then |dz| = |z|*ln|z|/d so although I did inadvertently turn this upside-down in my head my mistake wasn't that bad....in fact the scale of |dz| does increase as you approach the set relative to |z|*ln|z| but only in a simple inverse relationship with the DE

So if your bailout is m (if testing cabs(z)) then for z^p+c the maximum possible value of |z| "outside" is approx. m^p so the max. poss value of |dz| is m^p*ln(m^p)/d where d is the DE value  i.e. as I said in the previous post the value at 1 unit distance and a bailout of m then the max storage required for dz is that required for m^p*ln(m^p) and if your min. distance (i.e. surface solid threshold) is say 1e-6 then if you require space for 1e100 for the components of |z|*ln(|z|) then you just require 1e106 for the components of dz, although allowing 1e107 would be better

Apologies for the previous mistake !! I sometimes rush in without working things out clearly enough (especially when tired) !!

Of course the closer you want to get to the set then not only will this require more iterations but also higher bailout values since the %age accuracy of the DE does tend to reduce as you get closer to the boundary even if using a "perfect" analytical method for the DE.

With respect to the derivative.....

http://www.fractalforums.com/index.php?action=gallery;sa=view;id=1151
 « Last Edit: March 29, 2012, 11:18:47 PM by David Makin » Logged

The meaning and purpose of life is to give life purpose and meaning.

http://www.fractalgallery.co.uk/
"Makin' Magic Music" on Jango
tit_toinou
Iterator

Posts: 192

 « Reply #5 on: March 30, 2012, 07:06:04 PM »

Just to be clear : I have a bailout value that depends on the iteratiok formula (2 for classic mandelbrot), a dwell limit that needs to be increased a little when zooming, and a NbMoreIterations which corresponds to the number of iterations to compute after the bailout value is reached (when we know that the point is outside the set).

Does your last remark still hold ?

So I really have a (precision-)scale issue...
And you're right, if I really want to compute the distance then i won't be able to zoom more than (min double value) close to the set.
 Logged

David Makin
Global Moderator
Fractal Senior

Posts: 2286

 « Reply #6 on: March 30, 2012, 09:50:13 PM »

If you are going to do extra iterations then you may as well simply use a larger bailout value in the first place - this increases the accuracy of the DE everywhere (analytical or delta).
 Logged

The meaning and purpose of life is to give life purpose and meaning.

http://www.fractalgallery.co.uk/
"Makin' Magic Music" on Jango
tit_toinou
Iterator

Posts: 192

 « Reply #7 on: April 01, 2012, 04:40:44 PM »

No because I would "loose" points z such that |z|>2 and |z|<newBailout that are outside the set but didn't reach the newBailout value.
But you're right, I could use a second bailout value so that I have the maximum precision.

I've managed to gain in precision : instead of iterating (z-> (((zc-1)^2-1)^2-1) ), i'm iterating (z->zc-1) and twice z->z^2-1. I can compute a few more iterations after |z|>2.
I still have a discontinuity   (but it is thinner than before).

Also, by making the approximation z~=z^2 and dz~=2×z×dz when |z|>2, the Distance Estimator reach its final value.. So doing this is like stopping the computation just after the bailout.
It means that the "information of the distance to the set" is lost when forgetting the "+c"...

Do I really need to use arbitrary precision arithmetic libraries ?
 Logged

David Makin
Global Moderator
Fractal Senior

Posts: 2286

 « Reply #8 on: April 01, 2012, 11:23:04 PM »

No because I would "loose" points z such that |z|>2 and |z|<newBailout that are outside the set but didn't reach the newBailout value.
But you're right, I could use a second bailout value so that I have the maximum precision.

I've managed to gain in precision : instead of iterating (z-> (((zc-1)^2-1)^2-1) ), i'm iterating (z->zc-1) and twice z->z^2-1. I can compute a few more iterations after |z|>2.
I still have a discontinuity  (but it is thinner than before).

Also, by making the approximation z~=z^2 and dz~=2×z×dz when |z|>2, the Distance Estimator reach its final value.. So doing this is like stopping the computation just after the bailout.
It means that the "information of the distance to the set" is lost when forgetting the "+c"...

Do I really need to use arbitrary precision arithmetic libraries ?

Only if you want the ridiculously deep zooms that some folks do in 2D

In practice if the DE is reasonably accurate you should be able to get pretty close to the true boundary....

http://www.fractalforums.com/index.php?action=gallery;sa=view;id=1043

i.e. in 2D "double" gets you to around 1e16 magnification so here this is reduced to around 1e12 - though this is an old render and more accurate DE would do better.......

Edit: Note the render time includes full hard-light tracing i.e. full ray-stepping back towards light source for every visible surface pixel....
 « Last Edit: April 01, 2012, 11:36:04 PM by David Makin » Logged

The meaning and purpose of life is to give life purpose and meaning.

http://www.fractalgallery.co.uk/
"Makin' Magic Music" on Jango
David Makin
Global Moderator
Fractal Senior

Posts: 2286

 « Reply #9 on: April 02, 2012, 03:53:12 AM »

No because I would "loose" points z such that |z|>2 and |z|<newBailout that are outside the set but didn't reach the newBailout value.
But you're right, I could use a second bailout value so that I have the maximum precision.

Ah - to be honest I never considered that

It prompts the idea of doing the full DE calculation after *every* iteration once bailout is reached and stopping when two consecutive DE estimates agree to a given accuracy....though maybe that's what you meant you are doing ?
Of course the bailout of magnitude>2 is only proved valid for z^2+c, or maybe z^p+c ? and then only for complex arithmetic where p is real AFAIK, not sure if anyone's proved it for any triplex maths or even for general quaternions or other hypercomplex forms though it's fairly obvious that the proof should extend to bi-complex and probably quaternions -- but here again only for real p.
 Logged

The meaning and purpose of life is to give life purpose and meaning.

http://www.fractalgallery.co.uk/
"Makin' Magic Music" on Jango
 Pages: [1]   Go Down