2
$\begingroup$

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$$

$\endgroup$
3
  • 1
    $\begingroup$ What exactly do you mean by your integer division? So, for example, is $5/3 = 1$ or $5/3 = 1.66667$? $\endgroup$
    – Ben Grossmann
    May 26, 2015 at 20:35
  • $\begingroup$ @Omnomnomnom You're absolutely right. I should have been more specific about that. Sorry. Updated the question. Thanks. $\endgroup$
    – Markus A.
    May 26, 2015 at 22:20
  • $\begingroup$ 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. $\endgroup$
    – hardmath
    May 26, 2015 at 23:11

1 Answer 1

Reset to default
1
$\begingroup$

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)$.

$\endgroup$
6
  • $\begingroup$ 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? $\endgroup$
    – Markus A.
    May 26, 2015 at 22:30
  • $\begingroup$ To get z you can reduce y1 to the last byte and then use a lookup table. The multiplicative inverse is usually computed with the extended Euclidean algorithm. $\endgroup$
    – coproc
    May 27, 2015 at 9:50
  • $\begingroup$ 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? $\endgroup$
    – Markus A.
    May 27, 2015 at 17:19
  • $\begingroup$ Sorry... Meant to write ...$x_1$ could end up being a multiple of $256$... $x_2$ would be $0$ then. $\endgroup$
    – Markus A.
    May 27, 2015 at 17:57
  • $\begingroup$ 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$. $\endgroup$
    – coproc
    May 27, 2015 at 18:37

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .