A Class for Representing Large Integers

Listing 5: Division of BigNum by another BigNum

//divide a bignum by another bignum
BigNum BigNum::operator/(const BigNum &denom){
     BigNum q;
     q.positive = (this->positive == denom.positive);
     if (abs(*this)<abs(denom)) return q;

     if (denom.exp <= 0){ //denom is a long;
                          //send it to the easy routine
         long x = denom.x[0];
         return (*this/x);
     }else{
         delete[] q.x;
         q.exp = this->exp - denom.exp;
         q.x = new int[q.exp+1];
         long qhat;  int qpos = q.exp;
         long d = BASE/(denom.x[denom.exp]+1); //d is a normalizer

         BigNum u(*this); //make a copy of the numerator
         BigNum v(denom); //make a copy of the denominator
         long start = u.exp+1;
         u = u*d;  v = v*d;
         if (u.exp<start){ u.exp = start;  u.x[start]=0;}

         for(;;){
          if (abs(u)<abs(v)){ //when u<v we can't divide anymore
            u = u/d;          //unnormalize u to get remainder
            return q;
          }
          int i = 0; long stop;
          while(u.x[start+i]==v.x[v.exp+i] && v.exp+i)i--;
          if (u.x[start+i] < v.x[v.exp+i])stop = start - v.exp -1;
          else stop = start - v.exp;

          qhat = long(u.x[start]);         //make a guess at qhat
          qhat = qhat*BASE + u.x[start-1];qhat/=v.x[v.exp];
          if (qhat > BASE-1) qhat = BASE-1;

          long temp;
          //fast check to see if qhat is too big
          if (start-1) temp = u.x[start-2]; else temp = 0;
          while (long(v.x[v.exp-1])*qhat>(long(u.x[start])*BASE + 
                      u.x[start-1]-qhat*long(v.x[v.exp]))*BASE +
                      temp)
          qhat--;

          BigNum work(v*qhat,u.exp);

          //qhat still too big??
          while(start-stop < work.exp){--qhat;  work = work - v;}

          long borrow = 0;                 //subtract work from u
          work.x[work.exp+1] = 0;
          for(i=stop;i<=start; i++){
             temp = long(u.x[i]) - long(work.x[i-stop]) + borrow;
             if (temp < 0){borrow = -1;temp+=BASE;}
             else borrow = 0;
             u.x[i] = temp;
          }

          v.x[v.exp+1] = 0;
          while (borrow < 0 && qhat){//oops qhat was still too big
                                     //add back
             qhat--;
             long carry = 0;
             for(i=stop;i<=start; i++){
                temp = u.x[i] + v.x[i-stop] + carry;
                carry = temp/BASE;
                u.x[i] = temp % BASE;
             }
             borrow += carry;
          }

          q.x[qpos--] = qhat;
          start = --u.exp;          //work on next digit of u
        }
     }
}
//End of File