My Pages

Thursday, October 20, 2011

Computer Science = Math

Today when I was at work, I realized that I needed to draw a string at the mid-point of a 2d line. So of course, I go and google mid-point of a line and get the equation below.



Once I had this formula I plugged it in; but of course I wanted it in a different place. So, what if I wanted to place it at the quarter mark? So I searched but found nothing. Now it was up to me to figure out the mathematics behind it. Well, it's pretty simple right? Since X2 is the X for the end point; if we plug-in the previous equation into X2 clearly we can get the midpoint of the midpoint. This is as shown below.



Of course, this is a nightmare to look at; we need to simplify the equation. We'll be looking at this for only the x parameter since I don't feel like showing both x and y since they are pretty much the same. The first thing to do is to split the equation a bit so that we can begin to simplify.



Now, we bring down the fraction on top of the second fraction and combine the two denominators.



Now we need to find a common denominator (easy to see is 4) so we need to look at the first fraction and get the denominator to 4. To do this we can multiple the denominator by 2 (in order to do this we must multiple by 1 so this means we have to multiple the whole thing by (2/2))





Now we combine the two fractions which leaves us with the single fraction below.



At this point we just combine the parameters to end up with the final equation for finding the mid-point of a mid-point.



Now here is the thing; what if I wanted to get the midpoint of the midpoint of the midpoint? Well we start off with the main function.



Again, we split the fraction in half, bring down the second fraction and find a common denominator.





Now that we have a common denominator, we can go ahead and combine terms to get the final fraction.



So here was the coolest part, do you see that there is a pattern? Below you see the final fraction; n is the number of divisions you want of the line. 1 is the point at 1/2 the line; 2 is the point at 1/4 the line; etc...



So what does all of this mean? Why am I bringing math into this blog? Because sometimes we as computer scientists need to be reminded that mathematics is important in our day to day lives. I've met way to many developers who consider themselves programmers; however, if there isn't already an equation to express something that they need they just kind of assume that because no one has done it then it's not a worthwhile thing to do. Either this, or I'll see them write some really terrible way to perform this.

So for our example above, the fastest way to figure out how to get to the point of the line is to figure out the m (rise/run) and just go from point A to what they think should be point B. Then call it good enough. But if you're just doing that, maybe you need to rethink what you are actually doing.

Another thing, mathematics supports recursion in every way. Algorithms much simpler to express recursively; however, most programmers will stray away from recursive algorithms. As a matter of fact, the main complaint that I hear is that they are just too difficult and "make my brain hurt" to think of how to implement them. Maybe I'll write a blog about recursive algorithms; just to show how easy they are to actually write. The main reason that they were never better than iteration is that they required "calls" into methods/functions. However, in many newer languages; recursion is supported and is actually much better and stabler than iteration. This is usually due to values vs. variables which I should cover again at a later date.

My point is that you should never actually be scared of algorithms or doing mathematical work. If you do, you are narrowing yourself down to a typist that is paid to implement other peoples ideas. As functional programming becomes a larger paradigm, it will become important to learn how to actually work around in that paradigm. If you don't believe me; go checkout erlang and try to write a very simple application. Not a "hello, world" but instead what about something with an accumulator? What about a general for loop? You'll quickly see that recursion is an important part of functional programming life.

No comments: