Saturday, January 30, 2010

Rounding An Integer To The Next Maximal Mutliple Of A Given Radix Power

Let $ (\ldots d_3d_2d_1)_b$ be the modulo-$ b$ representation of an integer $ A$, where each $ d_i$ is a symbol/digit corresponding to values $ \{0,1,2\ldots b-1\}$. Often we are encountered with problems where we need to find smallest integer $ A' \geq A$ such that $ A'\vert b^y$ (i.e. $ b^y$ divides $ A'$ without any reminder), where $ y\in I^+$. Some of the very common applications include rounding the number of bits required to represent a data structure to the nearest byte (i.e. power of $ 2^y$). Before we see how to address this problem its worth while to understand the following interesting property of modulo representation. Given a modulo-$ b$ representation of $ A$ we can get corresponding modulo-$ b^y$ representation of $ A$ by replacing every group of $ y$ digits (in modulo-$ b$ representation), by the corresponding digit (i.e. $ d_{i_y}\times b^{y-1} + d_{i_{y-1}}\times b^{y-2} \ldots d_{i_1}$) in modulo-$ b^y$. For instance if we would like to convert an integer $ A$ in binary (i.e. $ b=2$) representation to hexa-decimal representation ($ b^y = 2^4$). We start from left to right and replace every $ 4-$bits with the corresponding digit in hexa-decimal system. For example if we see $ 1101$ we will replace it with digit $ D$, $ 1110$ by $ E$ and so on. So the hexa-decimal system is providing us with a one-one function $ H: \{0,1\}^4 \rightarrow \{0,1,2\ldots A,B,C,D,E,F\}$ for every $ 4-$bit string, in fact we can use any one-one function here when we move for modulo $ 2$ representation to modulo $ 2^4$. However the one-one function $ H$ has become a standard for module $ 2^4$ system.

So coming back to our original problem given the modulo-$ b$ representation $ A$, we would like to round $ A$ to $ A'$ , where $ A'$ is the smallest multiple of $ b^y$ such that $ A' \geq A$. To accomplish this task we need to examine the first (from right) $ y$ digits in the modulo-$ b$ representation of $ A$. In fact the value of in those $ y$ bits is the reminder we get when we divide $ A$ by $ b^y$, so if $ V$ is the value in those $ y$ bits then $ A' = A + (b^y-V)$. When $ b=2$ we can elegantly use the bit-wise operators to accomplish this. So if some one gives an integer $ X$ and ask to find a smallest $ X'\geq X$ which is a multiple of $ 2^y$ then we use the following C-statement to accomplish this $ X += ((1\ll y)-(x\&((1\ll y)-1)))\&((1\ll y)-1)$. Where $ \&,\ll $ are the standard bit-wise operators in C.

Posted by at No comments:
Subscribe to: Posts (Atom)