0
$\begingroup$

I want to know exactly how many iterations it would take this algorithm to terminate. In other words, is there a closed-form solution for the number of iterations? (For my input values, it is always guaranteed to terminate.)

Let $x$, $y$, and $z$ be some positive integers. The values of $x$, $y$, and $z$ are chosen such that neither $y$ nor $z$ will become $\le 0$ before the loop terminates.

$\text{do}$

$\qquad \text{if } (x+y) \text{ mod } z = 0 \text{ then done}$

$\qquad x \leftarrow x + y$

$\qquad y \leftarrow y - 4$

$\qquad z \leftarrow z - 2$

$\text{loop}$

For example, if we let $x =184$, $y = 376$, and $z = 187$, this algorithm terminates in $19$ loops.

Here is a plot of $(x+y) \text{ mod } z$ for some real inputs. Here is another plot for larger inputs.

$\endgroup$
  • 1
    $\begingroup$ Of course you could say "whatever (x + y) modulo 0 is, it is not zero". In that case the loop runs forever if x is odd, y and z are even. $\endgroup$ – gnasher729 May 5 at 23:27
0
$\begingroup$

There might be no clean formula for that.

The values of $x,y,z$ after the $n$th iteration of the loop are $x_0 + (n+1) y_0 - 2n(n+1)$, $y_0 - 4n$, and $z_0 - 2n$, respectively, as can be verified by induction, where $x_0,y_0,z_0$ are their initial values (before the first iteration of the loop). The loop terminates for the smallest positive integer $n$ such that

$$x_0 + (n+1) y_0 - 2n(n+1) + y_0 - 4n \equiv 0 \pmod{z_0 - 2n}.$$

There might not be any nice expression for the smallest $n$ that satisfies that equation, in terms of $x_0,y_0,z_0$. It's also not obvious to me whether such an $n$ always exists, i.e., whether your loop will always terminate.


I'm glossing over a serious issue that you haven't addressed in the question: what is the meaning of $(x+y) \bmod z$ when $z=0$ or when $z<0$? It's not clear, and that will affect the answer.

$\endgroup$
  • $\begingroup$ $z$ will never be $\le 0$. The numbers are guaranteed to work by the way I've generated them, but I don't have time to explain the full problem. I'm just interested to know if there is a way to solve this kind of formula in general, or simply trying repeatedly is the only way. $\endgroup$ – EntangledLoops May 5 at 23:32
  • $\begingroup$ @EntangledLoops, From the text of the algorithm as you've described it, $z \le 0$ certainly can happen. For instance, suppose $x_0=1,y_0=100,z_0=2$. If there's something that prevents $z \le 0$, it's missing from the question -- and omitting relevant context makes it harder to provide a useful answer. We can only answer the question that was asked. $\endgroup$ – D.W. May 6 at 0:06
  • $\begingroup$ Yes you are correct, but what I'm saying is that $x$, $y$, and $z$ have been chosen by another algorithm that guarantees this won't happen. That's an invariant here. I'm hoping that knowing that up front will help, somehow. $\endgroup$ – EntangledLoops May 6 at 0:08
  • $\begingroup$ I added a plot to the original question to show the behavior under real inputs. The plots vary depending upon the input, but have some aesthetic similarity that I can't quantify. $\endgroup$ – EntangledLoops May 6 at 0:19
  • $\begingroup$ @EntangledLoops, that's fine, but please edit the question to state all relevant guarantees (such as that the initial values of $x,y,z$ are chosen so that the loop terminates before $z \le 0$; are there other guarantees?). $\endgroup$ – D.W. May 6 at 0:41

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.