Get rid of division in modulo

Question

I'm writing a program, that draws horizontal stripes and blank spaces between them with the same height 44.

So I made an inequality

$({{y}\over{44}}) \mod {2} < {1} $

The problem is I'm not allowed to use the division in this programming language.

Could you, please, help me to get rid of this division to make it giving me the same result.

Thanks in advance.

UPD: Sorry, I wasn't precise, I'm not allowed to use use even modulo, so I had to change it to this.

${{y} \over {44}} - {{{y} \over {44}} \over {2}} * 2 < 1 $

And this trick is working, because I can divide numbers by only powers of two.

UPD2: I changed the inequality to

${y} \mod {88} < {44} $

and transformed it to my case without modulo

${y} - {{y} \over {88}} * 88 < 44 $

but there is still division by number, which is not power of 2.

For these values, you can safely use $y-\Big\lfloor\dfrac{2979y}{2^{18}}\Big\rfloor\cdot88$. See my answer below for a detailed explanation. — barak manos, Dec 02 '15 at 07:09
@lhf: It is more likely a specific HW architecture, such as fixed-point processors (common among DSPs). — barak manos, Dec 02 '15 at 10:27

barak manos · Accepted Answer · 2015-12-02T09:39:02.567

You have $481$ possible values of $y\in[0,480]$.

So you can use a lookup table as follows:

LUT[481] =
{
    1,1,1,1 ... x 44 times
    0,0,0,0 ... x 44 times
    1,1,1,1 ... x 44 times
    0,0,0,0 ... x 44 times
    1,1,1,1 ... x 44 times
    0,0,0,0 ... x 44 times
    1,1,1,1 ... x 44 times
    0,0,0,0 ... x 44 times
    1,1,1,1 ... x 44 times
    0,0,0,0 ... x 44 times
    1,1,1,1 ... x 41 times
};

Then LUT[y] == 1 $\iff y\bmod88<44$.

Alternatively, you can rely on the following fact:

$$\frac{2^{5n+3}}{88}\approx\Big[\frac{2^{5n+3}}{88}\Big]$$

Therefore:

$$y-\Big\lfloor\frac{y}{88}\Big\rfloor\cdot88 \approx y-\Big\lfloor\frac{y\cdot\Big[\frac{2^{5n+3}}{88}\Big]}{2^{5n+3}}\Big\rfloor\cdot88$$

The larger value of $n$ that you choose, the higher accuracy that you get.

In your case, $n=3$ seems to yield perfect accuracy for all $y\in[0,480]$.

For $n=3$, we get $2^{5n+3}=2^{5\cdot3+3}=2^{18}=262144$.

So we calculate manually $\Big[\frac{262144}{88}\Big]=2979$.

And then we can finally use the formula:

$$y-\Big\lfloor\frac{y\cdot2979}{262144}\Big\rfloor\cdot88$$

It works! Thank you so much! – Ali_run Dec 02 '15 at 10:13 — Ali_run, Dec 02 '15 at 10:13

score 0 · Answer 2 · answered Dec 01 '15 at 15:08

0

Increment $y$ on every iteration; when it reaches $44$ toggle the stripe color and reset $y$ to $0$.

answered Dec 01 '15 at 15:08

Get rid of division in modulo

2 Answers2