Logo by Sockratease - Contribute your own Logo!

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

this forum will stay online for reference
News: Visit the official fractalforums.com Youtube Channel
 
*
Welcome, Guest. Please login or register. March 29, 2024, 01:20:55 AM


Login with username, password and session length


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


Pages: 1 ... 15 16 [17] 18 19 ... 24   Go Down
  Print  
Share this topic on DiggShare this topic on FacebookShare this topic on GoogleShare this topic on RedditShare this topic on StumbleUponShare this topic on Twitter
Author Topic: *Continued* SuperFractalThing: Arbitrary precision mandelbrot set rendering in Java.  (Read 46963 times)
0 Members and 1 Guest are viewing this topic.
TheRedshiftRider
Fractalist Chemist
Global Moderator
Fractal Iambus
******
Posts: 854



WWW
« Reply #240 on: August 25, 2016, 09:02:18 AM »

http://www.gigapan.com/gigapans/177160
I found another example, when I rendered it I did not know but now I notice it has the bug as well.
Logged

Motivation is like a salt, once it has been dissolved it can react with things it comes into contact with to form something interesting. nerd
Kalles Fraktaler
Fractal Senior
******
Posts: 1458



kallesfraktaler
WWW
« Reply #241 on: August 25, 2016, 04:07:52 PM »

http://www.fractalforums.com/ultra-deep-mandelbrot/lightyears-away/
I have tried to render one of my contest images in 16000x9000. I had low tolerance active. I do not have an image of the glitch.
OK, I found the glitch.
When rendering in 16000x9000 the number of terms is 252, which is exaggerating a lot but I haven't tried to render this big images.
I made some small 1280x760 renders with different number of terms.
The minimum iteration pixel on this location is 313467.
With 50 terms 305825 iterations are skipped, and the render is correctly, as the top cut-out shows.
With 100 terms 313088 iterations are skipped, and the left-pointing tip of the structure becomes fuzzy, as the second cut-out.
With 252 terms 313197 iterations are skipped, and the left-pointing tip becomes distorted.

Maybe KF should have a maximum of terms somewhere between 50 and 100...


* light years.jpg (116.19 KB, 298x602 - viewed 127 times.)
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
quaz0r
Fractal Molossus
**
Posts: 652



« Reply #242 on: August 25, 2016, 07:40:38 PM »

Quote from: kalles
Maybe KF should have a maximum of terms somewhere between 50 and 100

Quote from: hapf
Analysing the behaviour of the series itself did not work out in the end because as the terms go up the contributions are spread around more and more in waves and it was unclear when to stop safely looking at contributions.

kalles it sounds like this is probably what is causing your woes?  since you are testing against points in your program, maybe if you try knighty's formula for testing against points it will work.

i think his formula for only analyzing the series coefficients to determine the skip amount is what there is still a question about, and his formula for testing against points is good to go?
Logged
stardust4ever
Fractal Bachius
*
Posts: 513



« Reply #243 on: August 25, 2016, 09:22:28 PM »

We can play dice roll with the numbers all we want; ultimately it is a game of risk (glitch) versus reward (speed).

It also happens that some of the most visually interesting extremely deep zoom locations are often worst case scenarios for guessing algorithms. evil
Logged
TheRedshiftRider
Fractalist Chemist
Global Moderator
Fractal Iambus
******
Posts: 854



WWW
« Reply #244 on: August 25, 2016, 09:39:41 PM »

OK, I found the glitch.
When rendering in 16000x9000 the number of terms is 252, which is exaggerating a lot but I haven't tried to render this big images.
I made some small 1280x760 renders with different number of terms.
The minimum iteration pixel on this location is 313467.
With 50 terms 305825 iterations are skipped, and the render is correctly, as the top cut-out shows.
With 100 terms 313088 iterations are skipped, and the left-pointing tip of the structure becomes fuzzy, as the second cut-out.
With 252 terms 313197 iterations are skipped, and the left-pointing tip becomes distorted.

Maybe KF should have a maximum of terms somewhere between 50 and 100...
Thank you for having a look at it. Yes I know 16k is large. I even had to decrease the terms to below ten to make it work. But I have not had time to do the complete render.

We can play dice roll with the numbers all we want; ultimately it is a game of risk (glitch) versus reward (speed).

It also happens that some of the most visually interesting extremely deep zoom locations are often worst case scenarios for guessing algorithms. evil
True smiley
Logged

Motivation is like a salt, once it has been dissolved it can react with things it comes into contact with to form something interesting. nerd
knighty
Fractal Iambus
***
Posts: 819


« Reply #245 on: August 25, 2016, 09:42:47 PM »

Sorry for the late reply. Busy @ work.  smiley
And still haven't done any thing for the test.

(...) maybe if you try knighty's formula for testing against points it will work.

i think his formula for only analyzing the series coefficients to determine the skip amount is what there is still a question about, and his formula for testing against points is good to go?
Maybe not. I think It would work better for small number of coefficient. When it is large, the error may stay very small on most of the rendered area and quite big elswhere. The variation of the error goes faster as the number of SA terms is raised. In those cases, cheking on some points may not be sufficient.

The proposed formula (without interval arithmetic) is still useful because the derivative of the SA is important. When the absolute value of that derivative is small, a little error on the SA value may become very large w.r.t. pixel size. I mean if there if an error epsilon in the computation of a function f(x), the error Omega on x will be epsilon/f'(x).
 
For a bullet proof test, the interval arithmetic test is reliable. There is still some work to do in order to finish it even if for now we can use what we have for debugging purposes (it is far less costly than checking the difference between SA and perturbation at each pixel)... Anyway, so far it is promising: I was surprised to see that the estimation of the error is not too big, that is because IA methods are known to be too conservative. Also, even if it is expensive, in general one can skip more iterations with it.

OK, I found the glitch...
grin
I think those case (except maybe the last one) could be easily avoided by not systematically using the pixel at the center as the reference. A lazy approach may be more effective and faster: use the already found references (usually used in glitch correction) as much as possible. Even more lazy: Compute new references only when there are glitches. It is also possible to find (and/or refine) good refence points by using interval arithmetics (again  grin) and/or Newton root finding and it is not that slow.

We can play dice roll with the numbers all we want; ultimately it is a game of risk (glitch) versus reward (speed).

It also happens that some of the most visually interesting extremely deep zoom locations are often worst case scenarios for guessing algorithms. evil
True smiley
Yep!
Logged
quaz0r
Fractal Molossus
**
Posts: 652



« Reply #246 on: August 25, 2016, 11:36:06 PM »

Quote from: knighty
Maybe not.  I think It would work better for small number of coefficient.  The proposed formula (without interval arithmetic) is still useful because the derivative of the SA is important.

indeed, i simply meant within the scope of the "check against a point or handful of points in order to divine how much to skip for all points" approach, your formula should give more of a proper error estimate and ultimately fare better than the stop condition that people have discussed in the past, of simply checking the relative size of the terms.  does that sound right?
Logged
stardust4ever
Fractal Bachius
*
Posts: 513



« Reply #247 on: August 26, 2016, 02:01:53 AM »

"check against a point or handful of points in order to divine how much to skip for all points"
Fractals are divine creatures... angel
« Last Edit: August 29, 2016, 12:17:57 PM by stardust4ever » Logged
Kalles Fraktaler
Fractal Senior
******
Posts: 1458



kallesfraktaler
WWW
« Reply #248 on: August 26, 2016, 04:33:03 PM »

indeed, i simply meant within the scope of the "check against a point or handful of points in order to divine how much to skip for all points" approach, your formula should give more of a proper error estimate and ultimately fare better than the stop condition that people have discussed in the past, of simply checking the relative size of the terms.  does that sound right?
Yes I agree that even though lowering the maximum terms to 50 would solve TheRedShifter's location, there will most probably be other locations that requires even lower number of terms.
And unfortunately I don't think there is a way to validate the correctness of a pixel after the SA-terms is applied to it?
I hope you follow what I meant?
- First, calculate the SA coefficients and the skippable iteration number by checking against a handful of points
- Second, each pixel starts by applying the coefficients and start from the skippable iteration number - is there any validation possible here?
If it is, one could mark these pixels as glitches and redo them with a closer reference, in the same way as Pauldelbrot's glitchdetection...  praying
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


« Reply #249 on: August 29, 2016, 10:10:27 AM »

Ok!

After trying a lot of alternatives, I came back to the simplest one, the one I was thinking would not work well but... It worked!
In the test:

R * |tmax|m+1 <= |SA'(tmax)| * |dt|

The formula proposed for the lower bound of |SA'(tmax)|:

\left |a_1 \right | - \sum_{i=2}^{m} i \left |a_i \right | \left |t_max \right |^{i-1}
 
works only for one period of the reference point. That is because a1 becomes very small.

The formula:

max_{k}(k \left |a_{k} \right | \left |t_{max} \right |^{k-1}) - \sum_{i=1 | i\neq k}^{m} i \left |a_{i} \right | \left |t_{max} \right |^{i-1}

(that is, we subtract from the max term the remaining ones.)

Solves the problem.

It is still a crude estimation. It shouldn't fail but it is somewhat conservative. Some times it gives almost optimal result, some other times... less optimal. Nothing dramatic though. For example, the location given by claude in m.cpp, is really difficult: at 1E-47, the test (even the per pixel test) fails way before the errors become visible.

Of course, when the test fails, it is possible to repeat it on smaller areas. The simplest is to redo the test with smaller values of tmax to get the area (around the reference point) where the SA is still accurate.

This is not the end of the story. Using the derivative of the SA is actually just an approximation. The full test formula is:

\left | K t^{m+1} \right | \leq \left | SA(t+dt) - SA(t)\right |

where dt corresponds to the circle of radius |dt|.

So far, the test uses a Taylor expansion of (SA(t+dt) - SA(t)) of the first order. Higher orders are also possible. It is maybe even possible to use the above formula as it is. Anyway, that would be too complicated and with little benefit IMHO.

* m14.cpp.txt (9.26 KB - downloaded 44 times.)
Logged
claude
Fractal Bachius
*
Posts: 563



WWW
« Reply #250 on: August 29, 2016, 08:26:30 PM »

After trying a lot of alternatives, I came back to the simplest one, the one I was thinking would not work well but... It worked!
...
(that is, we subtract from the max term the remaining ones.)

Awesome!

I did a quick test, your refined method described in this post skips 3544 iterations with no apparent ill effects.  The period here at this location is 927.  So significantly more than one period, nice.

Code:
./a.out --width 1920 --height 1080 --maxiters 65536  --precision 100 --output out.ppm \
--re -1.94021202906904108793666462798106635116194041886835880862863e+00 \
--im 1.47021750196972546090052860958643781234133289155702935853549e-04 \
--radius 1.4349296274686127e-42

Code attached, changed to use Boost Multiprecision (based on MPFR) for high precision (shouldn't be too hard to revert it back to using QD if necessary), with rudimentary command line argument parsing.  Also renders with exterior distance estimation - no check on the validity of the series approximation for the derivative is performed, just fingers crossed at this point...  I guess I should add my glitch correction method to the example code to make it almost complete (the final step would be interior distance estimation).

* mandelbrot-series-approximation-v2.cpp.txt (9.48 KB - downloaded 41 times.)

* mandelbrot-series-approximation-v2.jpg (229.56 KB, 960x540 - viewed 100 times.)
Logged
claude
Fractal Bachius
*
Posts: 563



WWW
« Reply #251 on: August 29, 2016, 11:20:15 PM »

added my own method of recursive glitch solving to the code, hopefully it is useful to see a simple implementation without multithreading optimisations getting in the way of understanding.

* mandelbrot-series-approximation-v3.cpp.txt (11.51 KB - downloaded 50 times.)

* mandelbrot-series-approximation-v3.jpg (225.09 KB, 960x540 - viewed 109 times.)
Logged
quaz0r
Fractal Molossus
**
Posts: 652



« Reply #252 on: August 30, 2016, 02:16:20 AM »

Quote from: knighty
The formula proposed for the lower bound of  |SA'(tmax)|  works only for one period of the reference point.  That is because a1 becomes very small.
Subtracting from the max term the remaining ones solves the problem.  Some times it gives almost optimal result, some other times... less optimal.

good work!  a few thoughts:

are we in fact saying that if the value for the lower bound of  |SA'(tmax)|  becomes negative, this Always represents an inadequate analysis of the series?  If yes, might we take your idea of subtracting from the largest term the remaining terms one step further and say, subtract from the sum of one or more of the largest terms the remaining terms, such that the result is a positive value?
Logged
knighty
Fractal Iambus
***
Posts: 819


« Reply #253 on: August 30, 2016, 05:48:36 PM »

are we in fact saying that if the value for the lower bound of  |SA'(tmax)|  becomes negative, this Always represents an inadequate analysis of the series?  If yes, might we take your idea of subtracting from the largest term the remaining terms one step further and say, subtract from the sum of one or more of the largest terms the remaining terms, such that the result is a positive value?

No, not always. The lower bound formula is crude, very conservative. If you take a polynomial p(z) and set the magnitude of z to a constant value, you get something like a spirograph curve. Getting the smallest distance from this curve to the origin requires solving a polynomial equation. That is why the lower bound is useful: it is much cheaper. It works very well in general but unfortunately in the case of the location given by claude, it is too conservative and makes the test stop around 3544 while one can go to 4800 or 5000 (depending on m). IMHO, the lower bound and/or using the 1st derivative only, is inadequate in that case. A "higher order test" is needed. Which means more work/ideas needed.  smiley

added my own method of recursive glitch solving to the code, hopefully it is useful to see a simple implementation without multithreading optimisations getting in the way of understanding.

Indeed! It wouldn't have been possible to me to do any test without your code. Thank you very much!

Logged
quaz0r
Fractal Molossus
**
Posts: 652



« Reply #254 on: August 31, 2016, 01:11:58 AM »

R^{n+1} = \sum_{k=m+1}^{2 m} |t_{max}|^{k-m-1} \left | \left ( 2 \sum_{i=k-m}^{2 m} 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}

just curious, earlier it was written as |tmaxn|, but according to this it seems to be |tmax|n.  should these be equivalent or should it be one or the other?

also,

2 \sum_{i=k-m}^{2 m} a_i^n a_{k-i}^n

this seems weird to me... for instance at m=3 and k=4, this seems to give 2(a1a3 + a2a2 + a3a1 + a4a0 + a5a-1 + a6a-2).  should that 2m instead be m ?
« Last Edit: August 31, 2016, 03:11:57 AM by quaz0r » Logged
Pages: 1 ... 15 16 [17] 18 19 ... 24   Go Down
  Print  
 
Jump to:  

Related Topics
Subject Started by Replies Views Last post
Java applet for exploring the Mandelbrot set Announcements & News Paton 5 6600 Last post March 26, 2007, 06:03:34 PM
by Paton
What range/precision for fractional escape counts for Mandelbrot/Julia sets? Programming Duncan C 7 9923 Last post May 01, 2007, 08:23:13 PM
by Duncan C
Java Mandelbrot segment Help & Support fractalwizz 10 1895 Last post December 29, 2008, 08:01:24 PM
by cKleinhuis
[Java] Double-double library for 128-bit precision. Programming Zom-B 10 16966 Last post 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 98960 Last post August 17, 2016, 11:59:31 PM
by cKleinhuis

Powered by MySQL Powered by PHP Powered by SMF 1.1.21 | SMF © 2015, Simple Machines

Valid XHTML 1.0! Valid CSS! Dilber MC Theme by HarzeM
Page created in 0.152 seconds with 25 queries. (Pretty URLs adds 0.008s, 2q)