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

claude

Fractal Bachius

Posts: 563

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

« Reply #210 on: August 16, 2016, 03:38:47 PM »

Quote from: knighty on August 13, 2016, 10:37:12 PM

Ok!
The last formula for cheking if the series appriximation is good at iteration n should be:

R_n*|tmax|⁴ <= (|A_n| - 2*|B_n|*|tmax| - 3*|C_n|*|tmax|²)* |<Quoted Image Removed>|

Where:

R_n*|tmax|⁴ is an upper bound on the truncation error.

(|A_n| - 2*|B_n|*|tmax| - 3*|C_n|*|tmax|²) is a lower bound on the absolute value of the derivative. As it is, it can be negative which means that the derivative could be 0 somewhere so the approximation's quality is likely to be too low.

|<Quoted Image Removed>| is related to the "radius" that corresponds to a pixel.

|tmax| is the maximal distance between the reference point and any point of the rendered area.

I don't understand why the derivative being small is a problem.

I switched to this alternative which allows much more to be skipped (beyond one period) without affecting appearance adversely in my tests:

R_n*|tmax|^m+1 <= | $\Delta t$ |

The rationale is that if the truncation error in the Z plane is less than the size of a pixel in the C plane, should be fine (because Z values will spread out from the original C values, except in interior regions). If it looks fuzzy when I add distance estimation then I'll see what adding a 1e-3 factor does to it.


	Logged

knighty

Fractal Iambus

Posts: 819

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

« Reply #211 on: August 16, 2016, 04:26:10 PM »

@Quazor:
Glad it worked. Thank you very much.

The formulas were derived 5 months ago. I'll have to re check the formula for arbitrary m before posting it.

@claude:
Thank you for looking at it.

I think Rn can still be used when zooming towards a good reference point because the tmax in the test can be different from the one used for the computation of Rn. It would be much smaller as one zooms in.

I realize now that the test have to be changed: The derivative necessarily becomes 0 at some point inside the minibrot. Therefore, the lower bound of the absolute value of the derivative -as computed- will necessarily be negative after 1 period or so. What we actually need is a lower bound of the magnitude of the derivative outside the set... not easy if ever possible. For test purposes on can still do the test per pixel to see where the series approximation error becomes too big.

How many iterations doest it skip if stopping at when R*|tmax|==|a_m|? (that is the truncation error equals last term of the series approximation)

Quote from: Kalles Fraktaler on August 16, 2016, 02:07:31 PM

Seems tmax and <Quoted Image Removed> are limited to double precision, unless you are using some other datatype?

$\Delta t$ is very small so one can't use double precision.

PS: I was still writing when claude posted the previous message.


	Logged

knighty

Fractal Iambus

Posts: 819

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

« Reply #212 on: August 16, 2016, 04:38:37 PM »

Quote from: claude on August 16, 2016, 03:38:47 PM

I don't understand why the derivative being small is a problem.

I switched to this alternative which allows much more to be skipped (beyond one period) without affecting appearance adversely in my tests:

R_n*|tmax|^m+1 <= |<Quoted Image Removed>|

The rationale is that if the truncation error in the Z plane is less than the size of a pixel in the C plane, should be fine (because Z values will spread out from the original C values, except in interior regions). If it looks fuzzy when I add distance estimation then I'll see what adding a 1e-3 factor does to it.

Great!

The derivative is there because (to be accurate in the error estimation) the image of the area of a pixel by the series approximation should be always bigger than the area of the truncation error at that pixel. Unfortunately, the derivative vanishes inside minibrots after 1 perod or so.


« Last Edit: August 16, 2016, 11:28:10 PM by knighty, Reason: Mistake »	Logged

quaz0r

Fractal Molossus

Posts: 652

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

« Reply #213 on: August 16, 2016, 04:59:28 PM »

Quote from: kalles

Seems limited to double precision, unless you are using some other datatype

im using extended doubles for all these, i assumed you guys are too?

Quote from: claude

once I get the truncation error stuff for the derivative's series approximation sorted

you are talking about for distance estimation? im using your DE method (without checking the error on it specifically) and it seems fine so far.

Quote from: claude

seems it skips at most 1 period of the reference

all i know is im skipping more than i ever have huh?

skipping most iters at most locations, except when getting close to a minibrot where the number of skipped iters levels off, which is the behavior i am used to anyway

edit: actually i just remembered i had optimized my greater than less than operators on my extended double type to not bother checking the sign, since i was only ever checking positive magnitudes and such.. maybe that was affecting things embarrass

ok after fixing that i can see what you are talking about now, how it gets stuck at the same iter. sad

Quote from: claude

I switched to this alternative which allows much more to be skipped (beyond one period)

better, but still very conservative

so i went ahead and changed both sides of knighty's original comparison to the absolute values to mimic what i was accidentally doing.. i guess its not a proper thing but like i was saying its getting me further than ive been getting with other methods, without causing improper results... might that indicate some potential more proper alteration that will work at least as good?

edit: looks like it is still getting stuck on the same iter after zooming in to deep enough minibrots. maybe with this it is getting stuck after a couple periods worth instead of 1 or whatever..
though im remembering you guys have said that increasing the number of terms gets you more periods' worth to skip, so maybe im just exhausting what 3 terms can do and this would still be pretty good with more terms. i need to decipher claude's math blob so i can try more than 3 terms.. claude, maybe you can throw an abs() around your implementation and see if it does good things?

oh, looks like claude's example code implements arbitrary terms. i'll have better luck deciphering that


« Last Edit: August 16, 2016, 09:58:46 PM by quaz0r »	Logged

knighty

Fractal Iambus

Posts: 819

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

« Reply #214 on: August 16, 2016, 11:27:00 PM »

Ok!
I see now what is hapenning.

Just don't give up the first time the test fails. Only if it fails two times in a row. This is because when the derivative vanishes a some iteration N, it will recover at iteration N+1 unless there are other minibrots that show up nearby. in that case use the coefficients computed just before the first fail (that is at N-1).

That also may explain why sometimes the series approximation doesn't work correctly while it could be done with much higher skipped iterations number: at the first fail of the test, because the magnitude of the derivative is low (over some rendered area in fact), the quality (conditionning) of the series approximation is bad.

If I'm not mistaken, the skipped number of iterations will be roughly a multiple of the period of the minibrot that's near or that contains the reference point. Also, the number of skippable iterations can't be less than the minimal iteration. The more coefficients in the series approximation the closer we get to that limit. The series approximation will tend to approximate the shape of MB shape. I gess the closer we get to the limit (minimal iterations) the less effective the series approximation will be. IIRC, These behaviors are already known. I believe that now we have a good mean to be sure about when to stop skipping.

And thank you very much quazor and claude.


	Logged

quaz0r

Fractal Molossus

Posts: 652

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

« Reply #215 on: August 17, 2016, 02:15:55 AM »

Quote from: knighty

This is because when the derivative vanishes at some iteration N, it will recover at iteration N+1

could one use this as a cheap way to infer the period?


	Logged

stardust4ever

Fractal Bachius

Posts: 513

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

« Reply #216 on: August 17, 2016, 03:03:32 AM »

Quote from: claude on August 16, 2016, 03:38:47 PM

Especially in the higher order Mandelbrot equations, as Kalles Fraktaler alluded to, there can be like 20 terms in the 4th and 5th order equations when you factor in the deltas and expand the expression.

Suppose I'm rendering an image at a zoom depth of e1000. Those delta values are going to be approximately 1e-1000 or smaller in size. The arbitrary precision necessary to calculate a depth of e1000 only needs to be marginally smaller. Maybe the software is using say 1e-1100 for the least significant bit.

Well the full expanded perturbation equation for higher orders is going to have a bunch of terms with deltaX or deltaY squared or even cubed or higher. This means the relative magnitude of these terms is like 1e-2000 or 1e-3000 when you only need 1e-1100 precision to avoid precision errors. So why calculate these sums in the equation when they will just be discarded anyway? Seems like a waste of computational resources.

So unless it somehow causes glitch issues, I would be in favor of discarding any terms with squared or cubed or higher order deltas, unless it specifically causes artifacts or glitching.

EDIT: Just wanted to thank all you programming gurus out there making lightning fast Mandelbrot and related formula deep fractal zoomers. Keep at it! afro


	Logged

Kalles Fraktaler

Fractal Senior

Posts: 1458

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

« Reply #217 on: August 17, 2016, 11:34:26 AM »

Quote from: stardust4ever on August 17, 2016, 03:03:32 AM

The things you describe above is what MM is doing and is why it is often 10 times faster than KF instead of just 4 which comes from SIMD.
However it probably also explains the unsolvable glitches MM suffers from. I've tried that path but eventually gave it up


	Logged

Want to create DEEP Mandelbrot fractals 100 times faster than the commercial programs, for FREE? One hour or one minute? Three months or one day? Try Kalles Fraktaler http://www.chillheimer.de/kallesfraktaler
http://www.facebook.com/kallesfraktaler

knighty

Fractal Iambus

Posts: 819

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

« Reply #218 on: August 17, 2016, 10:28:38 PM »

Forget about my previous post. I was wrong about the "Just don't give up the first time the test fails"... at least. hurt

I've managed to compile claud's code (awesome BTW) and tried the double check, aaaand... it doesn't work! hurt

Now I'm confused. Even when setting the derivative norm to 1 in the test, The skipped number of iterations Grows very slowly with zoom factor (beginning at around 1e-30). The only explanation I have is that the error estimation becomes really too conservative at some point.

More investigation is needed... cheesy


	Logged

quaz0r

Fractal Molossus

Posts: 652

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

« Reply #219 on: August 18, 2016, 03:01:28 AM »

Quote from: knighty

Forget about my previous post. I was wrong

dont give up! there just has to be a way to make this or something similar to this do the right thing cry

Quote from: claude

note this includes some terms twice multiplied in opposite orders, could be implemented by multiplying by 2 instead of repeated calculations

this is one reason i like to see a thing written all the way out, so i can try to visualize the patterns and skip right to implementing some optimized code. speaking of which, i dont suppose one of you could post another such example or two of the form

R_n+1 = |B_n|² + 2*(|z_n|*R_n + |A_n|*|C_n|) + 2*|tmax|*(|A_n|*R_n + |B_n|*|C_n|) + |tmax²|*(|C_n|² + 2*|B_n|*R_n) + 2*|tmax³|*|C_n|*R_n + |tmax⁴|*R_n²

perhaps at say m = 4 or 6 or something. trying to extrapolate from the math thing or the example code of the math thing makes my brain hurt and my eyes glaze over head banging wall


	Logged

hapf

Fractal Lover

Posts: 219

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

« Reply #220 on: August 18, 2016, 11:27:56 AM »

Quote from: knighty on August 16, 2016, 11:27:00 PM

If I'm not mistaken, the skipped number of iterations will be roughly a multiple of the period of the minibrot that's near or that contains the reference point. Also, the number of skippable iterations can't be less than the minimal iteration.

Quote

The more coefficients in the series approximation the closer we get to that limit. The series approximation will tend to approximate the shape of MB shape. I gess the closer we get to the limit (minimal iterations) the less effective the series approximation will be. IIRC, These behaviors are already known. I believe that now we have a good mean to be sure about when to stop skipping. And thank you very much quazor and claude.

Yes, the reference period rule is quite safe when excluding pixels that go corrupt due to rounding issues independent of skipping and when not in the direct neighbourhood of a/the minibrot.


	Logged

knighty

Fractal Iambus

Posts: 819

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

« Reply #221 on: August 18, 2016, 02:08:31 PM »

Quote from: quaz0r on August 18, 2016, 03:01:28 AM

dont give up! there just has to be a way to make this or something similar to this do the right thing cry

I'm not giving up. This is a very interesting and challenging problem. There are a lot of things to learn.

For the formula, I haven't yet had time to check it. You can still use claude's formula for now.

Quote from: hapf on August 18, 2016, 11:27:56 AM

More, not less. If one uses the same skip for all pixels, yes. The question is if a variable skip could do better. I think so but I have not found an efficient and safe way to decide skip for every pixel separately.Yes, the reference period rule is quite safe when excluding pixels that go corrupt due to rounding issues independent of skipping and when not in the direct neighbourhood of a/the minibrot.

Thank you.
I was meaning "same skip for all pixels".


	Logged

quaz0r

Fractal Molossus

Posts: 652

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

« Reply #222 on: August 18, 2016, 04:44:36 PM »

Quote from: hapf

The question is if a variable skip could do better.

when i was experimenting with different stuff a while back i had implemented a system of deciding on an initial iteration as usual, and then for each point going up or down in increments of say 50 iters or whatever, depending on whether the starting point tested good or bad. it seemed to work and performed okay, though it didnt actually solve other issues i was having at the time so i decided to go back to the simpler standard approach.


	Logged

knighty

Fractal Iambus

Posts: 819

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

« Reply #223 on: August 20, 2016, 11:18:44 PM »

There is still hope! grin

Here are the formulas I get. Here, in a_iⁿ and Rⁿ, n is an index not an exponent. In tⁿ, n is indeed an exponent.

We have:
$[Z_{n}] = z_{n} + \sum_{i=1}^{m}{a_{i}^{n} t^{i}} + R^{n} t^{m+1} [E]$
and
$[Z_{n+1}] = z_{n+1} + \sum_{i=1}^{m}{a_{i}^{n+1} t^{i}} + R^{n+1} t^{m+1} [E]$

Then:

$a_{1}^{n+1} = 2 z_{n} a_{1}^{n} + 1$

$a_{k}^{n+1} = 2 \left \{ z_{n} a_{k}^{n} + \sum_{i=1}^{\left \lfloor \frac{k-1}{2} \right \rfloor} {a_{i}^{n} a_{k-i}^{n}}\right \} + \left \{ \left ( a_{\frac{k}{2}}^{n} \right )^{2} \: if\: k\: is\: even \right \}$

Where:

$2\leq k \leq m$

$\left \lfloor k \right \rfloor$ means floor(k)

Now for the truncation error:

$R^{n+1} = \Xi \left \{ \sum_{k=m+1}^{2 m} t^{k-m-1}\left [ \left ( 2 \sum_{i=k-m}^{\left \lfloor \frac{k-1}{2} \right \rfloor} a_i^n a_{k-i}^n \right ) +\left ( \left ( a_{\frac{k}{2}}^n \right )^2 \:if\:k\:even\right )\right ] + 2 R^n[E]\left [ z_n + \sum_{i=1}^{m} a_i^n t^i \right ] + (R^n)^2 t^{m+1}[E]\right \}$

Where $\Xi \left ( p\left ( z \right ) \right )$ is some function that gives the max value (upper bound) for $|p\left ( z \right )|$ over the interval {z | |z|<tmax}. It is computationally expensive to get a precise value of the upper bound. We need some estimation that is not too conservative. Previously, I did this:

$R^{n+1} = \sum_{k=m+1}^{2 m} |t_{max}|^{k-m-1}\left [ \left ( 2 \sum_{i=k-m}^{\left \lfloor \frac{k-1}{2} \right \rfloor} |a_i^n|| a_{k-i}^n| \right ) +\left ( |a_{\frac{k}{2}}^n|^2 \:if\:k\:even\right )\right ] + 2 R^n\left [ |z_n| + \sum_{i=1}^{m} |a_i^n| |t_{max}|^i \right ] + (R^n)^2 |t_{max}|^{m+1}$

By inspecting the values of R while doing experiments thanks to claude's programm, I noticed that it doesn't "blow up" prematurally and it is quite a good estimation of the trucation error. A better way to compute R which is slightly less conservative:

$R^{n+1} = \sum_{k=m+1}^{2 m} |t_{max}|^{k-m-1} \left | \left ( 2 \sum_{i=k-m}^{\left \lfloor \frac{k-1}{2} \right \rfloor} a_i^n a_{k-i}^n \right ) +\left ( (a_{\frac{k}{2}}^n)^2 \:if\:k\:even\right ) \right | + 2 R^n\left [ |z_n| + \sum_{i=1}^{m} |a_i^n| |t_{max}|^i \right ] + (R^n)^2 |t_{max}|^{m+1}$

Sorry... I couldn't make it simplier.


« Last Edit: August 31, 2016, 11:11:01 AM by knighty, Reason: correcting a mistake in the formuas »	Logged

knighty

Fractal Iambus

Posts: 819

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

« Reply #224 on: August 20, 2016, 11:43:21 PM »

Note about claud's code:
To compile it one needs QD library downloadable here: http://crd-legacy.lbl.gov/~dhbailey/mpdist/
On 32bit systems one have to add the code for fixing floating point precision:

Code:

int main(int argc, char **argv)
{
	//from qd_test.cpp
	unsigned int old_cw;
	fpu_fix_start(&old_cw);
	//end from qd_test.cpp

	.......

	//from qd_test.cpp
	fpu_fix_end(&old_cw);
	//End from qd_test.cpp
  return 0;
}

I had a lot of fun playing with it. grin

It happens that the truncation error formula I suggeted gives very good results. The problem comes from the estimation of the lower bound of the absolute value of the derivative: It is toooo conservative! I believe such lower bound is necessary because using only the truncation error is not sufficient.

While varying the number of iterations of the series approximation, one can notice that it usually breaks down suddenly. For example the first picture ( zoom level: 1E-45, m=7, series approx iterations 2808) is correct. The second one ( zoom level: 1E-45, m=7, series approx iterations 2809) with just one more iteration, is very different. Moreover, if one inspects the pictues, the number of "rays" and blobs in the little "wheel" are different.

00002808.jpg (32.91 KB, 640x360 - viewed 337 times.) 00002809.jpg (29.82 KB, 640x360 - viewed 346 times.) m3.cpp.txt (8.02 KB - downloaded 64 times.)
	Logged

Pages: 1 ... 13 14 [15] 16 17 ... 24 Go Down

« previous next »

	Author	Topic: Continued SuperFractalThing: Arbitrary precision mandelbrot set rendering in Java. (Read 50863 times)
		Description:
0 Members and 1 Guest are viewing this topic.

Related Topics
	Subject	Started by	Replies	Views	Last post
	Java applet for exploring the Mandelbrot set Announcements & News	Paton	5	7116	March 26, 2007, 06:03:34 PM by Paton
	What range/precision for fractional escape counts for Mandelbrot/Julia sets? Programming	Duncan C	7	11164	May 01, 2007, 08:23:13 PM by Duncan C
	Java Mandelbrot segment Help & Support	fractalwizz	10	2042	December 29, 2008, 08:01:24 PM by cKleinhuis
	[Java] Double-double library for 128-bit precision. Programming	Zom-B	10	17354	December 20, 2010, 04:03:48 AM by David Makin
	SuperFractalThing: Arbitrary precision mandelbrot set rendering in Java. Announcements & News « 1 2 ... 16 17 »	mrflay	252	102781	August 17, 2016, 11:59:31 PM by cKleinhuis

END OF AN ERA, FRACTALFORUMS.COM IS CONTINUED ON FRACTALFORUMS.ORG

it was a great time but no longer maintainable by c.Kleinhuis contact him for any data retrieval,
thanks and see you perhaps in 10 years again

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

	Welcome, Guest. Please login or register.	April 24, 2024, 09:48:17 PM
		Login with username, password and session length

END OF AN ERA, FRACTALFORUMS.COM IS CONTINUED ON FRACTALFORUMS.ORG

it was a great time but no longer maintainable by c.Kleinhuis contact him for any data retrieval, thanks and see you perhaps in 10 years again

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

it was a great time but no longer maintainable by c.Kleinhuis contact him for any data retrieval,
thanks and see you perhaps in 10 years again