Logo by Trifox - Contribute your own Logo!
News: Check out the originating "3d Mandelbulb" thread here
 
*
Welcome, Guest. Please login or register. June 25, 2017, 05:44:29 AM


Login with username, password and session length



Pages: 1 ... 21 22 [23]   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 12064 times)
0 Members and 1 Guest are viewing this topic.
knighty
Fractal Iambus
***
Posts: 815


« Reply #330 on: September 24, 2016, 06:52:14 PM »

did you write the formula right?  if we subtract an amount <Quoted Image Removed> from pmax, the test bails sooner rather than later.  also the test seems to bail rather early in general?

No! I did a mistake again.  embarrass
It must be : 2-(pmax-s)
I'll correct the formula.

is it a coincidence that the number of terms it appears we can safely use seems to also roughly correspond to the number of bits of mantissa precision?  or could we use that as a general rule of thumb?  i guess you are saying the truncation error computation can fall apart with more terms, but it seems the calculation of the coefficients themselves can also fall apart, ie, light years away location being fuzzy.
I don't know if there is any coincidence.
The rounding errors in the computation of the tuncation are not important AFAIK. The right way to compute the truncation is by using a rounding to infinity. I've tried that and the difference is small. This is certainly because we are adding positive values which don't cause cancellation. In the other hand, the coefficients may suffer from cancellation, especially the last ones. The more terms to add/subtract, the more rounding and cancellation risks. the number of iterations also have a big impact on the rounding errors. (The rounding error at iteration n on the coefficient ai is roughly O(i*n) or maybe more)
As you pointed out, maybe using kahan summation would reduce the problem. Anyway, in general higher order polynomials having bad conditionning, I think there is no benefit in using SA with m > 64.
Logged
claude
Fractal Phenom
******
Posts: 479



WWW
« Reply #331 on: September 26, 2016, 07:58:37 PM »

The test should be:
(tex)R \left | t_{max} \right |^{m+1} \leq 2^{-(p_{max} - s)} \sum_{i=1}^{m}\left | a_i \right | \left | t_{max} \right |^m(/tex)
Where:
  pmax is the number of bits in the mantissa (64 for long double)
  s is the (misterious) number of bits of accuracy that could be loosed without causing too much errors. This depends a lot on the location. it can go from 0 to
    something like 20 or 30. Better set it to 0.

I implemented it (attached) as "--stopping knighty2" with "--accuracy 24" to have 2-24 as multiplier on the right hand side (series approximation accurate to 24 bits, makes more sense to me then saying how many bits should be deducted from the precision of the type).  Here are some data:

location 1:
orderknightyquaz0rknighty2 24knighty2 8
163298329732163298
323298337932983380
location 2 "light years away":
orderknightyquaz0rknighty2 24knighty2 8
32300359298493300359308258
64300359303375305241311275

With knighty2, even at --accuracy 8 only a few pixels are different from --accuracy 24 by a few grey-levels, imperceptible to the naked eye.

* mandelbrot-series-approximation-v8.cpp.txt (27.27 KB - downloaded 24 times.)
Logged
quaz0r
Fractal Molossus
**
Posts: 651



« Reply #332 on: September 26, 2016, 10:21:43 PM »

claude i wonder if your test code is still underflowing or something?  at 2-8 at location 2 i get 313084 with 32 terms, and 313193 with 64 terms.

i have noted how at this location i cant skip any more (than 313083) with 64 terms than with 32.  do you guys have the same experience?  this seems maybe kind of weird, as the resulting glitchiness with 64 terms isnt the same as the noisy areas that appear with yet more terms, with the noisy areas seeming more like what you would expect from precision/cancellation errors.  but if the weird render i get skipping more than 313083 with 64 terms is in fact also the result of precision errors then i guess it makes sense.

at 2-16 at this location i get 313084 with 64 terms the same as i do with 32, which is what needs to happen to get a correct render (rolling back by 1).  it would be nice if one could predict what the multiplier needs to be in examples like this, though i guess here if the problem is simply a precision/cancellation sort of problem, maybe there is no correlation to be made.

also i was a little disappointed that it seems using this multiplier still cant get us away from the overskipping by 1, requiring the additional rollback logic.  testing at location 1 for instance with 8 terms, at 2-17 i skip 3216 which requires rolling back by 1, and at 2-18 i skip 2781, a lot less than the max possible.  though the gap does seem to narrow quite a bit with more terms.

in fact it appears that when the multiplier is sufficient to change the stopping point by very much, the result seems close to a shifting down of the stopping point by 1 chunk/interval/whatever.  ie, at 2-17, 8 terms stops at 3216, 16 at 3294, 32 at 3356, and 64 at 3380.  at 2-18, 8 terms stops at 2781, 16 at 3216, 32 at 3298, and 64 at 3380.
« Last Edit: September 26, 2016, 10:43:55 PM by quaz0r » Logged
claude
Fractal Phenom
******
Posts: 479



WWW
« Reply #333 on: October 04, 2016, 01:13:34 AM »

claude i wonder if your test code is still underflowing or something?  at 2-8 at location 2 i get 313084 with 32 terms, and 313193 with 64 terms.

Pretty sure it isn't underflowing (now uses "edouble" which is a double with a separate long exponent, could be that there are bugs in that though).

Maybe I'm calculating R in a different way to you?  I think knighty posted a couple of different versions of that part of the algorithm.  Plus there was the cartoon, and your version of the equation.  Here's the relevant snippet from my code, where a[0] is z and a[m + 1] is R:

Code:
   // calculate truncation error
    {
      // knighty's second estimate
      R_lo sum(0);
      R_lo tmaxn(1);
      for (N k = m + 1; k <= 2 * m; ++k)
      {
        C_lo sum2(0);
        for (N j = k - m; j <= (k - 1) / 2; ++j)
          sum2 += a[j] * a[k - j];
        sum2 *= R_lo(2);
        if (! (k & 1)) // if k is even
          sum2 += a[k / 2] * a[k / 2];
        sum += abs(sum2) * tmaxn;
        tmaxn *= tmax;
      }
      tmaxn = R_lo(1);
      R_lo sum2(0);
      for (N j = 0; j <= m; ++j)
      {
        sum2 += abs(a[j]) * tmaxn;
        tmaxn *= tmax;
      }
      sum += 2 * abs(a[m + 1]) * sum2;
      sum += 2 * abs(a[m + 1]) * abs(a[m + 1]) * tmaxn;
      a_next[m + 1] = C_lo(sum);
    }

UPDATE: I tried with your formulation from this post with identical results to the code above  huh?
http://www.fractalforums.com/announcements-and-news/*continued*-superfractalthing-arbitrary-precision-mandelbrot-set-rendering-in-ja/msg95838/#msg95838

So still searching for the difference.  Hard for me to tell without seeing your code where my code is different, you at least have both sets of code and can compare.

Quote
also i was a little disappointed that it seems using this multiplier still cant get us away from the overskipping by 1, requiring the additional rollback logic.

By the nature of the test ("is this set of coefficients good or bad?"), I think rolling back from the first "these are bad" to the last known "these are good" coefficients is the only way it can work.  Or is there even more overskipping by 1 beyond that?
« Last Edit: October 04, 2016, 01:57:15 AM by claude, Reason: link » Logged
quaz0r
Fractal Molossus
**
Posts: 651



« Reply #334 on: October 04, 2016, 02:47:30 AM »

eh, i dont know what was up with the cartoon really...also i think they used a version of knighty's equation to make the cartoon before he fixed some of his copy paste mistakes..

the way i had my series stuff written originally was to keep the last iteration of stuff in memory, do the next iteration, do the test condition, if it passes put the new stuff in memory and loop, if it fails stop and use the last good set of stuff in memory.  i was in fact doing the obvious thing in other words.  my experience of knighty's truncation error stuff is that when the test condition fails, the previous iteration is not good; it is in fact the iteration before that which is good, hence my complaining about overskipping by 1.

this is if it goes the full distance of course.  with the addition of the pmax multiplier or whatever, this will cause it to stop sooner sometimes, so you wouldnt experience the overskipping in that case.

this is just my experience with my own code.. its always possible im doing something different or made a mistake somewhere or something.

Quote from: claude
Hard for me to tell without seeing your code where my code is different, you at least have both sets of code and can compare.

well, my endeavor is to make a relatively complete program, unto itself at least, and my personal preference is to reach a certain degree of completeness before posting it.  i'll post my code eventually, not that i presume anyone to care what im doing, but i am a staunch user and advocate of open source   smiley
« Last Edit: October 04, 2016, 03:03:41 AM by quaz0r » Logged
skychurch
Alien
***
Posts: 20



« Reply #335 on: January 20, 2017, 01:47:41 AM »

A bit off current topic I know. But has anyone developed a heuristic to optimise SA bailout and number of terms to use in the SA approximation?
Logged
hapf
Fractal Lover
**
Posts: 215


« Reply #336 on: January 20, 2017, 09:43:42 PM »

A bit off current topic I know. But has anyone developed a heuristic to optimise SA bailout and number of terms to use in the SA approximation?
As a rule of thumb every doubling of coefficients is good for an additional x skips with x = period of reference upto getting close to the minimal iteration
in the image. If minimal iteration < period of reference...  hm...  grin
Logged
hapf
Fractal Lover
**
Posts: 215


« Reply #337 on: January 20, 2017, 09:52:09 PM »

I don't know if this is old news but the perturbation approach and series approximation break down the more the closer one gets to the border of the main body or a minibrot copy. First numerically (as in objective errors compared to correct arbitrary precision numbers) and then visually. The reason is that references are good for fewer and fewer pixels till they support only themselves at which point we are back at full arbitrary precision for every pixel. And the reason for this is that orbiting behaviour from pixel to pixel gets different enough that the deltas quickly run out of hardware bits and rounding errors take over way too early for correct results. Fortunately there are enough other places where the method works very well and allows spectacular results otherwise not obtainable with "normal" hardware in a reasonable time.
Logged
quaz0r
Fractal Molossus
**
Posts: 651



« Reply #338 on: January 21, 2017, 08:30:17 AM »

if only there were a formula with just multiplication and no addition  evil
Logged
hapf
Fractal Lover
**
Posts: 215


« Reply #339 on: January 21, 2017, 01:21:18 PM »

if only there were a formula with just multiplication and no addition  evil
Then it either goes to infinity or zero. Bye bye fractal structures.
Logged
skychurch
Alien
***
Posts: 20



« Reply #340 on: January 21, 2017, 08:16:30 PM »

I don't know if this is old news but the perturbation approach and series approximation break down the more the closer one gets to the border of the main body or a minibrot copy.

Yes, that makes sense. Thanks for the insight. So it seems we can only tame the beast in it's less chaotic regions.
Logged
hapf
Fractal Lover
**
Posts: 215


« Reply #341 on: January 27, 2017, 01:07:08 PM »

Yes, that makes sense. Thanks for the insight. So it seems we can only tame the beast in it's less chaotic regions.
Well, there still are ways to speed up things even in dense regions. The perturbation and delta approach are not limited to
hardware bits... Of course  the hardware bits offer the big speed up factors, but any speed up compared to full arbitrary precision
for each pixel is welcome.
Logged
skychurch
Alien
***
Posts: 20



« Reply #342 on: January 28, 2017, 06:02:15 PM »

Well, there still are ways to speed up things even in dense regions. The perturbation and delta approach are not limited to
hardware bits... Of course  the hardware bits offer the big speed up factors, but any speed up compared to full arbitrary precision
for each pixel is welcome.

Do you think it's worth implementing a 128 bit mantissa for the SA calcs as well as a wide exponent?
Logged
hapf
Fractal Lover
**
Posts: 215


« Reply #343 on: January 29, 2017, 12:10:46 PM »

Do you think it's worth implementing a 128 bit mantissa for the SA calcs as well as a wide exponent?
Depending on where you want to go, yes.
Logged
skychurch
Alien
***
Posts: 20



« Reply #344 on: January 29, 2017, 09:03:46 PM »

Depending on where you want to go, yes.
Cheers. I'd better get to work.  cheesy
Logged
Pages: 1 ... 21 22 [23]   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 2686 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 3226 Last post May 01, 2007, 08:23:13 PM
by Duncan C
Java Mandelbrot segment Help & Support fractalwizz 10 1231 Last post December 29, 2008, 08:01:24 PM
by cKleinhuis
[Java] Double-double library for 128-bit precision. Programming Zom-B 10 9650 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 50762 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.659 seconds with 28 queries. (Pretty URLs adds 0.021s, 2q)