 | Note |
|---|---|
| We will not be doing real division. Apart from the changes in representation of floating point numbers, the same principles are used in integer and real division. | |
Division on a computer is by long division, the way you'd do it by hand. It's slow (O(n)) and computers have special hardware (math coprocesssor) to speed up the operations.
In both binary and decimal, dividing by 10,100... removes 0's from the right end of the number. This is called right shifting and is a quick operation in computers. If the higher level language (e.g. python) detects that the divisor is a power of 2, it will substitute a right shift for the divide.
1100/10 =110 1100/100 = 11 1100/1000= 1 #note loss of a digit by underflow |
What is 1010/10 [374] ?
Here's long division in decimal. The algorithm (approximately): while there are more numbers in the dividend, loop through
move the divisor along the dividend. Place a 0 in the quotient where the divisor is greater than the dividend.
if the divisor is less, multiply the divisor by increasing single digits to find the biggest multiplier which gives a number smaller than the dividend. Record this number in the quotient.
Subtract this largest number from the dividend to give the new dividend.
063
-------
89 ) 5682
534
---
342
267
---
75
result 5682/89=63 with 75 remainder
|
Long division in binary is simpler. The divisor is either bigger than the dividend, in which case you place a 0 in the quotient, or is smaller, in which case you place a 1 in the quotient.
You can do subtraction by complement (this is what the computer will do). It's probably faster to do regular substraction. Here's the subtraction table (it may be easier to figure out subtraction in your head.)
A-B carry
B B
-| 0 1 -| 0 1
------ ------
0| 0 1 0| 0 1
A 1| 1 0 1| 0 0
|
010101
----------
101) 01101011
101
---
0011
00110
101
---
111
101
---
10
01101011<subscript>2</subscript>/101<subscript>2</subscript>=10101<subscript>2</subscript>
with 10<subscript>2</subscript> remainder (decimal 107/5=21 with 2 remainder)
|
what is 100111102/1102 using the complement to do subtraction [375] ?
It's not often that you do a lot of division, but if you do, since division is slow and multiplication is fast, you should combine divisions e.g.
original problem (you're dividing twice) A=B/C D=A/E or D=B/(C*E) instead multiply once and divide once divisor=C*E D=B/divisor |
Say you're dividing a whole lot of numbers by the same number (e.g. you're rescaling a set of numbers) A division might take 64 clocks, while a multiplication might take 4 clocks. Rescaling 100 numbers by division will take 6400 clocks, whereas doing it by a single division followed by 100 multiplications will take (64+4*100=464) clocks, a speed up of 14.
instead of a/x, b/x, c/x.... do X=1/x (one division) then a*X, b*X, c*X... |
Hardware that does a lot of division (supercomputers, graphics cards) will have a hardware reciprocal operation (divides the number into 1). (Graphics cards have lot of code that takes reciprocals of reciprocals.) This uses Newton's method, is mostly multiplies and is quite fast. You won't know that the machine is doing a reciprocal - the compiler will handle that for you. The reciprocal hardware is too expensive to justify adding to regular desktop machines.