OT: computer arithmetic question on integer division
Markku Kolkka
markkuk at tuubi.net
Wed Jan 19 00:57:08 UTC 2005
Globe Trotter kirjoitti viestissään (lähetysaika keskiviikko, 19. tammikuuta 2005 01:59):
> Hi, thanks, to you and everybody!
>
> My question is: how does a computer actually do it? When we
> are dividing a number by a multiple of two, for example 5 =
> 101 divided by 2 = 10, then all we do is shift the bit by the
> number of digits after the leading 1 in 2. So, 101 divided by
> 10 means drop the last 1 in the 101 so we get 10.
>
> What happens if we divide 5= 101 by 3= 11? Anything similar?
It's done by shifts, subtractions, additions and comparisions. There are
many possible algorithms, here's a simple one called "restoring radix-2
division" (copied from Hennessy&Patterson):
We need three registers, one for the dividend (A), one for the divisor (B)
and one for the remainder (P). P and A form a double-length register pair,
P is initially zero.
1. Shift the register pair (P,A) one bit left
2. Subtract B from P
3. If the result in step2 is negative, set the low-order bit of A to 0,
else set it to 1
4. If the result of step 2 was negative, restore P to original value by
adding B to P
Repeat the steps as many times as there are bits in the registers.
The quotient will be in A and the remainder in P.
If A=101 and B=011 then:
P A
000 101 initial state
001 010 1. shift
-010 010 2. subtract
-010 010 3. set
001 010 4. restore
010 100 1. shift
-001 100 2. subtract
-001 100 3. set
010 100 4. restore
101 000 1. shift
010 000 2. subtract
010 001 3. set
010 001 4. restore
result=1 and remainder=2.
There are faster and more complex division methods.
--
Markku Kolkka
markku.kolkka at iki.fi
More information about the users
mailing list