Home arrow Development Cycles arrow Page 3 - 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 - The Code Snippet
(Page 3 of 4 )


Large_Numbers Large_Numbers::NewtonIterPrep

( Large_Numbers& forNumber ) const

{

Large_Numbers x0; // this will hold the inverse

int at ; // the initial inverse


// now resolve the shift of the input to be a integer with

int shifted = forNumber.m_all - forNumber.m_whole;

forNumber.ShiftIt(shifted); //shift



if(forNumber.m_all < 5)

{

at = atoi(forNumber.m_number.c_str());

}

else

{

std::string temp; temp.assign(forNumber.m_number.begin(),

forNumber.m_number.begin() + 5);

at = atoi(temp.c_str());

}



First we shift the input number so we'll work only with integers. After that we take the first five digits and find its inverse, as the first five digits will tell us the correct first five inverse for the number. This way we'll start pretty close to the root.



char buf[9];

sprintf_s(buf, 9, "%1.6f", static_cast<double>(1) / at );

 

x0.m_number.assign(buf, 7 * sizeof(char));

x0.m_number.erase(++x0.m_number.begin());

 

x0.m_all = 6; // the dec + 0

x0.m_whole = 1; // only one whole

 


Now we'll extract the inverse here. We only need to be aware that the division made by C will round the last digit if needed, so we'll extract the first six digits but save only the first five.


int size;

if( (size = forNumber.m_number.size()-5) > 0)

x0.ShiftIt(-(int)forNumber.m_number.size()+5);


double kl ;

kl = DIVIDE_PRECISION/5;

int prec =static_cast<int>(log(kl)/ log(2.0)) + 2;


The number of iterations needed to complete this depends on the precision required. This way we are getting iterations of the following formula: 5*2^i. But a specific level of precision can be reached also by cutting off the extra digits after the inversion. We also shift the initial number, so if we got a large number the inverse value will be equally small. 


Large_Numbers two("2", 1, 1, +1);

 

x0.opt();

int tempN = x0.m_all, i;

for ( i =0; i < prec; ++i)

{

x0 = x0 * (two - x0*forNumber);

 

if (tempN == x0.m_all) // check if no change

{

break;

}

else

tempN = x0.m_all;

}


Now here we execute the iteration, but watch out: no change means that no change occurred, so we already have the exact result; thus, we do not need to iterate further.


if ( i == prec)

{

x0.m_number.erase(x0.m_number.begin() + x0.m_all/2, x0.m_number.end());

x0.m_all /= 2;

}

 

 

 

//redo the shift

forNumber.ShiftIt(-shifted);// reshift

x0.ShiftIt(shifted);

 

return x0;

}


The iteration does not converge perfectly, even with a perfect start; at the end, some errors will creep in. However, it is safe to say that the previous iteration's generated digits are correct. Therefore, we'll generate the iteration a step further and cut off the last iteration. Nevertheless, this is done only if we don't get a perfect result.

Once we get the inverse, all we need to do is to call a multiplication, as we have done in the lines below:


Large_Numbers Large_Numbers::operator/(Large_Numbers& x)

{

// just return the multiplication with the inverse

return this->operator *(NewtonIterPrep(x));

}



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