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.

Answer 1

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

Answer 2

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