Function nekolib::algo::tortoise_hare::cycle_mu_lambda

pub fn cycle_mu_lambda<T, F>(x0: T, f: F) -> (usize, usize)where
    T: Eq + Clone,
    F: Fn(T) -> T,

周期検出を行う。

与えられた $x_0$ と $f$ を用いて $x_i = f(x_{i-1})$ ($i > 0$) として 定義される列 $\{x_i\}_{i=0}^\infty$ の周期検出を行う。 $x_{\mu} = x_{\mu+\lambda}$ なる最小の $(\mu, \lambda)$ を返す。

Requirements

$f$ は参照透過である。

Notes

共通の $f$ に対して、異なる複数の $x_0$ から周期検出を行いたい場合は、 この関数を複数回呼ぶよりも高速なアルゴリズムがあると思われる。 ある $x_0$ での出力が $(\mu, \lambda)$ であれば、 $x_i$ ($1\le i< \mu$) での出力は $(\mu-i, \lambda)$、 $x_i$ ($\mu\le i<\mu+\lambda$) での出力は $(0, \lambda)$ とわかる。 さらに、これら $\mu+\lambda$ 個以外の $x'$ についても、 $f^i(x')$ がこれらのいずれかと等しくなる $i$ が存在すれば、 $\Theta(\mu)$ 回の $f$ の呼び出しで $x', f(x'), \dots, f^{i-1}(x')$ の出力もわかるはず。

Complexity

$\Theta(\mu+\lambda)$ 回の $f$ の呼び出しを行う。

Examples

use nekolib::algo::cycle_mu_lambda;

// 3, 9, 11, 9, 11, ...
assert_eq!(cycle_mu_lambda(3, |x| x * x % 14), (1, 2));
// 2, 6, 4, 5, 1, 3, 2, ...
assert_eq!(cycle_mu_lambda(2, |x| x * 3 % 7), (0, 6));

use nekolib::algo::cycle_mu_lambda;

assert_eq!(cycle_mu_lambda(0, |x| x), (0, 1));