# Speeding up integer division if only certain bits in result are needed

Let's say I need to divide two integers $x$ and $y$, but I only care about the lowest 8 bits of the answer, i.e. I'm calculating:

$$r = \frac{x}{y}\,\,\%\,\,256$$where % is the modulus operator.

Is there a way to short-cut the answer rather than having to do the full division-calculation?

Update:

I'm entirely working with integer variables on a computer, so the result is rounded down to an integer as well. So, for example for $x=18423$ and $y=29$: $$r=\frac{18423}{29}\,\,\%\,\,256=635\,\,\%\,\,256=123$$

• What exactly do you mean by your integer division? So, for example, is $5/3 = 1$ or $5/3 = 1.66667$? May 26, 2015 at 20:35
• @Omnomnomnom You're absolutely right. I should have been more specific about that. Sorry. Updated the question. Thanks. May 26, 2015 at 22:20
• Knuth (AOCP vol. II, Semi-numerical Algorithms) may have some material on the question of whether it is possible to derive the low-order half of an arithmetic operation with any better method than truncating the full result. May 26, 2015 at 23:11

If you know that $x$ can be divided by $y$ without remainder (i.e. $x/y=d \in N$ because, e.g., $y$ is the result of some gcd computation of $x$ with some other number) you can do the following (for simplicity let me further restrict the answer to $x,y>0$:
1. $y = 2^k*y_1$ with $y_1$ odd. Hence $x$ must be divisible by $2^k$ and $x_1 = x/2^k$. $x/y$ = $x_1/y_1$.
2. Since $y_1$ is odd there exists $z$ in $[0,255]$ with $z*y_1 \equiv 1 (256)$. Also there exists $x_2$ in $[0,255]$ with $x_1 \equiv x_2 (256)$. Now $d = x/y = x_1/y_1 \equiv x_2*z (256)$.
• Unfortunately I can't be sure that $y$ divides evenly into $x$. But just to make sure I understand: You're first cancelling all common factors of 2 and then you calculate $1/y_1$ by determining its inverse $z$ in the multiplicative group mod 256 (if that is the correct use of the terminology) and multiplying that with $x_1\,\,\%\,\,256$, correct? Is there a way to determine $z$ that is quicker than doing the full initial division? May 26, 2015 at 22:30
• I'm trying to understand exactly why this approach only works if $y$ divides evenly into $x$. Clearly, if $y$ does not divide evenly into $x$, $x_2$ could end up being a multiple of $256$, in which case $d$ will always be $0$, no matter what $y$ is, which clearly is wrong. But somehow I'm missing the intuition in which general cases step 2 breaks down and why a zero-remainder fixes it. Step 1 should not cause any issues if the numbers don't divide evenly, correct? May 27, 2015 at 17:19
• Sorry... Meant to write ...$x_1$ could end up being a multiple of $256$... $x_2$ would be $0$ then. May 27, 2015 at 17:57
• For remainder equal to 0 we have $x_1 = d y_1$. Now $x_1 z = d y_1 z \equiv d (256)$. Now try to isolate $d$ in $x_1 = d y_1 + r$. May 27, 2015 at 18:37