Kalles Fraktaler 2

[Botond Kósa]

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++;
}

I suppose you store the full precision numbers in arrays inside sr/si/xr/xi. How are they stored exactly? In int or long arrays? Do you store decimal or binary digits? How many digits are stored in an int/long value?

[Kalles Fraktaler]

I suppose you store the full precision numbers in arrays inside sr/si/xr/xi. How are they stored exactly? In int or long arrays? Do you store decimal or binary digits? How many digits are stored in an int/long value?

Yes, these are of type CFixedFloat.
The full precision numbers are stored in an array of 64-bit integers.
They are limited to 8 decimal digits per integer in the array.

So... perhaps the "Lattice multiplication" method could allow me to have more digits per integer, as long as I use the Microsoft specific routines to multiply them and have them stored in two integers.
It could perhaps be a little more effective if they would be stored as binary values, so that bit-wise AND, OR and shift operations could be used instead of modulus, division etc.

http://www.chillheimer.de/kallesfraktaler/fractal_src%202.5.zip

[laser blaster]

I have a couple of tips about arbitrary precision arithmetic. I once wrote my own arbitrary precision math functions for my own fractal zoomer. Nothing came of it, though.

Don't use base 10. It adds extra overhead and is only useful for banking and accounting. Use the full range of the native integer type on the target machine as the arithmetic base.

For good performance, it's essential to use inline assembly or intrinsic functions to access the carry bit from addition, and to access the full 128-bit result of multiplying two 64-bit integers (on 32-bit machines, halve those numbers).

There's also this fantastic article on hpdz.net about arbitrary-precision math for fractals (these may be the articles you mentioned earlier): http://www.hpdz.net/TechInfo/Bignum.htm

It has great tips such as halving the number of multiplications needed for a bignum multiplication (which introduces error, but it's more efficient to use this trick and simply increase precision to compensate), and halving it once again for squaring .It also covers karatsuba multiplication, which I would recommend using for very high precisions (the savings will eventually greatly outweigh the costs of the extra carries), although it's not a good fit for SSE instructions, as the article mentions.

[Botond Kósa]

Laser blaster summed it up very well. One more thing to add: you can avoid multiplication and replace it with a squaring (which is about twice as fast) using an algebraic trick. Details can be found in the following article written by Bruce Dawson, author of Fractal eXtreme:
http://randomascii.wordpress.com/2011/08/13/faster-fractals-through-algebra/

[3dickulus]

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

if you have access to webserver logs...

$> grep fraktal_sft64.zip /var/log/www-access.log | wc -l

will tell you how many times the file has been accessed on *nix machines

[youhn]

I want to use Kalles Fraktaler to make zoom video, but I'm having some troubles. I'm running Kalles through wine on Linux and would like to produce a serie of still images, which I can scale back to get AA pictures. Then I want to use ffmpeg of mencoder to create the actual video. Is there a way to script it from command line? Or another way to produce large series of images?

[Kalles Fraktaler]

Thanks for the articles.
Of those I had already read and adopt one of them, i.e. the maximum precision truncates the result of a multiplication, and squaring can reuse the same result from a*b and b*a.
I just tested the square instead of multiplication trick, and it reduces the time to calculate an e8000 reference with 60000 iterations from 1:10 to 0:47 minute, so I can save a little but not revolutionary much...

I think the main drawback with my implementation is that each integer in the array only store 8 decimal digits. If they could store full 64-bit binary values and be multiplied to a 128 bit result, and implemented in assembler, I guess that would probably make it a couple of times faster.

I want to use Kalles Fraktaler to make zoom video, but I'm having some troubles. I'm running Kalles through wine on Linux and would like to produce a serie of still images, which I can scale back to get AA pictures. Then I want to use ffmpeg of mencoder to create the actual video. Is there a way to script it from command line? Or another way to produce large series of images?

You have the option to store additional jpeg images for each frame on a zoom sequence.
There will still be kfb files, so you have to remove these manually if you don't want them.
You can choose to store them in highest quality so that you don't loose too much quality.

[youhn]

Maybe I'm looking in the wrong corner, but I cannot seem to find a way to create good enough series of images. The function "Store Zoom-out images" seems broken (or just does not work correctly running it under Wine in Linux?). Both the kfb and jpg files are created and the numbering in the filenames seems OK. But after some images have been calculated, it seems to hang on just 1 location. Only the first and last few are good, everything in between are duplicated of 1 image.

In the keyframemovie.exe program I don't see an option for storing all (30 fps) images as jpg.

[marius]

I just tested the square instead of multiplication trick, and it reduces the time to calculate an e8000 reference with 60000 iterations from 1:10 to 0:47 minute, so I can save a little but not revolutionary much...

I think the main drawback with my implementation is that each integer in the array only store 8 decimal digits. If they could store full 64-bit binary values and be multiplied to a 128 bit result, and implemented in assembler, I guess that would probably make it a couple of times faster.

Just pointing out the obvious:
e8000 is 1000 "digits" in your notation? Thus a simple multiply (non-karatsuba) would be order of 1000x1000 operations.
e8000 in 64 bit would be 125 "digits". Thus 125x125 operations. That makes it 64x faster.. might be worth the hassle, perhaps?

Also, computers are binary machines. Doing such computations in decimal is a crime against their nature 

[Botond Kósa]

Just pointing out the obvious:
e8000 is 1000 "digits" in your notation? Thus a simple multiply (non-karatsuba) would be order of 1000x1000 operations.
e8000 in 64 bit would be 125 "digits". Thus 125x125 operations. That makes it 64x faster.. might be worth the hassle, perhaps?

Also, computers are binary machines. Doing such computations in decimal is a crime against their nature 

e8000 is 8000 decimal digits, this equals to 8000 * log₂10 = 26575 binary digits, and this equals 416 words (assuming 64-bit word length). So it would need 416x416 operations in binary, that is only about 5 times faster.

[marius]

e8000 is 8000 decimal digits, this equals to 8000 * log₂10 = 26575 binary digits, and this equals 416 words (assuming 64-bit word length). So it would need 416x416 operations in binary, that is only about 5 times faster.

Good point, duh. It seemed excessive when I did the math in my head but what's a factor of 10 among friends?

[SeryZone]

Heehee... My location is useful, isn't it?
P.s. Who knows, what does it means:
sfufpd or shufps ymm1, ymm2 and after binary code??? How it works?

[Botond Kósa]

Heehee... My location is useful, isn't it?
P.s. Who knows, what does it means:
sfufpd or shufps ymm1, ymm2 and after binary code??? How it works?

http://www.jaist.ac.jp/iscenter-new/mpc/altix/altixdata/opt/intel/vtune/doc/users_guide/mergedProjects/analyzer_ec/mergedProjects/reference_olh/mergedProjects/instructions/instruct32_hh/vc293.htm
http://www.jaist.ac.jp/iscenter-new/mpc/altix/altixdata/opt/intel/vtune/doc/users_guide/mergedProjects/analyzer_ec/mergedProjects/reference_olh/mergedProjects/instructions/instruct32_hh/vc292.htm

These are descriptions for the shufps and shufpd working on 128-bit xmm registers. 256-bit ymm variants work analogously, but shuffle twice as many data.

[ratcat65]

Newbie question here, i'm afraid. The last few frames of creating a zoom out movie are painfully slow to render. I'm currently stuck rendering a mandelbrot at 1.5 million iterations which is absurd. Is there some way to render these final few keyframes at a more realistic resolution? I tried cancelling the render and then lowering the iterations and then refresh but the program just renders that one frame and stops. If i try to restart the zoom out it just goes back to 1.5 million iters again.

[Kalles Fraktaler]

Ratcat65 - lower the iterations and restart the zoom sequence - but not with the "resume" menu option but instead with the "store zoom sequence" menu. The program keeps track of previous rendered files and their numbers. 
I will make an update within short with this issue fixed. There is a risk though that it will be an issue with the extreme movies like the YouTube user "fractal universe" creates, so I need to test it...