1
$\begingroup$

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?

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ The question written seems to be very low in quality. Thanks for the explanation as you have added a lot of useful constraints missing from the original question, so now it makes much more sense. With what you explained, one comparison and one subtraction then are enough. $\endgroup$
    – Avv
    Oct 17 '21 at 19:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.