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.

Advertisements

Pages: 1 2

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: