Link to home
Get AccessLog in
Avatar of beavis6325

asked on

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.

Thanks in advance.

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";

      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;
                  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;

Avatar of 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.

Avatar of DanRollins
Flag of United States of America image

Link to home
This content is only available to members.
To access this content, you must be a member of Experts Exchange.
Get Access
Avatar of beavis6325


I've finallly worked it out in some free time that I've had, what do I do about the points?
if you believe that any of the comments posted has helped you, then award appropriate points. I believe that you probably want to lower points for the question or delete the question. to do so ask a question in the CS, post a link to this question and state the reason.