Joe Antonakakis

Eng @ Notion

Division without Multiplication, Division, and Mod Operators | Algos in Plain English

Posted at — Sep 25, 2022

This post is part of the “Algos in Plain English” post series.

The discussed algorithm aims to efficiently express floor division without use of multiplication (*), division (/ or //, depending on the language), and modulo (%) operators. This algorithm is expected to run in O(log(n)), where n is the dividend.

Problem Statement

The problem statement (pulled straight from Leetcode), is as follows:

Given two integers dividend and divisor, divide two integers without using multiplication, division, and mod operator.

Constraints on the problem include:

NOTE: Division can always be thought of as an operator between 2 unsigned integers, with a sign applied later based on the similarity or difference of the dividend and divisor signs. In the discussions below, we will speak of division as if it’s between unsigned integers for the sake of simplicity.

Naive Subtraction Approach

A common approach to solve this problem is to repeatedly subtract divisor from dividend until we can’t subtract a full divisor from dividend without going below 0. This algorithm would keep track of the number of times we could subtract divisor from dividend. The naive approach can be written as follows:

 from decimal import DivisionByZero

MAX_INT = 2**31 - 1
MIN_INT = -(2**31)


def basic_divide(dividend: int, divisor: int) -> int:
    if divisor == 0:
        raise DivisionByZero()

    is_pos = (dividend < 0 and divisor < 0) or (dividend > 0 and divisor > 0)

    dividend, divisor = abs(dividend), abs(divisor)
    answer = 0
    while dividend >= divisor:
        answer += 1
        dividend -= divisor

    return max(min(answer if is_pos else -answer, MAX_INT), MIN_INT)

Outside of some boilerplate code to check inputs and deal with signs, this code is very basic. However, it is also very slow for larger dividend’s and small divisor’s. It runs in O(n) time, where n is the dividend.

Assume the following pathological input:

basic_divide(MAX_INT, 1)

The algorithm above literally counts from 0 to MAX_INT, which is incredibly slow. If we run the above python code, it takes 169.63s to run on my Macbook Pro 15’.

Improved Algorithm Intuition

To understand the improved algorithm, we must build on a few concepts.

Binary Intuition

The naive approach fails to recognize a facet of numbers we can exploit for a logarithmic runtime:

Any number can be expressed by some summation of unique powers of 2 (1, 2, 4, 8, etc.)

Let’s look at some examples of what I mean:

The above is obvious if you think of numbers in terms of their binary representation. The binary representation of a number is literally expressing what powers of 2 sum to a given number by having a 1 in the binary value if that corresponding power of 2 is part of the summation, and a 0 if it’s not. Let’s look at a few of the above examples in their binary representations:

To really drive this point home, take 7. 7 can be expressed as a summation in the following way:

(1 * 2 ** 2) + (1 * 2 ** 1) + (1 * 2 ** 0)

Notice how each “chunk” of this summation is the bit value at a given position, multiplied by a power of 2. 9 can be expressed the following way:

(1 * 2 ** 3) + (0 * 2 ** 2) + (0 * 2 ** 1) + (1 * 2 ** 0)

At this point, you may be asking why this binary intuition is necessary. Well…

Finding Divisor Multiples Intuition

Given the above intuition, we can apply it to the original problem. If any number can be expressed as a summation of unique powers of 2, this means our quotient can be expressed in this way as well. How can we derive the quotient then?

It helps to start with an example upfront of why the above is important. Say we want to perform the following operation:

divide(100, 5)

One could subtract 5 from 100 a total of 20 times, but let’s see if we can apply some of our intuition to the problem.

Let’s ask ourselves a question: what is the highest power of 2 that 5 can be multiplied by where the product of said multiplication is still <= 100? This can be stated formally as:

What is largest n where (2 ** n) * divisor <= dividend?

NOTE: The above question is not framed in terms of the power of 2, but rather the exponent that yields a power of 2.

In the case of 5 and 100, the highest value of n is 4 (which represents 16 as the power of 2), because 5 * 16 = 80. This is valuable intel, because we now know that 5 goes into 100 at least 16 times.

Now what? Well, let’s perform 100 - 80 = 20, since we already know how many times 5 goes into 80. We are concerned now with understanding how many times 5 goes into 20. We can now ask a similar question to before: what is the highest power of 2 that 5 can be multiplied by where the product of said multiplication is still <= 20 The answer to this question is 4 (or n = 2 in terms of the exponent), because 5 * 4 = 20. At this point, we’ve found the answer because performing 20 - 20 = 0. This means the result of our division is 16 + 4 = 20.

Let’s take another example: divide(55, 7). Let’s run through our approach:

55 - (7 * 4) = 27
27 - (7 * 2) = 13
13 - (7 * 1) = 6

In the above example, we avoid going to 0 because 7 can’t go into 6 a total of 1 or more times. Our answer would be 4 + 2 + 1 = 7.

Final Intuition

With the above building blocks, we can formalize the final question our algorithm aims to answer:

What unique powers of 2 can I multiply by divisor and sum up to derive my answer to the division question?

An ideal algorithm would enable us to find 16 + 4 quickly in the 100 / 5 example, and 4 + 2 + 1 quickly in the 55 / 7 example.

Wait!? What’s all this talk of multiplication? I thought that wasn’t allowed based on the question prompt? Well, a useful property of binary numbers is that multiplication and division can be expressed as left and right shifts respectively. For example:

7 << 1 = 14 # 111 -> 1110; this is equivalent to multiplying by 2
7 >> 1 = 3 # 111 -> 11; this is the equivalent of dividing by 2

This means we can “multiply” by using bit shifts; we can derive the power of 2 that we’re considering by tracking the number of bit shifts in a separate variable.

At this point, we’re ready to put the approach into code.

Improved Algorithm Code

Below is the sample code for the improved algorithm. It is a heavily commented and tweaked version of some of the code found in this detailed StackOverflow answer.

 from decimal import DivisionByZero

MAX_INT = 2**31 - 1
MIN_INT = -(2**31)


def divide(dividend: int, divisor: int) -> int:
    # Early exit on invalid input
    if divisor == 0:
        raise DivisionByZero()

    # Derive the sign info; it's easier to work with unsigned
    # integers
    is_pos = (dividend < 0 and divisor < 0) or (dividend > 0 and divisor > 0)
    # Make both integers positive, and therefore "unsigned"
    dividend, divisor = abs(dividend), abs(divisor)

    # Early exit, as this would be 0 no matter what;
    # technically this algorithm would run correctly without
    # this check (as if divisor > dividend, current would
    # never be shifted left, and the shift right would make
    # it perma-0 throughout the run of the algorithm)
    if dividend < divisor:
        return 0

    # Answer will be what is built throughout the
    # algorithm's progression below
    answer = 0

    # Represents the most-significant bit we can add to answer, as
    # the algorithm's logic flows
    current = 1
    # This run finds the highest n where:
    # (2 ** n) * divisor <= dividend
    while divisor <= dividend:
        divisor <<= 1
        current <<= 1

    # Backtrack as the above loop will overshoot the highest
    # n by 1
    divisor >>= 1
    current >>= 1

    # Loop until we have no divisor left
    while divisor != 0:
        # Attempt to see if the current divisor (which is
        # multiplied by power of 2) is <= the remaining dividend
        if divisor <= dividend:
            # If it is <=, then `current` represents a new
            # power of 2 we can add to `answer`; OR-ing the numbers
            # together is a simple way to add that power of 2 to
            # answer
            answer |= current
            # The dividend is subtracted by divisor; for the rest
            # of the while-looping, a new, lower n is attempted to be
            # found which satisfies the condition:
            # (2 ** n) * divisor <= dividend (what is remaining of it)
            dividend -= divisor

        # Akin to dividing each by 2
        divisor >>= 1
        current >>= 1

    # When submitting this answer on Leetcode, the answer must be within
    # the bounds of 2 specified integers; this max(min(...)) sequence
    # ensures that
    return max(min(answer if is_pos else -answer, MAX_INT), MIN_INT)

What are these while-loops doing?

The most important nuance of this approach is that it doesn’t start from 0 to determine the power of 2 to add to the answer at each step. It uses the fact that the quotient will be the sum of unique powers of 2. This means the algorithm can scan the powers of 2 from highest to lowest, adding the ones to the answer that, when multiplied by divisor, incrementally “chip away” at dividend.

The above approach results in a single clean pass. This is more efficient than “counting up” (e.g. 1, 2, 4, 8 ...) to see what power of 2 can be added to the answer based on the divisor going into the remaining dividend that number of times.

Runtime Analysis

The above algorithm has a time-complexity of O(log(n)), where n = dividend. Counting up to the most significant bit takes log(n) time, and going down to 0 again takes log(n) time.

Practically speaking, running:

divide(MAX_INT, 1)

…takes 0.03s to run on my Macbook Pro 15’. Recall, the naive solution took 169.63s to run on my Macbook Pro 15’. This is a speed-up of 3 orders of magnitude (5000x speedup).

Conclusion

Analyzing algorithms like this one enables one to understand the binary number system better, and how it can be used creatively for efficient operations on numbers. It’s also a good look “under the hood” at how mathematical operations can be built programmatically.

Footnotes

Like this post? Add your email here to be subscribed to my future email list.