Division
From ScienceZero
Revision as of 19:07, 5 January 2009 by Bjoern (Talk | contribs) (New page: Integer division is slightly more complicated than multiplication, one of the differences is that most numbers will not give an exact result. The simplest of all division algorith...)
Integer division is slightly more complicated than multiplication, one of the differences is that most numbers will not give an exact result.
The simplest of all division algorithms is just counting how many times the divisor can be subtracted from the dividend, (result * divisor) + remainder should always give us the original dividend:
result = 0 do dividend = dividend - divisor result = result + 1 while (dividend >= 0) remainder = dividend + divisor
The problem with this algorithm is that it is extremely slow when the dividend is a lot larger than the divisor.
The efficiency can be increased by subtracting some multiple of the divisor, by using 2n as the multiple we can use simple shifts to generate the required multiples.
divisorM = divisor //Find the largest multiple that makes sense do while ((dividend >> 1) > divisorM) divisorM = divisorM << 1 loop //Do division result = 0 do result = result << 1 if (dividend - divisorM) >= 0 then dividend = dividend - divisorM result = result + 1 endif divisorM = divisorM >> 1 while (divisorM >= divisor) remainder = dividend