RFC: Provide "partial" cycle‐finding (skip minimal μ computation)

[rafl]

In many practical applications, the exact length $\mu$ of the non-cyclic prefix of a cyclic function really doesn't matter, and having to re-traverse the sequence again only to find that value is a waste of resources, especially if the function under iteration is expensive.

It's very often sufficient to provide only an upper bound $\tilde{\mu}$ somewhere within the first cycle. For example, this still allows one to compute $f^{10^{100}}(x)$ or similar without having to wait longer than the current age of the universe.

This is technically also true for $\lambda$, where some multiple $\tilde{\lambda}=k\lambda$ is also perfectly fine in practice, but most if not all cycle finding algorithms one would use in practice (Brent, Nivash, etc - not Floyd) find the minimal $\lambda$ directly anyway, so it's less of an issue there.

If a minimal $\mu$ is actually needed, it can be easily computed from just $\lambda$.

I'd be happy to create a pull-request to somehow expose an interface to find cycles without the need compute the minimal $\mu$, but it seemed better to first ask how you think this should best be done.

Would we perhaps want to change the existing cycle finding functions to provide a $\tilde{\mu}$ rather than $\mu$ and provide some convenient way of finding $\mu$ from $\lambda$ (maybe something like minimal_mu(brent, x0, f) or minimal_mu(lambda, x0, f) or similar)?

Should we instead expose new functions, say, brent_partial and floyd_partial, which only compute a $\tilde{\mu}$ and implement brent and floyd in terms of those with an additional step to find $\mu$ from $\lambda$?

Maybe something else entirely would be preferable?

For context, this issue/question is motivated by my desire to add a new cycle finding algorithm (Nivash, both non-partitioned and partitioned) which can outperform Brent (and therefore Floyd) in many practical cases at the expense of logarithmic rather than constant memory usage, as well as a convenience helper to compute $f^n(x)$ for large $n$ via

$$f^n(x) = \begin{cases} f^n(x) & \text{if } n < \mu, \\ f^{\mu + ((n - \mu) \bmod \lambda)}(x) & \text{if } n \ge \mu. \end{cases}$$

An implementation of Nivash would be less practical in some cases if it needed to compute the minimal $\mu$, and the same is true for the above approach for fast function exponentiation even in cases where Brent is more practical than Nivash.

Your feedback on how to best fit these new features into the existing library would be much appreciated.

Thanks!

[samueltardieu]

Would we perhaps want to change the existing cycle finding functions to provide a μ ~ rather than μ and provide some convenient way of finding μ from λ (maybe something like minimal_mu(brent, x0, f) or minimal_mu(lambda, x0, f) or similar)?

I would prefer to not change the API, as programs already depend on it.

Should we instead expose new functions, say, brent_partial and floyd_partial, which only compute a μ ~ and implement brent and floyd in terms of those with an additional step to find μ from λ ?

That looks promising, provided that the performances of the brent and floyd methods don't degrade too much by doing so.

[samueltardieu]

What do you think of #706? I've been wanting to try AI on some coding tasks, and as you can see it took suite a few iterations until it got it working.