Dividing large integer by large integer

Question

Guys I'm working on class called LINT (large int) for learning purposes, and everything went ok till know. I'm stuck on implementing operator/(const LINT&). The problem here is that in when I want to divide LINT by LINT I'm getting into recursive fnc invocation i.e:

//unfinished
LINT_rep LINT_rep::divide_(const LINT_rep& bottom)const
{
typedef LINT_rep::Iterator iter;
 iter topBeg = begin();
 iter topEnd = end();
 iter bottomBeg = bottom.begin();
 iter bottomEnd = bottom.end();
LINT_rep topTmp;//for storing smallest number (dividend) which can be used to divide by divisor
 while (topBeg != topEnd)
 {
  topTmp.insert_(*topBeg);//Number not large enough add another digit
 if (topTmp >= bottom)
 {//ok number >= we can divide 
     LINT_rep topShelf = topTmp / bottom;//HERE I'M RUNNING INTO TROUBLE
 }
 else
 {


 }
 ++topBeg;
 }
 return LINT_rep("-1");//DUMMY
}

What I'm trying to do is to implement this as if I would divide those numbers by hand, so for example having for a dividend 1589 and for divisor 27 I would go like so:

1. check if first digit is >= divisor and if so divide
2. if not add to the first digit another digit and check if a > b

At some point it will be bigger (in simplified scenario) and if so I have to divide but in this case I'm running into recursive call and I have no idea how to break it.
One note: as a tmp I have to use LINT instead of int for example because those numbers my not fit into int.
So generally what I'm asking for is there any other way to do division? Or maybe there is false logic in my thinking (quite possible). Thank you.

Answer 1

First, please don't work on such a class. Use CGAL's big int, and there was some boost bigint submission I think, also, there're about three or four other popular implementations.

Second, the division algorithm is described here: http://en.wikipedia.org/wiki/Long_division

[EDIT] Correct way to do it: Digit k of the result (C): if first digit (from left) of A, call it A[nA-1] is smaller than B[nB-1], write zero into C[k]. k-- (move to next digit). Otherwise, you seek maximum digit C[k] so that C[k]*B*10^k <= A. That is done in a loop. Actually, the previous sentence is a private case of this one. But it is not yet finished. You do A-=C[k]*B*10^k (the substracted part was zero otherwise). Only then,

k-- (next digit). Loop until k==0.

No need for recursion. Just two nested loops.

One loop for k (digit of the result), one loop for finding every digit, one loop (near it) for substracting (the -= operator).

Answer 2

When doing your part (1) you can't divide; you have to repeatedly subtract, or guess to subtract a multiple, just like when you do it by hand. You can 'guess' more effectively by setting upper and lower bounds for the multiple required and doing a binary-chop through the range.

I've done a similar thing myself; it's a handy exercise to practice operator overloading. I can supply a snippet of code if you like, although it uses arrays and half-baked exceptions so I hesitate to offer it up before the expert readers of this site.