Division of Large Numbers
(Page 1 of 4 )
Working with large numbers (including extremely precise ones) is possible, although compilers don't acknowledge the existence of such a class/type. Writing such a type/class may seem to be a hard task; however, if we take it one step at a time, it turns out that there are many advanced techniques that make our lives easier. This situation is true with the procedure of division, on which we will focus in this article.
I've already handled the build of the class and subtraction/addition here; also, we found a reasonably fast and efficient way to resolve multiplication with Karatsuba's technique. As you may have already figured out, this is a three-part article series, so if you missed the previous ones, please take the time to read them, as they are crucial if you intend to fully understand this one.
Now we have arrived at division. There are many ways that division can be interpreted. First, there is the concept that if multiplication really involves performing addition, just multiple times, then division is performing subtraction multiple times. This works well as long as you are in the world of integers. However, this can be extended to the type of division taught in elementary school.
So just write down the two numbers and transform all numbers into integers. Bring down the first n digits from the first number and start to find number two in the first n digits. Write down how many times you can find number two in the first n digits, subtract and repeat the procedure (n stands for however many digits have the second number).
This is a pretty straightforward method, but we have a small issue with it. This way you need to execute a subtraction and a few multiplications with one digit (to find out how many times you have the second number) and a compare for each digit precession in the result.
This sounds like (and it truly is) a very slow method, so we need to find something better. Luckily for us, the division part can be also perceived as nothing more than a multiplication with the inverse of a number. Hence, this is even better for us, because multiplication is already implemented, so less code needs to be written.
All that remains for us is to calculate the inverse of a specific "A" number. There exists a multitude of ways to accomplish this. And it also turns out that these methods are far more efficient than our initial approach. This issue was researched by many great mathematicians in the past, when computers weren't around to calculate division with blazing speed.
Namely, in the second part of the nineteenth century, Ramon Picarte published an accurate table of inverse of numbers with his own method. But we'll stick with a more widely known method that is thought to be simpler. It was made by the great physician and mathematician Isaac Newton, and is called Newton's Iteration (of course, as with many other theorems, he just came up with the initial idea as many others after him extended it to the way we know it today).
Next: Newton's Iteration >>
More Development Cycles Articles
More By Gabor Bernat
