Home arrow Development Cycles arrow Page 2 - 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 - Newton's Iteration
(Page 2 of 4 )

The technique is also known as Newton-Raphson method, and in order to fully understand this section a little math knowledge is required. However, if some parts seem tougher, you shouldn't worry at all. You still will be able to use the method, you just won't get the full picture as to why it works (after all, you can use electricity- lights, computer, TV set, fridge, et al.-without knowing how electricity truly behaves).

This is the best-known method for successfully finding a better approximation for where a real valued function will be equal to zero. The speed of the convergence can be fast, and depends very much on the starting value of the iteration. The closer to the result you start, the faster you'll get to a better result. Be warned, however, that an initial value "far" from the root will lead to an undetermined, bad result.

Briefly presented, the idea behind the method is the following: you start with an initial guess that is quite close to the root. If this is true, then its tangent line drawn in that point approximates the function. If you compute the interception between the tangent line and the initial function, the new-found intercept is typically better than the value with which you started. Now we can repeat this step until we reach a point where the value reaches an acceptable precision.


Written up in the form of math, this can be reduced to the following equation:



The convergence of this is quadratic, as the error is squared practically at each step. So while we retouch our value at each step, we extend the error rate also at a quadratic rate. So it's crucial that we get a relatively close value to the root, otherwise the iteration may fail to converge to the end result we desire.

All right, so now you may ask how this will help us in the finding of the inverse of a number. Well, what we are searching for is the root of the function f(x) = 1/x - A. We derive the function and put it into the upper equation, and we'll get xn+1 = 2xn-Axn2. This involves three large number multiplications, one with a small number and a subtraction.

We can further optimize this to the form of: xn+1 = Xn (2-Axn). This contains only two large number multiplications and a subtraction from 2. As for the starting value, we can go as far as five digits, as we can find out easily from using the internal division found inside every compiler/computer.


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-2017 by Developer Shed. All rights reserved. DS Cluster - Follow our Sitemap
Popular Web Development Topics
All Web Development Tutorials