Replacing the moduleo operation with occasional subtraction and one comparison

Question

Suppose we have the following equation:

$$k_{i + 1} = (k_i + 2i + 1) \bmod{n}, \quad k_0=k, \quad i\ge 0$$

Show how we can we replace the mod with one comparison and occasional subtraction.

Attempt: I understood elsewhere that occasional here doesn't mean one subtraction. So, to replace modulo, the only way that I understood it is to keep subtracting $k_{i + 1} $ from $n$, but that means we should keep checking if it's less than $n$ or not each time, so we violate as I see it the one comparison limit if I am not wrong. Second, we are supposed to step once we get the comparison false, which will give a number between $[0, n-1]$ same as $\bmod$ would do? What do you think please?

Answer 1

Since $0 \leq k_i < n$, as long as $i$ is not too large, we will have $0 \leq k_i + 2i+1 < 2n$. Therefore you can compute the modulo by checking whether $k_i+2i+1 \geq n$, and if so, subtracting $n$.

This works as long as $(n-1) + (2i+1) < 2n$, that is, as long as $i < n/2$. Usually $n$ is very large, and so we are never going to perform $n/2$ many iterations.