<ul>
<li>Given $f(x)$, I want to find $f^n(x)$ fast<ul>
<li>The domain and value range of f are common finite sets</li>
<li>The starting point x is a single</li>
<li>If the size of the definition region is D and the maximum value of n is N, then the pre-processing O(D) can be made into the main process O(1)</li>
</ul>
</li>
<li>pretreatment<ul>
<li>Prepare two arrays A and B</li>
<li>$A: f^i(x) \to i$</li>
<li>$B: i \to f^i(x)$</li>
<li>Fill this array by incrementing i</li>
<li>If Ai is not the initial value, it is a loop</li>
<li>Can be determined by constant order.</li>
<li>Worst case scenario, a loop is found by D</li>
</ul>
</li>
<li>main processing<ul>
<li>i, Ai to the loop and the length of the path and the length of the loop until it enters the loop.<ul>
<li>loop_start = Ai</li>
<li>loop_length = i - Ai</li>
</ul>
</li>
<li>Constant Order $f^n(x) = (n - A_i) % (i - A_i)$</li>
</ul>
</li>
</ul>
<hr>
<p>This page is auto-translated from <a href="https://scrapbox.io/nishio/%E3%83%AB%E3%83%BC%E3%83%97%E6%A4%9C%E5%87%BA">/nishio/ループ検出</a> using DeepL. If you looks something interesting but the auto-translated English is not good enough to understand it, feel free to let me know at <a href="https://twitter.com/nishio_en">@nishio_en</a>. I&#39;m very happy to spread my thought to non-Japanese readers.</p>


loop detection