Implement division without using the division or multiplication operation

Problem: Implement division without using the division or multiplication operation.  Round to the nearest whole number

int divide(int numerator, int denominator) {

...

}

Solution:  Let’s start with an example.  In this case,

Numerator= 108

Denominator = 10

We know that the answer to this is 10.8, which rounds up to 11.  But, let’s think about how we got that.  We know that 10 can be multiplied by 10 to get 100.  This is equivalent to adding 10, ten times.

Similarly, we can subtract 10, ten times from 100 to get zero. 

This starts to intuit an algorithm, where we see how many times we can subtract and that is most of the answer. 

But, how do we deal with what is left over?  In this case it is 8.  We’re supposed to round up or down, so we can compare 8 to 10.  We’re not allowed to divide, but we are allowed to add an compare.  So, we can double 8 by adding it to itself.  If the result is greater than 10, we round up.

Putting this into code, we get:

    int answer, curValue, i;

    for (i=0, answer=0, curValue=numerator; i < numerator; i+=denominator) {

        curValue -= denominator;
        answer++;

    }

    // round up if necessary
    if ( curValue + curvalue <= denominator) answer++;

    return answer;

}

This is almost right, but it has at least problem.   Can you see it?  If not, try a negative number example.

What do we do if we get a negative number?  In this case, our algorithm fails as one number will go up or down indefinitely. 

To solve this, we need to use some if statements to make sure that we are always iterating in the right direction.  We also can’t divide by zero and need to check that case too.   We can solve this with three if statements a shown:

int divide(int numerator, int denominator) {

    int answer, curValue, i;

    //check for 0 denominator
    if (denominator == 0) return ERROR_VALUE;

    for (i=0, answer=0, curValue=numerator; (numerator > 0 && i < numerator) || (numerator < 0 && i > numerator);) {

        //if both numerator and denominator are positive or negative:
        if (numberator >= 0 && denominator > 0) {
            curValue -= denominator;
            answer++;
            i+=denominator;
        } else {
            //one is negative
            curValue+=denominator;
            answer--;
            i-= denominator;
        }

    }

    // round up if needed
    if (curValue + curvalue <= denominator) answer++;

    return answer;

}

This is an example of a problem which starts out simple, and gets much more complicated.  It’s good to do some examples now with varying positive and negative numerators and where you round down and up.  There’s actually still a bug in this solution, but I’ll leave it to you to discover it.

/*Please let me know if you know alternate solutions or find bugs other than the one left in there.  Thank you.  Noah */