; length of a cycle
(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)
(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))))))))
(call-with-values
(lambda () (floyd f 2))
(lambda (lam mu)
(display lam) (newline)
(display mu) (newline)))
(display counter) (newline)
(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)
(call-with-values
(lambda () (brent f 2))
(lambda (lam mu)
(display lam) (newline)
(display mu) (newline)))
(display counter) (newline)