How to implement division by addition?

Question

An interview question.

How to implement division by addition? suppose they are all int.

My idea

1. Add divisor to itself until it is larger than dividend. Each iteration, keep the sum result before addition.
2. The quotient is the sum result before the last addition. the remainder can be counted by adding 1 until the quotient * divisor + reminder == dividend.

It is O(e^n), any better ideas? bit operation?

Answer 1

dividing m by n:

int r = m;
int q = 0;

while( r >= n )
{
    int k = 1;
    int x = n;
    int t;

    while( ( t = x+x ) < r )
    {
        x = t;
        k += k;
    }

    q += k;
    r -= x;
}

The result is q - quotient, r - remainder.

The idea is that x+x is the same as x*2.

UPD:

Some may complain that r -= x is not addition. Well we may update the algorithm to not use subtraction:

int p = 0;
int q = 0;

while( p+n <= m )
{
    int k = 1;
    int x = n;
    int t;

    while( p + ( t = x+x ) < m )
    {
        x = t;
        k += k;
    }

    q += k;
    p += x;
}

The result is q - quotient.

If we need the remainder then we proceed as follows (p - output from the above):

int r = 0;

while( p < m )
{
    int x = 1;
    int t;

    while( p + ( t = x+x ) < m )
    {
        x = t;
    }

    r += x;
    p += x;
}

The result is r - remainder.

The algorithm has obviously polynomial (not exponential) running-time.

Answer 2

In digital arithmetic we can name restoring and non-restoring methods as simple division algorithms which are based on addition/subtraction. Number of iterations in these methods are of O(n) (where n is the number of bits). There are methods like Newton-Raphson or reciprocal calculation which are based on multiplication and number of iterations in them are of O(log n). Take a look at http://en.wikipedia.org/wiki/Division_%28digital%29