Logo by Pauldelbrot - 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: Follow us on Twitter
 
*
Welcome, Guest. Please login or register. March 29, 2024, 10:49:32 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]   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: Ultra Fractal double precision  (Read 3358 times)
Description: TIA artifacts with big bailout value
0 Members and 1 Guest are viewing this topic.
cabrif
Guest
« on: January 19, 2012, 08:30:47 PM »

Hi everyone,
I am trying to write a little program to draw fractals in C, and I am using Ultra Fractal as an example.
I implemented triangle inequality average coloring (TIA), but my results differ a bit from UltraFractal. I understand that to obtain a good image with TIA, one has to chose a big bailout radius, (like 1E20), but with my program I get artifacts for such big values.

The weird thing is, my program uses double precision floats, like Ultra Fractal by default (I checked in the "statistics" panel that the type used is indeed double), so I just don't understand why Ultra Fractal doesn't show any artifacts.

To illustrate what I am talking about, below is what I obtain using TIA with my program, for a bailout value of 1E20 (this is the classic mandelbrot set).
First with no interpolation :
http://dl.free.fr/k4lvSLyZG
With linear interpolation (like Ultra Fractal) :
http://dl.free.fr/nukvlbBle
And here is the result with Ultra Fractal (gradients differ, but apart from that it should be the same) :
http://dl.free.fr/ntgp4MLS5
Note that the artifacts do also appear with Ultra Fractal for a bigger bailout radius, like 1E50 (unless you increase the precision, so that Ultra Fractal switches to Arbitrary precision floats) :
http://dl.free.fr/h3eWZMiAI

Also, if I reduce the bailout value to something 1E7 in my program, the artifacts disappear.
First with no interpolation (see ? no artifacts) :
http://dl.free.fr/bXmTqM21V
Then with linear interpolation (like UltraFractal) :
http://dl.free.fr/rjSZElo1F

Now I can explain why MY program shows such artifacts, but I can't explain why Ultra Fractal does NOT. Here is the explanation :
At one point during the TIA computation, you have to compute something like ||z-c|-|c|| (where c is denoted as #pixel in Ultra Fractal scripts, for those who now). Now if |z| is much much bigger than |c|, then |z-c| ~= |z| : in particular, if your float is not precise enough, you will have |z-c|=|c| (which leads to those artifacts). You also experience the same thing when you compute z_{n+1} = z_n^2 + c : you may have z_n^2+c = z_n^2 because of lack of precision.

For example : In C, mantissa for double precision numbers is 52 bits, so about 14-15 decimal digits. So if |z|>1E16 (which happens when bailout radius is > 1E20), and 0<|c|<10 (which is the case for the given example), then double precision numbers are not precise enough to evaluate |z-c| (we will actually have |z-c|=|z|).
Try initializing a double with 2E20+3E-1, and print it, you will get 2E20 (because 2000000000000000000003 does not fit in 52 bits).

Anyone has any idea how Ultra Fractal can compute things like that with only double ? Because that just seems impossible..

Edit : found this in the Ultra Fractal 8 manual on triangle inequality average :
"Use very large bail-out values for good results. The default value 1e20 (a 1 with 20 zeroes) is a good
starting point. The Mandelbrot (Built-in) formula cannot handle such large values, so use the non-
built-in Mandelbrot instead."
I checked, and indeed, with the Mandelbrot (Built-in) formula, the artifacts appear at a bailout radius of 1e12 or something (and with less, the result is not even smooth, as though there was no linear interpolation), like for my program which uses doubles. So apparently, the problem does not come from my implementation, and the trick for Ultra Fractal is probably that for non builtin formulas it does not use double precision numbers (even if it says so), but something else, maybe double double or quad precision numbers smiley. What do you think ?
« Last Edit: January 19, 2012, 10:42:04 PM by cabrif, Reason: Information from Uf5 manual » Logged
David Makin
Global Moderator
Fractal Senior
******
Posts: 2286



Makin' Magic Fractals
WWW
« Reply #1 on: January 20, 2012, 03:57:00 AM »

Do *not* go through the colouring loop calculation *after* bailout and the artifacts should go away.

i.e in UF in all main formulas *except* the in-built ones the loop: section of colouring formulas is only called after the main formula loop: section *if* bailout did not occur - so when bailout does occur the only part of the colouring formula processed after the main formula loop: section is the final: section of the colouring formula.

(if the above fixes your problem then I think the reason for your artifacts is actually overflow)
« Last Edit: January 20, 2012, 05:02:01 AM 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
cabrif
Guest
« Reply #2 on: January 20, 2012, 05:29:11 PM »

I don't get it : are you saying I should skip the coloring calculations if bailout occured ?
But bailout always occurs (except when maximum number of iterations is reached, that is to say inside the fractal. but anyway, only points outside the fractal are colored), doesn't it ? Isn't it the condition to exit the calculation loop (well, that and the maximum number of iterations) ?
i.e.
while (iteration_number <= max_iteration && |z| < bailout_value)
Could you clarify please ?
Logged
David Makin
Global Moderator
Fractal Senior
******
Posts: 2286



Makin' Magic Fractals
WWW
« Reply #3 on: January 20, 2012, 07:57:06 PM »

No.

If you look at the UF code there is some calculation in the loop: section that is performed per iteration and in the final; section there is the final section which is performed after bailout.
On the iteration when bailout occurs *the loop: code* is *not* executed in UF precisely because *after* z is found to be too large it could actually be :INF: or :NAN:

From the standard UF TIA formula:

loop:
  sum2 = sum
  IF (!first)
    az2 = cabs(#z - #pixel)
    lowbound = abs(az2 - ac)
    sum = sum + ((cabs(#z) - lowbound) / (az2+ac - lowbound))
  ELSE
    first = false
  ENDIF
final:
  sum = sum / (#numiter)
  sum2 = sum2 / (#numiter-1)
  f = il*lp - il*log(log(cabs(#z)))
  #index = sum2 + (sum-sum2) * (f+1)  


The loop: above is normally executed on each iteration after the main formula loop: code *but* if at the end of the main formula loop: code bailout occurs then the above colouring loop: code is not executed *on that final iteration* and program flow continues directly to the colouring final: section.

I hope that's now clear wink


For a clearer description of UF's execution sequence see the UF help (in program or online) "Tips->Execution sequence".

« Last Edit: January 20, 2012, 08:05:07 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
cabrif
Guest
« Reply #4 on: January 20, 2012, 09:00:17 PM »

Just to be sure In understood correctly :
You are saying that the last iteration (where bailout occurs) is ignored for TIA coloring.
If that's what you're saying, then it's exactly what I do in my program.

No, I'm quite convinced these artifacts come from loss of precision in floating point operations, because :
1) My calculations show so. If you have a bailout of 1e20 and your floating point precision is 14-15 decimal digit, you will experience loss of precision (even if you skip the last iteration for coloring).
2) Experience shows so : those artifacts appear both with my program and with Uf5 (with built-in mandelbrot) for a bailout of 1e20. They also appear with Uf5 with *non* built-in mandelbrot for a bigger bailout (like 1e50)

The only mystery is : why do those artifacts appear with Uf5 for a bailout of ~ 1e15 with built-in mandelbrot, but with *non* built-in mandelbrot for a bailout >= 1e50 ?

Edit :
Quote
*but* if at the end of the main formula loop: code bailout occurs
Why do you say "if" ? Bailout *always *occurs at the last iteration (for points outside fractal) : it is the condition to break the loop.
« Last Edit: January 20, 2012, 09:04:49 PM by cabrif » Logged
David Makin
Global Moderator
Fractal Senior
******
Posts: 2286



Makin' Magic Fractals
WWW
« Reply #5 on: January 20, 2012, 09:19:56 PM »

I have no idea why it works in UF and not in your code - assuming you are using double and not float - I implemented it in my own software for 32-bit DOS in 2000 exactly as in UF and it performed/performs exactly as in UF.

Here's the main UF executon including both main formula and colouring:

for each transformation
  execute global section of transformation
execute global section of fractal formula
execute global section of inside coloring algorithm
execute global section of outside coloring algorithm

Then, for each pixel, the following calculations are performed:

for each transformation
  #solid = false
  execute transform section of transformation
  if #solid == true
    stop and give pixel the solid mapping color
endfor
execute init section of fractal formula
execute init section of inside coloring algorithm (if it exists)
execute init section of outside coloring algorithm (if it exists)
int iter = 0
repeat
  execute loop section of fractal formula
  bool b = the expression in the bailout section of the fractal formula
  if b == true
    ; not yet bailed out
    execute loop section of inside coloring algorithm (if it exists)
    execute loop section of outside coloring algorithm (if it exists)
  endif
  iter = iter + 1
until (b == false) || (iter == #maxiter)
#numiter = iter
if #numiter == #maxiter
  ; pixel is inside
  execute final section of the inside coloring algorithm
else
  ; pixel is outside
  execute final section of the outside coloring algorithm
endif
color the pixel
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



Makin' Magic Fractals
WWW
« Reply #6 on: January 20, 2012, 09:28:56 PM »


The only mystery is : why do those artifacts appear with Uf5 for a bailout of ~ 1e15 with built-in mandelbrot, but with *non* built-in mandelbrot for a bailout >= 1e50 ?

Because the built-in Mandelbrot (and Julia) are essentially historical redundancies going back to the early days of UF - and in fact Fractint for that matter - the z value is one iteration off as compared to the non-built-in version i.e. when executing the colouring code (loop or final or both) the z value is one iteration further on than normal.
Logged

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

http://www.fractalgallery.co.uk/
"Makin' Magic Music" on Jango
cabrif
Guest
« Reply #7 on: January 20, 2012, 09:34:54 PM »

But my program works just like Ultrafractal with built-in Mandelbrot. I get the same result (see the image files I gave in the first post), with the same bailout radius smiley.
The weird thing is that in Ultra fractal :
- with built-in mandelbrot, those artifacts appear for a quite small bailout radius (like my program)
- with *non* built-in mandelbrot, they appear *too* but for a much bigger bailout radius (try 1e50)

The only mystery is : why do those artifacts appear with Uf5 for a bailout of ~ 1e15 with built-in mandelbrot, but with *non* built-in mandelbrot for a bailout >= 1e50 ?
Because the built-in Mandelbrot (and Julia) are essentially historical redundancies going back to the early days of UF - and in fact Fractint for that matter - the z value is one iteration off as compared to the non-built-in version i.e. when executing the colouring code (loop or final or both) the z value is one iteration further on than normal.
To me, a difference of one iteration does not justify such a difference on acceptable bailout values.
Do you think it is possible that for non built-in formulas, Uf5 uses something more precise that simple C doubles ?

« Last Edit: January 20, 2012, 09:37:03 PM by cabrif » Logged
David Makin
Global Moderator
Fractal Senior
******
Posts: 2286



Makin' Magic Fractals
WWW
« Reply #8 on: January 20, 2012, 09:43:30 PM »

But my program works just like Ultrafractal with built-in Mandelbrot. I get the same result (see the image files I gave in the first post), with the same bailout radius smiley.
The weird thing is that in Ultra fractal :
- with built-in mandelbrot, those artifacts appear for a quite small bailout radius (like my program)
- with *non* built-in mandelbrot, they appear *too* but for a much bigger bailout radius (try 1e50)

The only mystery is : why do those artifacts appear with Uf5 for a bailout of ~ 1e15 with built-in mandelbrot, but with *non* built-in mandelbrot for a bailout >= 1e50 ?
Because the built-in Mandelbrot (and Julia) are essentially historical redundancies going back to the early days of UF - and in fact Fractint for that matter - the z value is one iteration off as compared to the non-built-in version i.e. when executing the colouring code (loop or final or both) the z value is one iteration further on than normal.
To me, a difference of one iteration does not justify such a difference on acceptable bailout values.
Do you think it is possible that for non built-in formulas, Uf5 uses something more precise that simple C doubles ?



No - because I can turn the "use extra precision" in the options/preferences to "never" and it makes no difference whatsoever.

Under further investigation (since I don't normally ever use the in-built formulas I found that for correct rendering using the built-in formulas if you use a bailout magnitude of m in the main formula then the correct bailout value to give the TIA colouring is m^2 e.g. in UF using the in-built formula try 1e17 for the formula and 1e34 for the TIA colouring.

You are probably correct that when using say 1e40 for both bailouts using the normal formula or 1e20 and 1e40 for the built-in and the TIA then the errors are due to lack of resolution in the mantissa rather than the exponent as I was theorising....
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



Makin' Magic Fractals
WWW
« Reply #9 on: January 20, 2012, 10:03:08 PM »

Also if you're used to:

|z| being used strictly to mean the magnitude of z as in formal maths then you need to be aware that UF (and most other fractal siftware) actually interpets |z| as x*x+y*y rather than sqrt(x*x+y*y) which would be an alternative explanation as to why your bailout values when errors begin do not match those in UF.

Of course x^2+y^2 (i.e, magnitude^2) is used for the bailout testing as getting the actual magnitude involves an unnecessary and slow sqrt function call.
Logged

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

http://www.fractalgallery.co.uk/
"Makin' Magic Music" on Jango
cabrif
Guest
« Reply #10 on: January 20, 2012, 11:01:59 PM »

Ah ! There it is ! You have the explanation smiley.
It seems that :
bailout(my program) <=> bailout^2(Ultra fractal built-in mandelbrot)
and
bailout(my program) <=> bailout^4(Ultra fractal *non* built-in mandelbrot)

This can be explained by the two following remarks you made :
|z| being used strictly to mean the magnitude of z as in formal maths then you need to be aware that UF (and most other fractal siftware) actually interpets |z| as x*x+y*y rather than sqrt(x*x+y*y)
I did not know that ! While ultra fractal does check that x*x+y*y<bailout, my program check x*x+y*y<bailout^2 (of course, I don't compute the square root at each iteration, I just pre-compute bailout^2 and then compare if with x*x+y*y).

Then, you were right about the last iteration : after re-reading my code, I found out that I was doing the TIA even for the last iteration. For TIA calculation, there is a difference of one iteration between my program and ultra fractal, and I was wrong saying that this would not make a big difference on bailout value. Indeed |z| doubles (approximately) after each iteration (for classic mandelbrot).

If I make these two modifications in my code (checking x*x+y*y<bailout and skipping calculation for last iteration), I obtain the same thing as Ultra Fractal : artifacts appear for bailout=1E31.
Anyway I prefer keeping my code as it is, I think it makes more sense :
bailout value is compared to |z| (mathematical definition), and I don't skip the last iteration for TIA calculation (why not use the informations of last iteration if I computed it ?).
« Last Edit: January 20, 2012, 11:08:00 PM by cabrif » Logged
David Makin
Global Moderator
Fractal Senior
******
Posts: 2286



Makin' Magic Fractals
WWW
« Reply #11 on: January 20, 2012, 11:48:35 PM »

smiley actually the magntude *squares* - its exponent doubles wink

One reason not use use z from *after* bailout in some calculations is as I said i.e. the fact that if the bailout is large than after the bailout iteration it's possible that the value may have overflowed or will overflow if used in colouring calculations (whereas we know the penultimate value is definitely of magnitude less than the associated bailout.
Other than that I'm not entirely sure wink

In fact my class colourings such as Smooth Orbit Traps in mmf.ulb I do give users the option of having the colouring loop process the fina iteration after bailout - and of course this results in similar restriction changes to the max possible bailout as with using the TIA colouring.
« Last Edit: January 21, 2012, 12:04:56 AM 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
Pages: [1]   Go Down
  Print  
 
Jump to:  

Related Topics
Subject Started by Replies Views Last post
[Java] Double-double library for 128-bit precision. Programming Zom-B 10 16970 Last post December 20, 2010, 04:03:48 AM
by David Makin
Julia set flower, at the limit of double precision Images Showcase (Rate My Fractal) Duncan C 1 2028 Last post January 11, 2010, 12:59:55 PM
by Nahee_Enterprises
Is there any way to get double precision camera data? Fragmentarium laser blaster 1 2699 Last post April 21, 2013, 09:56:09 PM
by Syntopia
End Of Double Precision Gestaltlupe Gallery trafassel 1 1523 Last post November 12, 2013, 04:50:56 PM
by eiffie
Playing Double Precision Mandelball Mandelbulber Gallery mclarekin 0 1947 Last post July 02, 2015, 01:28:22 PM
by mclarekin

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.31 seconds with 24 queries. (Pretty URLs adds 0.012s, 2q)