How the Program Works
Newton's Method is an iterated function system which lends itself very nicely to computer science. That's exactly what computers are great for, crunching through thousands of mundane computations to get the final results that may have taken weeks or years by hand. My program is based on the Sierpinski Gasket program by Prof. George Francis. I essentially gutted it and used it as a two dimensional Open GL shell to create my program. First the program calculates a couple of important values and sets itself up to run. Then my program starts in the top left corner of the window and applies Newton's Method to each pixel or square group of pixels on the screen. Sweeping left to right and top to bottom. At each point it calls a function to find what root the point converges to using Newton's Method. Once the root is found a color is selected so that each root has a unique color and equal roots are the same color. If the point never converged or Newton's Method failed the point is left black. Next the point is shaded depending on how many iterations it took to converge. Once the screen is filled the program waits for the user to use zoom functions to move about the fractal. The navigation only changes the boundaries of the complex plane. Once these are recalculated the the fractal is redrawn with the new boundaries and it waits for a new zoom operation. Of course the program can be quit at any time.
Technical Problems
The first and most formidable problem I faced in coding this project was implementing complex numbers on a computer. Since computers are remarkably stupid and really only deal with 1's and 0's I had to teach it how to handle complex numbers. My program only uses polynomials so I had a limited number of complex operations to create. I accomplished this by creating functions to handle all the different complex operation my program would need to use. Next I needed to find a way to make the program flexible so that any polynomial could be studied. I wont explain that here, but if you really want to know get my source code. The whole purpose of Newton's Method is to find the roots of a function, but to get a computer to recognize what is a root, what is not and which roots are the same is fairly difficult. From there it was fairly easy to assign a color to the point. In an iterated function system the speed of the program becomes an issue even on multi gigahertz machines. I implemented a number of things to speed the program up. After every iteration of Newton's Method the program check to see if the new point is close enough to quit. Also the max number of iterations can be changed. I also attempted to optimize anything I could. However, you trade speed for accuracy of the fractal. This has shown up in roots being miss colored and regions being left black.
Compiling Issues
My program is written in C and compiled on both a Windows XP pc and an SGI graphics workstation running Irix (a form of Unix). It is uses the Open GL graphics library to draw the graphics. The current version requires no changes to the source code for it to run on both systems. However, because of differences between the two OSes and hardware, they behave a little differently. They both run fine but due to buffer flipping issues on Windows machines the user has to refresh the screen in order to see the picture. It is a minor inconvenience and will hopefully be corrected in future versions.
Version History
5/10/03 - Version that I will hand in as my final project, user controls are limited to zoom function. Everything else is hard coded and must be changed in the source then recompiled. I've compiled multiple executables each with different functions and different parameters.
Planned Updates
1 - Recompile in C++, this will make user controls much easier to implement.
2 - Implement user controls.
3 - Fix buffer flipping issue in windows version.