I was re-reading Hacker's Delight and on page 202 I found a poem about division that I had forgotten about.

I think that I shall never envision
An op unlovely as division.

An op whose answer must be guessed
And then, through multiply, assessed;

An op for which we dearly pay,
In cycles wasted every day.

Division code is often hairy;
Long division's downright scary.

The proofs can overtax your brain,
The ceiling and floor may drive you insane.

Good code to divide takes a Knuthian hero,
But even God can't divide by zero!

Henry S. Warren, author of Hacker's Delight.


Rhomboid Permalink
May 25, 2012, 12:39

On modern Intel parts, 32 bit integer division for Nehalem and Westmere is specified with a throughput of 5-13 cycles, and for Sandy Bridge it's specified with a throughput of 11-17 cycles. At 3 GHz, that's in the neighborhood of 3-4ns, which is damn impressive. In the height of the Netburst era (~2004), 32 bit integer division on Prescott was specified with a latency of 30 cycles, or around 11ns at 2.66 GHz. And if you go back to the original Pentium, it was specified as 46 cycles, which at 166 MHz is 277ns.

I guess what I'm saying is that division used to be a scary boogeyman, but it's not anymore. The hardware people have done their job.

Leave a new comment

(why do I need your e-mail?)

(Your twitter handle, if you have one.)

Type the word "cloud_316": (just to make sure you're a human)

Please preview the comment before submitting to make sure it's OK.