Hello,
I wrote a library for arbitrary precision arithmetic recently and spent a long time implementing efficient multiplication algorithms. Now I am looking to see if it is possible for me to optimize anywhere else. One place that I thought should be more optimizeable is my division algorithm. Right now I use (hiding some internal implementation stuff):
Int divide(Int numerator, Int denominator)const
{
if (denominator==0)
return DIVIDE_BY_ZERO_ERROR;
if (numerator==0)
return 0;
if (numerator.sign()!=denominator.sign())//result is negative
return -((-numerator)/denominator);
if (numerator==denominator)
return 1;
Int num=numerator.abs();
Int den=denominator.abs();
Int ret=0;
while (num>den)
{
ret++;
num-=den;
}
return ret;
}
Which is fairly slow, especially since subtraction takes awhile when done on Int's instead of on the individual digits of those Int's. Is there a faster way to get the integer part of the quotient of two numbers? Perhaps one that actually uses their internal digit-array representation?