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));
}
Next: Epilogue and Tests >>
More Development Cycles Articles
More By Gabor Bernat
