Why is division more expensive than multiplication?

Question

I am not really trying to optimize anything, but I remember hearing this from programmers all the time, that I took it as a truth. After all they are supposed to know this stuff.

But I wonder why is division actually slower than multiplication? Isn't division just a glorified subtraction, and multiplication is a glorified addition? So mathematically I don't see why going one way or the other has computationally very different costs.

Can anyone please clarify the reason/cause of this so I know, instead of what I heard from other programmer's that I asked before which is: "because".

Pronto

"After all they are supposed to know this stuff." - You might be surprised what most people don't know. – Jodhpur

Search for division is slower/more expensive than multiplication online, and you will see it everywhere. I don't think anybody claims it's not slower. – Pronto

You will have to ask an electronics engineer, it is a circuit design problem. Creating a hardware multiplier is pretty easy, a hardware divider is not. Practical divider circuits are iterative and therefore take longer. Ask at electronics.stackexchange.com – Agnella

Wikipedia (cf. article on FLOPS) and other sources (en.community.dell.com/techcenter/high-performance-computing/w/…) claim that typical CPUs can execute 4 floating point operations per clock cycle. This seems to be regardless of the type. Following this, division would be as expensive/cheap as multiplication. Who is volunteering to do a benchmark? – Straphanger

In short: quotient estimate and correction steps. – Boart

You're right that multiplication breaks down into multiple additions and division breaks down into multiple subtractions. The difference is that the additions in multiplication can be done in parallel, whereas in division, you can't do the next subtraction until finish the previous one and do a comparison. So a hardware multiplier will exploit this inherent parallelism by computing and summing up many sub-products simultaneously at the cost of increased area real-estate. Division does not have this luxury. – Eat

@AlexKemper: Several jsperf benchmarks exist, e.g. jsperf.com/multiplication-vs-division-lars The results vary from 0 difference to multiplication being 4x as fast. I wonder if javascript optimization subverts some of the tests, by noticing that the computed value is unused (hence the "control" test case). – Sinkhole

Why is division so much more complex than other arithmetic operations?, Why does hardware division take much longer than multiplication? – Shandishandie

Answer 1

CPU's ALU (Arithmetic-Logic Unit) executes algorithms, though they are implemented in hardware. Classic multiplications algorithms includes Wallace tree and Dadda tree. More information is available here. More sophisticated techniques are available in newer processors. Generally, processors strive to parallelize bit-pairs operations in order the minimize the clock cycles required. Multiplication algorithms can be parallelized quite effectively (though more transistors are required).

Division algorithms can't be parallelized as efficiently. The most efficient division algorithms are quite complex (The Pentium FDIV bug demonstrates the level of complexity). Generally, they requires more clock cycles per bit. If you're after more technical details, here is a nice explanation from Intel. Intel actually patented their division algorithm.

Reconciliatory

Answer 2

But I wonder why is division actually slower than multiplication? Isn't division just a glorified subtraction, and multiplication is a glorified addition?

The big difference is that in a long multiplication you just need to add up a bunch of numbers after shifting and masking. In a long division you have to test for overflow after each subtraction.

---

Lets consider a long multiplication of two n bit binary numbers.

• shift (no time)
• mask (constant time)
• add (neively looks like time proportional to n²)

But if we look closer it turns out we can optimise the addition by using two tricks (there are further optimisations but these are the most important).

1. We can add the numbers in groups rather than sequentially.
2. Until the final step we can add three numbers to produce two rather than adding two to produce one. While adding two numbers to produce one takes time proportional to n, adding three numbers to produce two can be done in constant time because we can eliminate the carry chain.

So now our algorithm looks like

• shift (no time)
• mask (constant time)
• add numbers in groups of three to produce two until there are only two left (time proportional to log(n))
• perform the final addition (time proportional to n)

In other words we can build a multiplier for two n bit numbers in time roughly proportional to n (and space roughly proportional to n²). As long as the CPU designer is willing to dedicate the logic multiplication can be almost as fast as addition.

---

In long division we need to know whether each subtraction overflowed before we can decide what inputs to use for the next one. So we can't apply the same parallising tricks as we can with long multiplication.

There are methods of division that are faster than basic long division but still they are slower than multiplication.

Histogen