Cycle Detection: Floyd’s Algorithm: The Algorithm

[This page is auto-generated; please prefer to read the article’s PDF Form.]

The Algorithm

To be able to ﬁnd n and l, this algorithm ﬁrst ﬁnds out some element which belongs to the cycle. To ﬁnd such element, it observes that there must exist some integer t ≥ 1 such that e_t and e_2t are equal, i.e. have the same index. For e_t and e_2t to be equal, they both must belong to the cycle. That is:

Let us try to ﬁnd out more about such t. The index of e_t and e_2t are same iﬀ (due to (1)):

Due to (2), (3) and t ≥ 1, t is a positive multiple of n which is at least l. There are inﬁnitely many such t, but lets try to ﬁnd out the smallest of them. Now onward, we will simply use ‘t’ to denote this smallest t.

So we are looking for the smallest positive multiple of n, which is at least l. For the trivial case of l = 0, t is n. For l > 0 and n∣l, t is l.

Now consider the case of n ∤ l (which also implies l > 0). So, 0 < l mod n < n. Also, l − l mod n is a multiple of n. Hence the required t is: (l − l mod n) + n = l + n − l mod n.

For the case of l = 0 also, t = n can be written as l + n − l mod n. This reduces the number of cases we have to deal with while working with t. We can summarize our ﬁndings as:

Notice that t ≤ l + n always. We now understand how t relates to l and n, but these quantities are still unknown. To ﬁnd t and locate e_t, the algorithm works as follows.

It iterates over the possible values of t = 1,2,3,… while checking if the required t is reached, i.e. if e_t = e_2t. For that, it maintains two references (pointers) R₁ and R₂ at e_t and e_2t respectively, for the current t. When both R₁ and R₂ point to the same element e_t = e_2t, it knows that the required t is reached.

Below is an implementation of this algorithm in C. The above described part of this method will be referred as “Cycle-Searching” (the other two parts “Find n” and “Find l” will be discussed below). Whenever a reference R is updated to f(R), we will call it one “step” taken by R.

/* Parameter f is a function pointer.
   Output values of n and l are returned via pointers pn and pl.

   The elements e{i} are referred using type "void *". So,
   function f has input and output type as "void *". */

void floyd(void *e0, void* f(void*), int *pn, int *pl)
{
  void *R1, *R2, *R;
  int i, count, t, n, l;

  /***** Cycle-Searching *****/

  R1 = f(e0);
  R2 = f(f(e0));
  t = 1;

  /* loop-invariant: (R1 = e{t}) AND (R2 = e{2t}) */

  while(R1 != R2)
  {
    R1 = f(R1);
    R2 = f(f(R2));
    t++;
  }

  /* (R1 = R2), so (e{t} = e{2t}) holds */

  /***** Find n *****/

  R1 = f(R1);
  count = 1;

  while(R1 != R2)
  {
    R1 = f(R1);
    count++;
  }

  /* (R1 = e{t}) holds again */

  n = count;

  /***** Find l *****/

  R = e0;
  i = 0;

  while(i < t-n)
  {
    R = f(R);
    i = i + 1;
  }

  /* (R = e{t-n}) holds */

  count = 0;

  /* (R1 = e{t}) AND (R = e{t-n}) holds */

  while(R != R1)
  {
    R = f(R);
    R1 = f(R1);
    count++;
  }

  /* (R = R1 = e{l}) holds */

  l = (t-n) + count;

  *pn = n;
  *pl = l;
}