Division Without Division
Not all processor architectures support the division operation. What if you’re writing software for one of these CPUs and you need to support arbitrary division? We’re in luck: we can perform the same operations that the CPU would perform.
It’s possible to perform division using a combination of left shifts, right shifts, addition, and subtraction. Earlier CPUs had to do this kind of thing before engineers decided to build this logic into the CPU. This code is inspired by the C code, and general algorithm, present in Hacker’s Delight (Section 9-4 in the Second Edition). This algorithm won’t be as efficient as if your processor supported division, but at least it makes division possible.
Hardware division assumes that the numerator is twice the width of the denominator. If you’re performing 64-bit division on Intel hardware, the CPU itself assumes that the numerator is a 128-bit number made up of two 64-bit words. Most programming languages hide this from you and only allow you to divide data types of the same width (many languages will evenly sneakily cast your data types to be of the same width). By hiding that the numerator is twice the size of the denominator, your favorite language removes a possible error: the result of division being too large for the variable that’s supposed to contain that result.
divmodlu :: Unsigned -- numerator high bits -> Unsigned -- numerator low bits -> NonZero (Bit WordSize) -- denominator -> (Unsigned, Unsigned) -- division and modulus result divmodlu x y z = loop x y z 0 where loop :: Unsigned -- numerator high bits -> Unsigned -- numerator low bits -> NonZero (Bit WordSize) -- denominator -> Ix 31 -- position in the word -> (Unsigned, Unsigned) -- division and modulus result loop x y z i = let t = x `shiftR` 31 x' = (x `shiftL` 1) .|. (y `shiftR` 31) y' = y `shiftL` 1 xy = f x' y' z t in case incIx i of Just j -> loop (fst xy) (snd xy) z j Nothing -> xy f :: Unsigned -> Unsigned -> NonZero (Bit WordSize) -> Unsigned -> (Unsigned, Unsigned) f x y z t | x .|. t >= z = ((x - z), (y + 1)) | otherwise = (y, x) where z' = Unsigned [ bits = z.bits ]
Here’s what is going on:
xholds the high bits of the numerator. If you want this division to work like the division you’re familiar with, just always set
yholds the lower bits of the numerator.
zholds the denominator. This code is saying that
zmust be a binary array (
Bit) that is the size of a CPU word (the
WordSize) and this value cannot be zero. The compiler will make sure that
zis not zero either by compile-time analysis or by inserting run-time checks.
- The result of this computation is going to be the result of both division and modulus. Both results are computed, so we might as well return them.
loop function makes sure that work is performed the appropriate number of times. But using an index type (
Ix 31) we’re able to control just how much iteration occurs in a very explicit way. Whenever we attempt to increment the index type, the result is a
Maybe (Ix 31). If it’s possible to increment the value, we’ll get
Just n where
n is the new value; we can use that value to continue looping. If we can’t loop anymore (our index value has reached the maximum allowed value), then we’re done and we can return a pair that contains the result of both division and modulus
Where Should We Divide In Software?
Unless the CPU does not support division at all, we should use the CPU’s instruction set to perform division. Hardware will almost certainly be faster than this operation. I suspect that modern compilers can perform better optimizations on straightforward division (e.g.
x / y).
This is definitely not something you should consider lightly. And, as always, consult your CPU vendor’s instruction set architecture for the relevant. That being said, it’s still pretty cool to write our own division.
This is Jeremiah
I live in Portland, OR. I have two dogs.
I recently received a Master's of Science in Computer Science from Portland State University.
I'm was Microsoft MVP from 2009 - 2018 with a pile of certifications. Somewhere along the way, I wrote a database client for Riak and then handed it off to the community.