Division without / operator

Question

I created a method that does division without the / operator. I believe this code is a bit slow and can be improved, but I am not sure how to do so. I'm not so good with shift operators (>> and >>>), but I believe that this will help a bit. How can I change my code to increase the speed of the division. I am open the changing my logic as well.

public class DivisionReplace {
    public static void divide(int N, int D) {
        int result = 0;

        if (D == 0) {
            System.out.println("Cannot divide by 0");
        }
        else if (N == 0) {
            System.out.println(0);
        }
        else if (N == D) {
            System.out.println(1);
        }
        else if (N > 0 && D > 0 && N < D) {
            System.out.println(0);
        }
        else {
            // both negative
            if (N < 0 && D < 0) {
                while (N <= D) {
                    N += -1 * D;
                    result++;
                }
                System.out.println(result);
            }
            // either N or D negative
            else if (N < 0 || D < 0) {
                if (N < 0) {
                    N = -1 * N;
                }
                else {
                    D = -1 * D;
                }
                while (N >= D) {
                    N -= D;
                    result--;
                }
                System.out.println(result);
            }
            // both positive
            else {
                while (N >= D) {
                    N -= D;
                    result++;
                }
                System.out.println(result);
            }
        }
    }

    public static void main(String[] args) {
        divide(-4,-10);
    }
}

Answer 1

A couple of comments first

It would be better to let your divide method should return an int, not do the output to System.out itself. Do the output in main like this:

public static void main(String[] args) {
    System.out.println(divide(-4,-10));
}

The variables N and D are short and don't follow the Java naming conventions. Parameter names should start with a lowercase letter and use camelCase. I would recommend calling them numerator and denominator.

If denominator == 0 is a quite exceptional case, I would recommend throwing an ArithmeticException stating that it was caused by division by zero.

You treat more special cases than you need to. I don't think you need to handle either numerator == denominator or numerator == 0 as a special case. It should be possible to handle that using the normal logic for division.

If you were doing divisions by a power of 2 (2, 4, 8, 16, etc.) you could use right shift numerator >> 1, numerator >> 2 etc. However, your code should support more than just those cases which makes things more difficult.

In the end, you are trying to re-implement division by using repetitive subtraction. It will be slow, no matter what you do. If you want to be possibly somewhat faster for bigger numbers, or want to try another approach (I can't promise you it will be faster, but I believe that for big enough numbers it will be significantly faster), you could try to implement division by using one of the good old "pen and paper" ways. Think about the division 303364 / 596. Try to solve that by hand! and think about what it is that you are doing. (Hint: Also think about how you do multiplications by hand, how would you solve 583 * 42 ?)

However, in reality though, the fastest solution is to use the / operator in Java, but that wouldn't be a challenge now, would it? So I guess that's out of the question :)

Answer 2

I disagree (slightly) with Simon Forsberg. Rather than having your division routine return an int, it would be better for it to return an object containing both the dividend and the remainder.

Your routine has another problem: it depends on multiplying by -1 to turn a negative number into a positive number. Unless you also widen the number, this is doomed to failure. The problem is fairly simple: assuming 2's complement (which Java does) there's a negative number for which no corresponding positive number can be represented in the same type. For example, a byte has values from -128 to +127. For an input of -128, there's no corresponding positive number unless you convert to a wider type. The numbers are larger, but there's a corresponding case for short, int and long.

If you can live with restricting the inputs to 32 bits, you can convert them to long, then do the division, and convert back to int when you're done. It's a little ugly, but not too terrible.

If you might at some point want to be able to divide longs correctly, you run into a little bit of a problem: the only wider type available is BigInteger, which is fairly slow and clumsy. Alternatively, if you can live with a rather different restriction, Java 8 (finally) supports an unsigned-long type, so you can use that instead. This, however, basically subsumes the code you're writing by providing an unsigned division routine in the JDK. At least as far as I can see, it doesn't seem to provide you with the tools to do the job (at all conveniently) on your own.

As far as the division algorithm itself goes, you normally want to do binary division. Simon Forsberg alluded to how you'd do long division by hand, and he's right about that. Unfortunately, in all the years I've seen that advice given, I've seen only a handful of people figure out how to do long division in binary based on how you do long division in decimal. Most try to re-do long division in decimal, which is quite painful by comparison.

Let's consider long division in decimal in a little more detail, then think of the same basic idea in binary. If we were going to divide 12345 by (say) 17, at the first step we'd basically "shift" 17 to the left until it matched up with 12. Since 17 is larger than 12, we'd shift it to the right one place, so our first real division step is 123/17. We write the 7 into the answer and subtract 17*7 from 123. Our next step is 44/17, and so on. The tricky part of this (as every school kid knows) is having to figure that 123/17 part. Most people can guess it's going to be somewhere around 7, but few are certain immediately.

Fortunately, in binary division that never arises. Binary division is actually a bit simpler:

1. Shift the denominator left until it's larger than the numerator (keeping track of how far you've shifted it).
2. Shift the denominator right one place.
3. If the shifted denominator is smaller than the current numerator, subtract it and put a 1 into the current digit of the answer.
4. Otherwise, put a 0 into the current digit of the answer.
5. If we've shifted the denominator back to its original value, quit.
6. Otherwise, repeat from step 2.

Assuming you do have an unsigned type in which to do the division, the procedure for handling signs correctly is something like this:

1. check the signs of the inputs
   • If they match, the result will be positive
   • If they differ, the result will be negative
2. Convert inputs to unsigned
   • if negative, subtract from 0: unsigned intermediate = 0u - (unsigned)input;
   • if positive, leave unchanged: unsigned intermediate = (unsigned)input;

Finally, convert the result back signed, and negate it if the result should be negative. This might seem to run into the same problem as we started with, but it really doesn't. The problem arose because in two's complement, there is a negative number for which there is not corresponding positive number. Every positive number does have a corresponding negative number though, so converting back to negative (if needed) at the end is actually pretty trivial.

As far as code goes, I'll use C++ since it has syntax similar to Java, but supports unsigned types directly. Using it, division can look something like this:

// A type to store a quotient and a remainder. Also supports output to a stream.
struct result {
    int answer;
    int remainder;

    result(int a, int r) : answer(a), remainder(r) {}

    friend std::ostream &operator<<(std::ostream &os, result const &r) {
        return os << r.answer << " remainder " << r.remainder;
    }
};

int sign(int x) {
    if (x < 0)
        return -1;
    if (x == 0)
        return 0;
    return 1;
}

result divide(int dividend_, int divisor_) {
    int res = 0;
    int current = 1;

    if (divisor_ == 0)
        throw std::overflow_error("Division by 0");

    if (divisor_ == 1)
        return result(dividend_, 0);

    // record whether the result will be negative:      
    bool neg = sign(dividend_) != sign(divisor_);

    // convert both inputs to unsigned numbers:    
    unsigned divisor = divisor_ >= 0 ? divisor_ : 0u - (unsigned) divisor_;
    unsigned dividend = dividend_ >= 0 ? dividend_ : 0u - (unsigned) dividend_;

    // shift the denominator left until it's larger than the numerator,
    // recording how many places we've shifted    
    while (divisor < dividend) {
        divisor <<= 1;
        current <<= 1;
    }

    // shift denominator right one place
    while (current >>= 1) {
        divisor >>= 1;

        // if that's less than the numerator, subtract and record a 1 in the quotient
        if (divisor <= dividend) {
            res += current;
            dividend -= divisor;
        }
    }

    // if the quotient should be negative, negate it
    if (neg) res = -res;
    return result(res, dividend);
}

This treats both division by 0 and division by 1 as special cases. Division by 0 really is a special case, so that seems pretty obvious. Division by 1 is a special case only because of that nasty asymmetry in 2's complement. If we divide the maximum-magnitude negative number by 1, the result can't be represented as a positive signed number. We could use an unsigned number for the intermediate results, but if we did doing the negation at the end would be more complex. This takes a rather different route, treating division by 1 as a special case. We only really need that special-case code for min_int/1, but it's simpler to use it for all division by 1 than to test both the numerator and the denominator, and use the special case only for the one case that's really special.

Short review of the code above: not the best names. Comments refer to "numerator" and "denominator", but code uses "dividend" and "divisor". The comments refer to the quotient, which the code refers to only as res and answer. Likewise, result for the type of the result is a horrible name--saved from colliding with every other result in a program only by the fact that nobody else would be nearly insane enough to use such a general name for anything.

Looking past the names, the most obvious shortcoming is (of course) the mere fact that this exists at all. It's simply a pointless waste (though something vaguely similar could make sense in the implementation of a large integer type, for one example). For really large number, however, there are almost certainly better division algorithms available. This one is fairly simple, but performance isn't the best--it produces only one bit of the quotient per iteration of its main loop.