*divided*by $a$. Following is an algorithm which can compute the

*quotient*and

*reminder*in $\Theta(\log(a) + \log(b))$ operations without using multiplication or division operators. In fact if the number of bits in $a$ and $b$ are known then the algorithm runs in $\Theta(\log(a) - \log(b))$ operations.

typedef unsigned int uint; // Integer division of b with a without using division // or multiplication operators. div_t integer_div(uint a, uint b) { div_t result; uint bit_diff = bit_count(a) - bit_count(b); uint prod = 0, prod_shift = b << bit_diff, shift = 1 << bit_diff; result.quot = 0; do { if (prod + prod_shift <= a) { prod += prod_shift; result.quot += shift; } shift >>= 1; prod_shift >>= 1; } while (shift); result.rem = a - prod; return result; } // utility function to find number of bits // required to represent the value of a. uint bit_count(uint a) { unsigned int i = 0; do { ++i; } while ((a = a >> 1)); return i; }

The above algorithm was tested on $4294967293$ pairs of $(a,b), a,b \in [1, INT\_MAX]$ and compared with

*std::div*-- running all these combinations just take around $2$ minutes on a mac book pro. It makes sense because that $\log(a) \leq 32$ (word size on the machine) hence we were just running around four billion constant operations. Typically in all algorithm analysis the word size is considered a $O(1)$, so as long as the inputs bit-widths are within the word size of the machine the runtime of the algorithm can be considered $O(1)$.

Notice that the algorithm is

*greedy*in nature and will provide a correctness next.

Let $c=\sum_{i=0}^{\log(a)-\log(b)}t_i\times 2^{i}$ and $t_{\log(a)-\log(b)}t_{\log(a)-\log(b)-1}\ldots t_0$ the bit representation of $c$. The algorithm tries to pick the powers of $2$ in a greedy manner (i.e. $2^{\log(a)-\log(b)}\geq 2^{\log(a)-\log(b)-1} \geq \ldots 2^{0}$). Consider the choice of $i^{th}$ bit of $c$, if $2^{i}\times a \leq b$ then any $i$-bit integer with a $0$ in the $i^{th}$ bit is strictly less than $2^{i}$. Since $2^{i-1} + 2^{i-2} + \ldots 2^{0} = \frac{2^{i-1+1} -1}{2-1} = 2^{i}-1 < 2^{i}$. We can use induction of $i$ to complete the proof. Hence we can claim that if we greedily pick the powers of $2$ (i.e ${2^i\,\,| \log(a)-\log(b)\leq i \leq 0 }$) it will yield the largest integer $c$ s.t $a\times c \leq b$. The integer division algorithm is just corollary of this basic fact.

## No comments:

Post a Comment