Kalles Fraktaler 2

[ellarien]

The find minibrots is broken even on the z^2 mandelbrot method for me. Has anyone had success with this? Although it is a minor feature.

It does work for me now, at least on powers 2-6.  (64-bit version 2.5.1.) It isn't foolproof, and it works best if you can get it roughly centered first on somewhere a minibrot has to be -- then it takes some of the drudgery out of zooming in, which is nice for zoom movies. Also, when it does work it stops a few zooms short of the minibrot actually becoming visible -- and it can occasionally be fooled by dense julias of the sort you get by passing very close to a minibrot.

[SeryZone]

Kalle, approximation at 3 and more powers doesn't work well.
For example:
max: 250,000
min: 34,223
Approx is not 34,223 about less! it is 256 iterations!

[Kalles Fraktaler]

I made a small update, now 2.5.2
I have made more adjustments on the glitch detection threshold, increasing it for each power from 0.000001 (squared value) up to 0.5 for powers 11 and above. But it still doesn't work so well for powers higher than that. And I haven't yet tested all views either ()
I've also solved the issue with changing from reference <0,0> to the center of the view, which is done deeper than e10 and which caused a difference of one iteration. It's hardly noticeable in images but is visible on a movie.

SeryZone, can you give me location parameters? The series approximation is very dependent of the "flatness" of the image. An image with mostly thin filaments can be approximated for example 2000 with minimum iteration 2005. But the rate you showed is usually for deep minibrots...

[SeryZone]

SeryZone, can you give me location parameters? The series approximation is very dependent of the "flatness" of the image. An image with mostly thin filaments can be approximated for example 2000 with minimum iteration 2005. But the rate you showed is usually for deep minibrots...

For THIRD power.
re: -0.039518784717566485688811172499194617461984478762
im: -0.769259846138562111329035386664949131620627931046
iterations: 17000
min: 10300
max: 15521
approx: 119!!!

[Dinkydau]

The reason perturbation is being used is of course the super speed, and it is very good, but it can be much better. I know I already mentioned it before, but fractal extreme as well as mandel machine are much faster (something like a factor 10) at calculating pixels at full precision than kalles fraktaler is. It's such a big difference that there has to be something fundamentally different about the way they are calculated. What is it?

[Kalles Fraktaler]

For THIRD power.
...
approx: 119!!!

Thanks seryzone you found a bug. It will be at least 1000 skipped iterations!

The reason perturbation is being used is of course the super speed, and it is very good, but it can be much better. I know I already mentioned it before, but fractal extreme as well as mandel machine are much faster (something like a factor 10) at calculating pixels at full precision than kalles fraktaler is. It's such a big difference that there has to be something fundamentally different about the way they are calculated. What is it?

Unrolled for loops = at least 2 times faster
SIMD = also 2-12 times faster (depending on your CPU)
But you cannot unroll the e10000 loops and less the e100000 the program will be too large.
...and you cannot do SIMD in 32-bit...

[Dinkydau]

Okay, the loop unrolling is more of a speed for space trade-off, but probably still worth doing up to some depth at least. Can you program SIMD? It would improve the speed more than anything at the moment.

[SeryZone]

Stop... Why 32-bit do not support SIMD??? It really support SSE (I tried it for my own 32-bit application), I add AVX too. My processor suport all SIMD without AVX2. And my applications on 32 bit and works fast.

[Botond Kósa]

Okay, the loop unrolling is more of a speed for space trade-off, but probably still worth doing up to some depth at least. Can you program SIMD? It would improve the speed more than anything at the moment.

Loops can be partially unrolled by checking the condition every nth time. If n is large enough (>20), it will run just as fast as a fully unrolled loop.

Kalle uses some generic arbitrary precision library I guess, that cannot use Mandelbrot-specific optimizations. This may account for an additional 2x-3x speed difference (in the computation of reference orbits).

No SIMD instructions are used in MM to calculate the reference orbit with full precision.

[Botond Kósa]

Stop... Why 32-bit do not support SIMD??? It really support SSE (I tried it for my own 32-bit application), I add AVX too. My processor suport all SIMD without AVX2. And my applications on 32 bit and works fast.

SIMD can be used in 32-bit applications, but only half of the registers (8 instead of 16) will be available. This makes it almost impossible to fully saturate the FPU pipelines of modern processors (especially the ones without HyperThreading). And also full-precision calculation of references will be 4x slower compared to 64-bit.

Kalle, do you have any statistics about the 32/64 bit download ratio of KF?

[Kalles Fraktaler]

My full precision class is my own and is not intended to be general, it can be adjusted for Mandelbrot fractals as much as needed
When I made it I had an idea that if the number of digits in each integer in the array would be fewer, I would win performance since overflow would not having to be checked, ideally not at all. I compared it with IBM's decNumber and by Wikipedia referred ttmath, and mine was twice as fast when it came to multiplying.
I later rewrote it to use fixed decimal positions, and it got another 2 times faster.
So I was pleased with that and I haven't touched it much since my very first fractal video 1.5 years ago (18th October 2012 <a href="http://www.youtube.com/v/PvPk&rel=1&fs=1&hd=1" target="_blank">http://www.youtube.com/v/PvPk&rel=1&fs=1&hd=1</a> )

I know that some very smart guys have worked many years with a Mandelbrot program, and they also published a number of articles about it. I have read and adopted only one of these articles, the one about squaring, so I have indeed more to learn in this area.

Here is a snippet of the very calculation of the reference:

Code:

for(i=0;i<m_nMaxIter && !m_bStop;i++){
	m_db_dxr[i] = xr.ToDouble();
	m_db_dxi[i] = xi.ToDouble();
	m_db_z[i] = (m_db_dxr[i]*m_db_dxr[i] + m_db_dxi[i]*m_db_dxi[i])*0.0000001;

	xin = (xr*xi).Double() + m_iref;
	xrn = sr - si + m_rref; 
	xr = xrn; 
	xi = xin;
	sr = xr.Square();
	si = xi.Square(); 
	m_nRDone++;
}

One thing to note - I use C++ operators which might not be the most effective, since they create temporary variables out of my control.
I have implemented a Square function, according to the above, and a Double function that instead of multiplying with 2 does a bit-wise shift, but that's about it when it comes to optimizations.
Also note that the threshold values are stored in a 3rd double array, m_db_z, to be used for glitch detection. Those extra 6 double operators also takes some time.

The reference calculation has not been my main concern, but any help on making this faster is much appreciated

Kalle, do you have any statistics about the 32/64 bit download ratio of KF?

I am sorry I have no statistics of downloads of my program.
Maybe Chillheimer has?
It would of course also be interesting for me...

[SeryZone]

My full precision class is my own and is not intended to be general, it can be adjusted for Mandelbrot fractals as much as needed
When I made it I had an idea that if the number of digits in each integer in the array would be fewer, I would win performance since overflow would not having to be checked, ideally not at all. I compared it with IBM's decNumber and by Wikipedia referred ttmath, and mine was twice as fast when it came to multiplying.
I later rewrote it to use fixed decimal positions, and it got another 2 times faster.
So I was pleased with that and I haven't touched it much since my very first fractal video 1.5 years ago (18th October 2012 <a href="http://www.youtube.com/v/PvPk&rel=1&fs=1&hd=1" target="_blank">http://www.youtube.com/v/PvPk&rel=1&fs=1&hd=1</a> )

I know that some very smart guys have worked many years with a Mandelbrot program, and they also published a number of articles about it. I have read and adopted only one of these articles, the one about squaring, so I have indeed more to learn in this area.

Here is a snippet of the very calculation of the reference:

Code:

for(i=0;i<m_nMaxIter && !m_bStop;i++){
	m_db_dxr[i] = xr.ToDouble();
	m_db_dxi[i] = xi.ToDouble();
	m_db_z[i] = (m_db_dxr[i]*m_db_dxr[i] + m_db_dxi[i]*m_db_dxi[i])*0.0000001;

	xin = (xr*xi).Double() + m_iref;
	xrn = sr - si + m_rref; 
	xr = xrn; 
	xi = xin;
	sr = xr.Square();
	si = xi.Square(); 
	m_nRDone++;
}

One thing to note - I use C++ operators which might not be the most effective, since they create temporary variables out of my control.
I have implemented a Square function, according to the above, and a Double function that instead of multiplying with 2 does a bit-wise shift, but that's about it when it comes to optimizations.
Also note that the threshold values are stored in a 3rd double array, m_db_z, to be used for glitch detection. Those extra 6 double operators also takes some time.

The reference calculation has not been my main concern, but any help on making this faster is much appreciated
I am sorry I have no statistics of downloads of my program.
Maybe Chillheimer has?
It would of course also be interesting for me...

Kalle, try to test my e8000 location with operators and without it. And, you, maybe want to realize Karatsuba multiplying?

P.s. And you had mistake: rewrite 'Botond Kosa' without 'Botond Kysa':

Thanks also to Botond Kуsa and knighty for the extensions on Series Approximation.

[Pauldelbrot]

P.s. And you had mistake: rewrite 'Botond Kosa' without 'Botond Kysa':

Hm? His own user name has an O (though, it's an accented O): "Botond Kósa"

If you're seeing a Y, you might have character encoding issues with your browser configuration or something.

[SeryZone]

Hm? His own user name has an O (though, it's an accented O): "Botond Kósa"

If you're seeing a Y, you might have character encoding issues with your browser configuration or something.

Ummmm, maybe, you are rigth. My browser even not decode sweden! Duh...

[Chillheimer]

Maybe Chillheimer has?
It would of course also be interesting for me...

sorry, no I don't have.
if you know how to set this up, let me know, and we'll do this