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.