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@xxxxxx
