You all know the Newton method to approximate the roots of a function, don't you? My goal in this task is to introduce you into an interesting aspect of this algorithm.
Newton's algorithm converges only for certain, but most of all complex input values. If you picture the convergence of the method for all input values over the complex plane, you usually get a beautiful fractal like this:
Image from Wikimedia commons
The goal of this task is, to generate such fractals. This means, that you get a polynom as the input and have to print out the corresponding fractal as an image in a format of your choice as the output.
The input is a whitespace separated list of complex numbers. They are written down in the style
<Real part><iImaginary part>, like this number:
5.32i3.05. You may assume, that the input number has no more than 4 decimal places and is smaller than 1000. The first of them must not be zero. For example, this could be an input to your program:
1 -2i7.5 23.0004i-3.8 i12 0 5.1233i0.1
The numbers are interpreted as the coefficients of a polynom, beginning with the highest power. Through the rest of this specification, the input polynom is called P. The above input is equal to this polynom:
f(x) = x5 + (-2 + 7.5i)x4 + (23.0004 - 3.8i)x3 + 12ix2 + 5.1233 + 0.1i
The input may come to you either from stdin, from an argument passed to the program or from a prompt displayed to your program. You may assume, that the input does not contains any leading or trailing characters.
You have to render the fractal in the following way:
- Choose as many colors as roots of P plus an extra color for divergence
- For each number in the visible plane, determine whether the method converges and if yes to which root. Color the point according to the result.
- Do not print rulers or other fancy things
- Print a black point at the points, that are the polynoms roots for orientation. You may print up to four pixels around each root
- Find a way to choose the visible plane in a way, that all roots are distinguishable and spread widely across it, if possible. Although a perfect placement of the output frame is not required, I reserve the right to refuse to accept an answer that chooses the frame in an unacceptable way, eg. always at the same coordinates, all roots are in one point, etc.
- The output image should have a size of 1024*1024 pixels.
- Rendering time is 10 minutes maximum
- Using single float point precision is enough
The output should be a raster graphics image in a file format of your choice, readable by standard software for a brand X operating system. If you want to use a rare format, consider adding a link to a website where one can download a viewer for it.
Output the file to stdout. If your language does not support putting something to stdout or if you find this option less convenient, find another way. In any way, it must be possible to save the generated image.
- No image procession libraries
- No fractal generating libraries
- shortest code wins
If you like this task, you could try to color the points according to the speed of convergence or some other criteria. I'd like to see some interesting results.