March 24, 2012
Division Algorithm
Last week, I had mentioned I wanted to develop a math related program to go along with the whole "Pi Day" celebration. I intended to write it in Java. I ended out writing it in C++.
It deviated into another programming language when I couldn't recall what Java does to invoke exception handling. I can use exception handling just fine in C++, PHP, and JavaScript. But I guess I haven't been programming enough Java to know all of Java's predefined exceptions. That is one of Java's pitfalls. Just everything is defined for you right about at the time you'd rather make the discovery on your own. In this case, I wanted to demonstrate how computers divide and find square roots (or nth roots for that matter).
I think what really has me in a bind is that some of my job leads wanted me to know Hibernate and Spring. That would be all fine to work with if Eclipse wasn't such a Leviathan to work with and the software developer though about everyone who doesn't use the Enterprise Edition of Java.
To me, Eclipse and Java EE is being told that if you want to be a pilot, you have to fly a big commercial aircraft. Where as I have more experience flying the small airplanes (Vim and Java SE) which I am more comfortable with using.
But I can't have "no" in my heart, which has been one of my issues when I look for work to apply my skills. It's a challenge I am working to overcome. I mostly do it because I'm quite timid with working for someone who expects me to know everything and perform some sort of alchemy to spin thread into gold and to make a lot gold immediately.
What I do is not magic and is not done instantaneously. Rarely is great software written overnight by one person with no support or co-workers to fall back on when things are tough or when you need to know how to do something to make your task work. If you have ever seen the movie The Social Network, even Mark Zuckerberg had to rely on Eduardo Saverin, Dustin Moskovitz, and Chris Hughes to make Facebook possible. It was not a one person gig. The same can be said about Microsoft, Apple, Google, or any other successful software or hardware company in existence.
These things don't take off from the ground by having some guy with an MBA just hire some guy with a CS degree to create everything for him especially if it is something an IT person should be doing. A more responsible person hires several people, each with a unique talent or forte to assemble to components that can be put together to create the software he wants to sell. The maestro needs to assemble his orchestra and practice before he can invite the public to the concert.
Today, I am sharing one of my solo pieces with the audience.
Computers, by their design, can not divide. They can add, subtract (by modifying addition), and multiply. But on their own, they can not perform the most complex of the four basic arithmetic operations: Division. Even when they can divide, it takes at least four times as many clock cycles to complete division than it does for addition or multiplication. Part of the reason is that division requires modification of the division, to turn in into multiplication through a set of calculations using a method from the field of numerical analysis called the Newton-Raphson Method. I hope in the future to modify this post to explain it mathematically. The best I can do is come up with a video on YouTube in the near future that will describe the mathematics behind it. But for now, let's stick with the code.
After I attempted to try this with Java, I retried my method by writing it on a TI-83 graphing calculator. It was during this phase, I realized that instead of letting the pick the number to use to guess with, the computer--rather the calculator--could do this.
Since our Newton method formula requires that we turn division into multiplication by multiplying the dividend, or numerator, by the reciprocal of the divisor, or denominator, of which the key part of the division is finding the reciprocal of the divisor, all guesses had to have been a value greater than zero and less than 1. And to start out, our first guess had to be 0.1 (or 1/10). Using the first guess, we could find the value of what the next guess is. If the initial guess was larger than the next guess, such that the difference between the next guess and the initial guess was less than zero, an new initial guess had to be use that was smaller than the present initial guess. To find the new initial guess, we take the original guess and multiply it by 0.1. Thus 0.1 times 0.1 is 0.01. And if that is still too big, we can do that again and get a product of 0.001 and so on until it fit. This will go on so as long as the guess is greater than the precision variable or if the next guess generated was equal to zero.
When the reciprocal was discovered, it would return the value to the division function by multiplying it by the dividend producing the desired quotient answer.
So, submitted for my portfolio, with a downloadable version coming shortly, I present my division program.
A more advanced version of this program including a algorithm for nth roots (as I previously stated) should be coming soon. I just want to use the methods in this program in the other program and for polynomials in the future. Who knows, I'll probably throw in some OpenGL graphics. For now, this works. I will produce more programs like this in the near future.
