# need help implementing arbitrary precision integer division, having trouble understanding algorithm.

Hi, I have been trying to understand how to implement the rest of an arbitrary precision integer arithmetic class and  I'm having quite a bit of trouble implementing the divide function.

I would like some help, but what I am asking of the experts here is this:

1) implement the division function in C++ with the given constraints listed below.
2) if at all possible give a brief explanation of what you are doing so that I don't get stuck in the same jam again.

Constraints: I am going to give a description of the class that I've already implemented so you know the variable names
1) enum{negative, zero, positive};
typedef char digit;

2) important variables: digit*  LargeInt::num is an pointer to the beginning of an array of digits used to hold each digit of the number which gets allocated when arithmetic is performed or during the copyconstructor.
size_t LargeInt::len; amount of digits currently being held. to keep track of the size of the array
unsigned short sign; the sign of the number, either negative, zero, or positive from the enum above.
3)digit does not automatically expand, this has to be handled within the individual functions.
4)len needs to be updated within the functions if the length is to change.
5)implemented using an algorithm besides simply subtraction or addition i.e. long division algorithm or faster.
6)implemented assuming I do not have a working minus or compare or shift function currently, unless that is too much of a problem.

This seems like a lot of stuff, but I don't believe it would be too much code, the algorithm for long division I was using just won't click and I have exams to study for soon.  I also understand vector might be useful, but I'm stuck with someone else's implementation on most of this.

I hope this isn't too much to ask.  The sloppy code that I had originally is listed below only so you can see some examples of how the class currently works, not exactly works, but the work in progress of what I was trying.  I had no idea the division would be so much different than the rest of the operators.

I'll be checking up to answer any questions anyone has.

LargeInt operator/(const LargeInt& a, const LargeInt& b){

//if first is zero
if (a.sign == zero) {
LargeInt Int1;
return Int1;
}
else if (b.sign == zero){
cout << "Divided by zero, have to quit\n";
exit(-1);
}

int which;

which = LargeInt::compareAbsolute(a, b);

LargeInt temp;

if (which == -1){
return temp;
}

if (which == 0){
if (a.sign == b.sign){
return temp = 1;
}
else{
return temp = -1;
}
}

if (b == 1){
return temp = a;
}

LargeInt row;                  // shifted row
LargeInt tmp;                  //placeholder
LargeInt num1(a);
LargeInt num2(b);

LargeInt result;            //result to return;

delete [] row.num; delete [] tmp.num; delete [] result.num;   //requirement

int i;                        // counter

result.len = row.len = num1.len;
result.num = new digit[num1.len];
row.num = new digit[num1.len];

for (i=num1.len; i>=0; i--) {
LargeInt::shift(row,1);   //shift over 1 digit
row.num[0] = num1.num[i];
result.num[i] = 0;
while (LargeInt::compare(row,num2) != positive) {
result.num[i] ++;
size_t tmplen = num1.len;
tmp.num = LargeInt::minus(row,num2,tmp.len);
tmp.len = tmplen;
row = tmp;
}
}

return result;

}
grg99

The way to do it is to EXACTLY follow the steps you use to do it by hand.

And I do mean EXACLY.

Not all that hard as soon as you realize this.