Home arrow Development Cycles arrow Division of Large Numbers
DEVELOPMENT CYCLES

Division of Large Numbers


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.

Author Info:
By: Gabor Bernat
Rating: 3 stars3 stars3 stars3 stars3 stars / 8
March 10, 2009
TABLE OF CONTENTS:
  1. · Division of Large Numbers
  2. · Newton's Iteration
  3. · The Code Snippet
  4. · Epilogue and Tests

print this article
SEARCH DEVARTICLES

Division of Large Numbers
(Page 1 of 4 )

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).


blog comments powered by Disqus
DEVELOPMENT CYCLES ARTICLES

- Division of Large Numbers
- Branch and Bound Algorithm Technique
- Dynamic Programming Algorithm Technique
- Genetic Algorithm Techniques
- Greedy Strategy as an Algorithm Technique
- Divide and Conquer Algorithm Technique
- The Backtracking Algorithm Technique
- More Pattern Matching Algorithms: B-M
- Pattern Matching Algorithms Demystified: KMP
- Coding Standards
- A Peek into the Future: Transactional Memory
- Learning About the Graph Construct using Gam...
- Learning About the Graph Construct using Gam...
- Learning About the Graph Construct using Gam...
- How to Strike a Match

Watch our Tech Videos 
Dev Articles Forums 
 RSS  Articles
 RSS  Forums
 RSS  All Feeds
Write For Us 
Weekly Newsletter
 
Developer Updates  
Free Website Content 
Contact Us 
Site Map 
Privacy Policy 
Support 

Developer Shed Affiliates

 




© 2003-2014 by Developer Shed. All rights reserved. DS Cluster - Follow our Sitemap
Popular Web Development Topics
All Web Development Tutorials