AI and Mandelbrot Calculations One of the things I found out a few years ago as an electrical instructor teaching at nuclear power plants was that the largest barrier to people learning something new was fear of the unknown. To these older electricians it was fear of the mysterious something called a sine wave and the complex intricacies associated with the field of higher mathematics of algebra. To those of us in the younger generation this may seem inane, but to them it was deadly serious. These were things they had not been exposed to before and many of them felt it was beyond their capability to ever learn or understand. Phooey! I am happy to report that this is never true. Even those individuals who are much slower than average have the capacity to learning EVERYTHING about ANYTHING, only in some cases at a slower rate than others. The very first step in learning is something new is believing that you can. The subject of AI brings out these same fears in many people - the strange mysterious something called pattern recognition associated with the field of higher computer science of Artificial Intelligence. Relax! It really is very simple and easy to understand. After you see what's going on you'll probably ask yourself "Why didn't I think of that?". "An intelligent program is one that exhibits behavior similar to that of a human when confronted with a similar problem. It is not necessary that the program actually solve, or attempt to solve, the problem in the same way that a human would." -from 'Artificial Intelligence using C' by Herbert Schildt, Osborne McGraw-Hill, 1987, p. 11 Keeping that in mind, run the program called SMART and watch it operate for a while. This compiled version of FRACAI.C picks a random point on the screen and displays the successive iterations used to determine if it belongs in the Mandelbrot set. Have a cup of coffee, sit back, and see if you can figure out the criteria the program is using to decide if it's time to move on to the next point. Now press 'Esc' and the program will exit after it is done the current point. Run the program called STUPID. The only difference between SMART and STUPID is the variable 'IQ' in STUPID is set to zero. This means the program does no pattern detection and goes strictly by iterations before moving on to the next point. Let it run for as long as you can stand to watch it. Had enough? Ok, go ahead and say it, "You STUPID program! Can't you see that your iterating on the same dumb points!?" And in truth, no it can't. What happens during the calculation is that sometimes 'i' and 'j' converge onto one or more points and gets caught in and endless loop of successive iterations producing the same 'i' and 'j' combinations. Once it can be seen that the points have converged into a pattern there is no need to continue iterating. Nothing to it! Run the program SMART again and we'll continue. Have you got a printout of FRACAI.C handy? Good. Now, let's see if we can think of a way of detecting the condition where the iterations converge on one point. Easy, right? You just look to see if the 'x' and 'y' are the same as the 'Lastx' and 'Lasty' for five success loops. If so, then it's a pretty good guess that 'x' and 'y' will stay the same for all successive iterations and it's Ok to move on to the next point. We've determined that this point has a periodicity of 1. For a convergence onto two points, A and B, it's a little different. In this case the iteration moves back and forth between A and B over and over again. Let's set 'Lastx' and 'Lasty' as the coordinates for point A. Every other iteration will produce these same coordinates. If after 10 iterations we see that point A shows up every other time, then we can guess that this 'i' and 'j' has a periodicity of 2. The same applies for a convergence onto three point A, B, and C. Let's just pick a point, say B, and set 'Lastx' and 'Lasty' to the coordinates for B. Now every third iteration will produce the coordinates for point B. Here's the kicker: in order for successive iterations to keep coming back to the same point B every third iteration, then the iterations would HAVE to have gone through the same points A and C each time. There is no need to keep track of the values for A and C since the iterations must be producing the same A and C values each time in order to get back to point B. So if it does this five times in a row we can safely guess that this 'i' and 'j' has a periodicity of 3. The same applies for higher periodicities. Pick a point, any point, and see if the iterations repeatedly come back the that point at a fixed interval. If after a bit you don't see a pattern then you can assume that the iterations have not converged yet. In that case we've already gone through a number of iterations and maybe it's converged into a pattern that doesn't include the point we chose earlier, so pick another point. This point picking process is determined by the variable 'CheckEvery'. This has to be a dynamic variable. If it is set to a small value the program exhibits the characteristics of impatience. If you keep it at say the value of 5 and the pattern has converged into a periodicity of 6 then every fifth iteration it will say to itself "No pattern here, pick a new point" instead of being patient and waiting for that sixth iteration. To large a value and the program is very stodgy. If 'CheckEvery' is set to say 2000, and it picks a point not in the pattern, then the program will go through 2000 iterations before picking a new point thinking that maybe it's just a very large pattern. The implementation I've found for far that works best is to double the value of 'CheckEvery' whenever it picks a new point. This catches the small periodicity patterns right off the bat and quickly expands it's scope to catch the larger ones. In theory there should be no need for an iteration limit in the calculation process since the calculations will always, after some period of time, either cause the program to bail out on overflow or detect a convergence into a pattern. In practice after a certain number of iterations I really don't care if a particular point converges or not, I just want to get on to the next point. You'll probably have noticed that I've been comparing points on the screen rather than using the actual values of each successive 'i' and 'j'. There is a very good reason for this. Of the 15 significant digits available in a double value roughly only half of those digits are significant after many calculations due to roundoff errors anyways. Besides, if I get a convergence that is beyond the resolution of the video display then that's close enough for government work! In the assembly language implementation it is easier to just look at half the significant digits rather than to bother rounding off. So the assembly language algorithm just compares the new values of 'si' and 'di' (the high word for the 32 bit 'i' and 'j') to the previous ones and treats these the same as it would for points on the screen. So that's it! If anyone has any questions, I would prefer if you would address them to me through the CompuServes's Microsoft C programing section. Remember, high sounding concepts will only be as intimidating as you let them. Have faith in yourself and your ability to learn and I'll guarantee you won't ever let yourself down! -Mark C. Peterson, [70441,3353] 128 Hamden Ave., F Waterbury, CT 06704 (203) 754-1162 (voice) Note to you corporations out there: I do computer consulting work in addition to custom written computer training courses. Give me a call!