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. It must be : 2 ^{(pmaxs)}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 a _{i} 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


« 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: p_{max} 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: order  knighty  quaz0r  knighty2 24  knighty2 8  16  3298  3297  3216  3298  32  3298  3379  3298  3380 
location 2 "light years away": order  knighty  quaz0r  knighty2 24  knighty2 8  32  300359  298493  300359  308258  64  300359  303375  305241  311275 
With knighty2, even at accuracy 8 only a few pixels are different from accuracy 24 by a few greylevels, imperceptible to the naked eye.



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


« 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: // 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 http://www.fractalforums.com/announcementsandnews/*continued*superfractalthingarbitraryprecisionmandelbrotsetrenderinginja/msg95838/#msg95838So 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. 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. 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


« Last Edit: October 04, 2016, 03:03:41 AM by quaz0r »

Logged




skychurch


« 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...



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



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 Then it either goes to infinity or zero. Bye bye fractal structures.



Logged




skychurch


« 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


« 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


« 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.



Logged




