Brandon.Si(mmons)

my code, art and projects

Cycle Detection

The Algorithm

We can use Brent’s Algorithm to detect infinitely-repeating sequences in a list of values generated by some iterated function: that is, any list in which the next value in the sequence is generated from the previous value alone; if we find duplicate values in the list, we know we have a cycle.

The implementation below isn’t particularly elegant, and since I want to use it as a stand-alone tool I’m having it output strings:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

module Main
    where

cycling :: (Show a, Eq a) => Int -> [a] -> String
cycling k [] = "Empty list"
cycling k (a:as) = find 0 a 1 2 as
    where find _ _ c _ [] = "reached end at " ++ show c ++": no cycles"
          find i x c p (x':xs)
                | c > k = "no cycles after " ++ show k
                | x == x' = "cycle at "++ show c ++": "++(show$take (c-i) xs)
                | c == p = find c x' (c+1) (p*2) xs
                | otherwise = find i x (c+1) p xs

--- SOME RANDOM NUMBER GENERATORS TO TEST ---  
-- bad generators?:  
g1 = 0 : [ (g*7 + 1) `mod` 32 | g <- g1]
g2 = 17 : [ (g*22 + 221) `mod` 2^32 | g <- g2]
g3 = 3249 : [ (g*22695477 + 1) `mod` 300 | g <- g3]
g4 = 234587 : [ (g*22695476 + 1) `mod` 2^32 | g <- g4]

-- good generators:  
g5 = 294587 : [ (g*22695477 + 1) `mod` 2^32 | g <- g5]
g6 = 0 : [ (g*22695477 + 1) `mod` 2^32 | g <- g6]

Randomness is hard…

Linear Congruential Generator’s are notoriously easy to screw up with the wrong parameters. Let’s use our function to test just how finicky this RNG algorithm can be. random stream g4 is almost identical to g5, a known-good generator. Let’s compare the two with a cut off limit of 999,999. First the good:

1
2

*Main> cycling 999999 g5
    "no cycles after 999999"

Great, now let’s see how our typo-ed generator fares:

1
2

*Main> cycling 999999 g4
    "cycle at 17: [180790021]"

… yikes.

Comments