We're going to finish off this lecture by talking about an abstract data type for implementing complex numbers. This is almost ultimate extraction mathematically. So, what we're going to talk about is complex numbers, remember the form a plus bi, where a and b are real values, and i is defined to be the square root of minus one. Now, this is really a quintessential mathematical abstraction that dates back to the 18th century to Euler and Cauchy. Complex numbers are imaginary, but they give insight into real world problems that we wouldn't be able to easily address otherwise. So, to write programs to manipulate imaginary numbers is actually something that's actually quite relevant to the real world. So, if you're not familiar, we'll do a quick crash course. All you do to perform algebraic operations on complex numbers is just use real algebra, but whenever you see i squared, replace it by minus 1, and then collect terms. So, for example, to add 3 plus 4i and minus 2 plus 3i, we just use regular algebra, 3 plus minus 2 is 1, and 4 plus 3 is 7, and we have 1 plus 7i. To multiply, it's more complicated, 3 times minus 2 is minus 6, and then 4i times 3i is 12i squared, i squared is minus 1, that's minus 12, minus 6 plus minus 12 is minus 18, and then the other term comes from cross multiplying 3 times 3i is 9i, minus 2 times 4i is minus 8i, and so 9i minus 8i is i. So, just with regular algebra and collecting terms and replacing i squared by minus 1, we can perform algebraic operations, arithmetic operations on complex numbers. The other thing that's relevant about complex numbers is called the magnitude or absolute value, and that's just the square root of a squared plus b squared, so the magnitude of 3 plus 4i is 5, and there's many, many applications of complex numbers in signal processing, control theory, quantum mechanics, even understanding the performance of algorithms, we need to know about properties of complex numbers. So, now we want to develop an abstract data type for complex numbers on Java programs that manipulate them. So, what are the values? The value of a complex number is the real part and the imaginary part. So, 3 plus 4i, we'd use double values 3 and 4 minus 2 and 2, and so forth. Then, what operations do we want to perform? We're going to be able to create a complex number, we want to be able to add another complex number to this number, and multiply this number by another complex number. Compute the absolute value, the magnitude, and do a string representation. With this API, we can write programs that manipulate complex numbers, and that's very useful in all these applications. Some programming languages have a complex number type built-in because it's so useful, Java does not, but we can implement one as a Java class. So, let's do the implementation again according to the same methodology that we've been using. We're going to need instance variables, constructors, methods, and a test client. We'll start with a simple test client. Create two complex numbers and print them out, a equals plus a, then that calls the toString method, and b equals plus b that calls a toString method, and then print out the product and that's going to test out all the methods because in order to do the product you have to do a plus. So, if we call this test client, those values are built-in and makes those two numbers and multiplying, that's the way we expect this program to behave. Okay, so, let's take a look at the instance variables in the constructor, and again having done a turtle and the point charge is very similar. In this case, we are going to use immutable numbers. When you create a complex number it's a complex number, it's not going to change, same way when you create an integer, a double in a Java program, you don't expect its value to change. We might have a variable that has a value, we might have an object that has a value, but in complex numbers they're not going to change. So, here's how we create it, same way as before, instance, variables, and constructor are pretty much the same as before as in turtle and as in charge. Okay. Now let's look at the methods and given all the definitions that we have, the methods are quite straightforward. To add another complex b to this complex, we do the computation for the real part and the imaginary part and then we create a new complex number and return that. Now, there's a little bit, you might want to say that to make it more clear, you might want to be saying a.re instead of just re and there's a way to do that because the Java keyword 'this' refers to this object, the object that was used to invoke this method. So, you can say complex a equals this, and then say a.re. Now, we chose not to do that but that's an ultimate design for this code. For times, that's the manipulation that we talked about before where you can go ahead and do the cross multiplication and figure out the values of the real and imaginary parts of the product and then return, again, new complex with those parts. So, quite simple and then we've also done the test client and there's absolute value as well, and probably I should have tested that with our test client and there's toString. So, that's a full implementation of a complex number data type. There's a summary of it, and it's got the expected behavior, again, very similar to the other ones that we've done. So, as our last client, we're going to talk about a fascinating mathematical object called the Mandelbrot set. It's a set of complex numbers, was discovered by Benoit Mandelbrot quite a while ago several decades ago now, and it's really actually rather remarkable that he discovered it. It has to really involved with computation as you'll see, we'll get to this diagram in a minute. So, what we often do with complex numbers is represent a complex number x plus yi by a point x, y in the plane, and so that makes sense for the absolute value, it's the distance from the origin to the point. So, for Mandelbrot set uses specific definition. If the point is in the set we color it black, and if it's not in the set we color it white. So, for this example, say there's this point x equals minus 0.5 y equals 0. That one is in the set, so it's black, and all these points around the origin are black. Then points outside here say, 1 plus i, that one's not in the set. So, for every point in the plane there's a well-defined rule for whether it's in the set or not in the set, but the challenge is there's not a simple formula for testing whether a number's in the set. We have to employ computation and actually even the computation we employed, there's approximations as we'll see. So, how do we, how are we going to plot this? Well, I have to tell you what the rule is. It's really defined by an algorithm, and that's a really interesting concept. We're used to mathematical things being defined by equations or formulas and this case it's really defined by an algorithm and that's got interesting ramifications. So, I have to tell you what it means for a complex number to be in the set or not, and this is the test. Now, we have this iterative formula, where given z_0 and then we define z_1 to be z_0 squared plus z_0, z_2 to be z_1 squared plus z_0, and so forth, continue iterating that, if the absolute value of that sequence of numbers diverges to infinity, then z_0 is not in the set, that's the definition. Otherwise, it's in the set. So, what we have to know is for any given point, does this iteration diverge to infinity or not. So, for example, if we take our minus 0.5 plus 0i point and we keep iterating. We can do the calculations, but we'll do a simpler one in a minute. In this case, turns out to be always between minus 0.5 and 0, and so we can prove that, and that means at that point is in the set, does not diverge to infinity. On the other hand, if we take this point 1 plus i, and here's where you can check the math if you want, 1 plus i squared plus 1 plus i, 1 plus 2i plus i squared plus 1 plus i, i squared is minus 1, cancels out one of the ones, that's 1 plus 3i. Or if we take one plus 3i squared plus one plus i you can check the math that's minus seven plus seven i. This one, we can see that it's starting to get bigger and bigger and actually this one can prove that it diverges to infinity. So, that value one plus i is not in the set. That's the definition and it's really an algorithmic definition, you have to do this iteration and you have to know. Does the thing get, go grow without bound or not does the absolute value of that number grow without bound or not. So, that's the next challenge is to figure out how to actually plot this, and there's some definitely some practical issues. First one, is we can't draw infinitely many points, we can only draw a finite number of points. And the second one is, we can find out just by iteration, whether the thing goes to infinity or not. So, what we're going to have to resort to in order to plot the set, is some kind of approximate solution. So, for the first issue, what we're going to do is just take an N by N grid of points in the plane and just sample. We can take N to be big to get a detailed picture if we want but it's finite, so, N squared points, and if you want more detail, you can zoom in and stay tuned. We'll see, so we could take one of these little blocks and do an N by N grid inside that little block and we'll see examples of that in a minute. You're never going to get infinitely many points but you can get down to very very high precision, and for the second issue, well, there's actually a proven fact that if you get to the point where the absolute value is bigger than two, then you can prove that diverges and it's not in the set. So, if we get bigger than two we know it's not in the set. We never definitively know that it's in the set because we can't get to infinity but what we'll say is if we go 255 times and we haven't got over two, we're going to plot it black and probably we're going to think it's in the set, or anyway we're going to at least plot the points that you iterate 255 times and never got one that's bigger than two. So, now you have to note that in order to plot this we're really doing quite a bit of computation. For every one of those points you're doing this iteration, consideration involves operation on complex numbers. It's a lot of computation and I'll come back to this, that's why I say it's amazing that the Mandelbrot discovered this, and have to try to imagine his surprise as he did some of these computations for very small values of N. All right. So, let's look at the visualization. So, first of all, we want is just a function that returns white if a number is not in the set and returns black if well, iterates 255 times. So, that's a complex client. It's going to return a color, takes as argument or starting point in for 255 times. First of all, it's going to check if the absolute value of our number is bigger than two. If it is returns white. Otherwise we say z gets z times z and z gets z plus z zero and that's an iteration. Go through that and if we haven't returned yet that means we go 255 times we never got a value bigger than two, that's when we return black. So, that's the function we're going to use to determine the color that we assign to any point or any complex number. In a minute we'll see you can get a more dramatic picture by using grays, or colors picked from a color table. So, if you want to do gray-scale you just return 255 minus t. So, if you got above two right away, you'll have one color and if it takes you all but 255 you have much closer to white. So, we'll see that returns a much more dramatic picture allowing one color for each possible time that we got bigger than two, could have gotten bigger than two. So, that static method M-A-N-D we're just going to use to assign a color to a point and with that, we have another of our picture visualizations. We're going to take a point in the plane and then a size which is a square, what's the dimension of a square centered at that point, and that's in the whole plane. We can specify any point in any square and we'll take all of those from the command line, and then we'll also take N that is the size of our picture. How many pixels do we want to see? And we'll make a new picture N by N picture, and then as usual for every pixel, as for every column and every row, we're going to scale to get our x and y so, that's the standard scaling to convert our x and y into points in the plane, and then we're going to create a new complex which is our starting point from that x and y. So, for red at the center then x zero y zero is the points xc yc that we put in, and then we're going to create a color from that helper function for that point and we're going to set the pixel to that color, again, turning y-coordinate upside down because zeros zeros at the top and pictures, and then show the whole picture. That's a client that uses complex numbers to visualize the Mandelbrot set. Now, I'm just going to try to take you through what Mandelbrot maybe experienced. So, this is the kind of picture that you get with 32 by 32 in the 70s and 60s when he's working on these things that's about as many points as he could afford to plot and you can think of Moore's law going on as he got faster and bigger computers could do more points and maybe do 64 and the thing starts to come into a little bit sharper focus, or 128 now or 256. So, now we're talking about really a lot of points. So, this is you know getting up to millions of computations it's going to take awhile on an old computer. Particularly when you consider everything that goes into each point, and that's 512. So, this short program with a complex visualization. Immediately gives insight into this fascinating set, and this is only really the beginning of the story. If we start to put in our gray scale so, change that helper function to return a gray scale instead of just black or white. Then we get the same kind of thing, you can't really see the gray but here's one thing that we can do. Let's pick a little area there. So, that's a tiny little area and we'll blow that up to the whole screen. So, coordinates of that point is 0.1 and minus 0.637 and we'll make a 100 times we'll blow it up a 100 times by saying the size of R square is going to be 0.01. Get this amazing pattern that's completely different. And you can pick anywhere on here and blow that up and you'll get another amazing pattern or we can go to color and instead of assigning a gray scale for the zero to 255 we can pick 255 colors that we like and put them in a file and then just pick one of those colors when we get it i iterations we pick the color. They start getting a drawing like that, and if you blow up that one seems to be more interested in blow up that one. People have zoomed in on the Mandelbrot set for many many orders of magnitude. Up to a 100 orders of magnitude you can find on the web movies of people zooming in. All this interest in this simply a defined set, and these are just the kinds of images that you might get or that one all of this from that simple program that iterates complex numbers. So, that's really the ultimate client in terms of abstract data types. So, the summary, is with object oriented programming you can create your own data types, you can use them in your programs and manipulate objects that had datatype values, and really what it does is it helps us simulate the physical world. Often, objects are meant to model real world objects. Sometimes we have to struggle to make it reflect reality but we've seen plenty of examples with charged particles color sound and genome that allow us to compute with models of the real world. That's the real benefit of object oriented programming, and really it helps us extend the Java language to include the data types that we need. Java can't possibly have a data type for every possible application, but it does have us away for us to add our own abstractions, that's what a Java class does for us, and we've seen lots of examples of it just in this lecture and we'll see many many more examples because we're moving to a new level of programming. You've come a long way and in just, nine lectures from hello world. To programs that can manipulate color and pictures and charge objects in complex numbers. Our goal in this course was to open up a whole new world of programming for you and with this addition of object oriented programming we think we've satisfied that goal.
