Programming Praxis

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