## Length Of A Cycle

### July 21, 2017

We will be following the Wikipedia article on cycle detection. As at Wikipedia, we begin with a function that produces a cycle; variable `counter` increments with each calculation of the function, so we can compare the two algorithms:

```(define (f n)
(set! counter (+ counter 1))
(case n
((0 1) 6)
((2 8) 0)
((3)   1)
((4 7) 4)
((5 6) 3)))```
`(define counter 0)`

There are two cycles in this function: starting at 4 or 7 leads to a cycle of length 1 (4), and starting at any other number from 0 to 9 inclusive leads to a cycle of length 3 (6, 3, 1). Here is Floyd’s tortoise-and-hare algorithm:

```(define (floyd f x0)
(let loop ((tortoise (f x0)) (hare (f (f x0))))
(if (not (= tortoise hare))
(loop (f tortoise) (f (f hare)))
(let loop ((mu 0) (tortoise x0) (hare hare))
(if (not (= tortoise hare))
(loop (+ mu 1) (f tortoise) (f hare))
(let loop ((lam 1) (hare (f tortoise)))
(if (not (= tortoise hare))
(loop (+ lam 1) (f hare))
(values lam mu))))))))```
```> (floyd f 2)
3
2
> counter
16```

It correctly identifies the cycle length of 3 starting at list item 2 (indexing starts at 0), using 16 calls to `f`. Here is Brent’s power-of-two algorithm:

```(define (brent f x0)
(let loop ((power 1) (lam 1) (tortoise x0) (hare (f x0)))
(if (not (= tortoise hare))
(if (= power lam)
(loop (* power 2) 1 hare (f hare))
(loop power (+ lam 1) tortoise (f hare)))
(let loop ((i 0) (hare x0))
(if (< i lam)
(loop (+ i 1) (f hare))
(let loop ((mu 0) (tortoise x0) (hare hare))
(if (not (= tortoise hare))
(loop (+ mu 1) (f tortoise) (f hare))
(values lam mu))))))))```
```> (set! counter 0)
> (brent f 2)
3
2
> counter
13```

This algorithm also correctly identifies the cycle, but takes only 13 calls to `f`. As Brent promises, it is more efficient than Floyd’s algorithm.

You can run both programs at http://ideone.com/3z8ycq.

Pages: 1 2