1.7.3 Iterated Function Cycle Detection

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147

/*

Given a function $f$ mapping a finite set to itself and a starting value $x_0$, return the entry
value, position, and length of the cycle reached by repeatedly applying $f$. Formally, the sequence
$x_0$, $x_1 = f(x_0)$, $x_2 = f(x_1)$, $\ldots$, $x_n = f(x_{n - 1})$, $\ldots$ must eventually
repeat some value. If $x_i = x_j$ for $i < j$, then the sequence from $x_i$ to $x_{j - 1}$ repeats
forever. This is useful for detecting cycles in functional graphs (see 4.2.9), pseudo-random
generators, Pollard rho style algorithms, degenerate linked lists, and arrays where each index
points to the next index. For example, if an array $a_0, \ldots, a_{n+1}$ contains only values in
$[1, n]$, with exactly one value occurring more than once, then $f(i) = a_i$ forms a functional
graph; the duplicate value is the entry point of the cycle reached from $0$.

Floyd's cycle-finding algorithm, a.k.a. the "tortoise and the hare algorithm", is a space-efficient
default choice: it moves two pointers through the sequence at different speeds, finds a meeting
point inside the cycle, then locates the cycle start. Brent's algorithm is a compact variant that
usually calls $f$ fewer times by only resetting the tortoise at powers of two; prefer it when
evaluating $f$ is expensive and constant factors matter. In the detection phase, Brent advances one
pointer with one call to $f$ per step, while Floyd advances the tortoise once and the hare twice,
using three calls to $f$ per step.

For Floyd's algorithm, suppose the tail has length $m$ and the cycle has length $n$. At a meeting,
the hare has traveled twice as far as the tortoise, so the tortoise's distance is a multiple of $n$.
Consequently, the distance from the meeting point around the cycle to its entry is congruent to $m$
modulo $n$. Resetting one pointer to $x_0$ and advancing both one step at a time makes them meet at
the cycle entry after $m$ steps. Brent first determines $n$, then advances one pointer $n$ steps;
moving both together from that fixed separation likewise makes them meet at the entry.

- `find_cycle_floyd(f, x0)` repeatedly applies `f` starting from `x0` and returns the reached cycle
  as a tuple (`entry`, `start`, `length`), where `entry` is the first cycle value, `start` is its
  index in the sequence, and `length` is the number of distinct values in the cycle.
- `find_cycle_brent(f, x0)` does the same with fewer calls to `f` in many cases.

Time Complexity:
- O(m + n) per call, where $m$ is the first index in the cycle and $n$ is the cycle length.

Space Complexity:
- O(1) auxiliary.

*/

#include <tuple>

template<typename Fn, typename T>
std::tuple<T, int, int> find_cycle_floyd(Fn f, T x0) {
  // Find a meeting point inside the cycle.
  T tortoise = f(x0), hare = f(f(x0));
  while (tortoise != hare) {
    tortoise = f(tortoise);
    hare = f(f(hare));
  }
  // Find the cycle entry.
  int start = 0;
  tortoise = x0;
  while (tortoise != hare) {
    tortoise = f(tortoise);
    hare = f(hare);
    start++;
  }
  // Measure the cycle length.
  int length = 1;
  hare = f(tortoise);
  while (tortoise != hare) {
    hare = f(hare);
    length++;
  }
  return {tortoise, start, length};
}

template<typename Fn, typename T>
std::tuple<T, int, int> find_cycle_brent(Fn f, T x0) {
  // Find the cycle length by doubling the search block.
  int power = 1, length = 1;
  T tortoise = x0, hare = f(x0);
  while (tortoise != hare) {
    if (power == length) {
      tortoise = hare;
      power *= 2;
      length = 0;
    }
    hare = f(hare);
    length++;
  }
  // Separate the pointers by one cycle length.
  hare = x0;
  for (int i = 0; i < length; i++) {
    hare = f(hare);
  }
  // Find the cycle entry.
  int start = 0;
  tortoise = x0;
  while (tortoise != hare) {
    tortoise = f(tortoise);
    hare = f(hare);
    start++;
  }
  return {tortoise, start, length};
}

/*** Example Usage ***/

#include <cassert>
#include <set>
#include <vector>
using namespace std;

int f(int x) {
  return (123 * x * x + 4567890) % 1337;
}

void verify(int x0, int start, int length) {
  set<int> s;
  int x = x0;
  for (int i = 0; i < start; i++) {
    assert(!s.count(x));
    s.insert(x);
    x = f(x);
  }
  int startx = x;
  s.clear();
  for (int i = 0; i < length; i++) {
    assert(!s.count(x));
    s.insert(x);
    x = f(x);
  }
  assert(startx == x);
}

// Given n + 1 integers within [1, n], where one value in [1, n] is present 2 or more times (but
// other values in [1, n] are present at most once), find the duplicate without modifying the array.
// Interpret each value as a pointer to the next index; the duplicate is the cycle entry.
int find_duplicate_integer(const vector<int> &a) {
  return get<0>(find_cycle_floyd([&](int i) { return a[i]; }, 0));
}

int main() {
  int x0 = 0;
  auto [floyd_entry, floyd_start, floyd_len] = find_cycle_floyd(f, x0);
  assert(floyd_start == 4 && floyd_len == 2);
  verify(x0, floyd_start, floyd_len);

  auto [brent_entry, brent_start, brent_len] = find_cycle_brent(f, x0);
  assert(brent_entry == floyd_entry && brent_start == floyd_start && brent_len == floyd_len);

  assert(find_duplicate_integer({1, 3, 4, 2, 2}) == 2);
  assert(find_duplicate_integer({3, 1, 3, 4, 2}) == 3);
  return 0;
}