OT: computer arithmetic question on integer division
deron.meranda at gmail.com
Tue Jan 18 08:22:52 UTC 2005
On Tue, 18 Jan 2005 07:35:37 +0000, Paul <paul at all-the-johnsons.co.uk> wrote:
> > > Does anyone know how the computer *actually* does integer
> > > division? I understand that with powers of 2, it just does bit
> > > shifting, but what about other powers, do you know?
Usually integer division is performed directly by the CPU in hardware
as a single instruction; although it's certainly possible in software
given a few basic primitives.
One of the most popular methods is a Radix-4 division, or more
generally a high-radix divider. There are however other methods too,
usually a tradeoff between complexity, transitor count, and
efficiency. Explaining how it works is a bit too involved for here.
However if you think about how you were taught to do long-hand
division (in decimal), the idea is similar, although your long-hand is
rather inefficient and unoptimal.
If you want to do more research, a good textbook on the subject of
"Computer Architecture" will cover this.
More information about the users