Implementing all the Algorithms - Day 2: Brent's Algorithm for Cycle Detection

It's day two of implementing all the algorithms. I figured that I'd get bored pretty soon if I just started to implement all the sorting algorithms in one go. To combat just focusing on one niche field of algorithms I headed to Wikipedias excellent list of algorithms to find some new inspiration.

To not get overwhelmed trying to find the best option, I just started at the top with Brent's algorithm.

Brent's algorithm

Brent's algorithm solves the problem of cycle detection. Given a finite set S, a function that maps S to itself, and a starting value x0, find the start and length of the first repeating sequence of elements.

This definition is maybe a bit dry and paraphrased from Wikipedia which does a much better job of explaining it anyways. But here is the code:

pub fn brents_cycle_detection<T: PartialEq, F: Fn(&T) -> T>(f: &F, x0: T) -> (usize, usize) {
    // if we have a cycle at first element, return immediately to avoid moving x0 to tortoise
    if f(&x0) == x0 {
        return (1, 0);
    }

    // initialize the values as if we had already run the loop once
    let mut power = 2;
    let mut lambda = 1;
    let mut hare = f(&f(&x0));
    let mut tortoise = f(&x0);

    while tortoise != hare {
        if power == lambda {
            tortoise = hare;
            power *= 2;
            lambda = 1;
            hare = f(&tortoise);
        } else {
            hare = f(&hare);
            lambda += 1;
        }
        
    }

    let mut tortoise = x0;
    let mut hare = f(&tortoise);
    for _ in 0..lambda - 1 {
        // decrease the range by one because we already "added" one to the hare to avoid moving x0
        hare = f(&hare)
    }

    let mut mu = 0;
    while tortoise != hare {
        tortoise = f(&tortoise);
        hare = f(&hare);
        mu += 1
    }

    (lambda, mu)
}

This code is pretty much directly adapted from the pseudocode Wikipedia article itself. The only minor changes I made, are to avoid cloning objects. To do so, I had to add an if at the top to check for the trivial case of the first x0 looping back to itself. With that out of the way, I could directly initialize the values for the first loop to reflect the state after having run the loop once already. I already had written this article halfway before I thought to do it that way. Before that, I did some horribly complicated version of the loop which you can see in the commit history if you're really interested.

Testing

Nothing special here. I started out with some very simple test cases and then later added a version that generated values for different iterations. Though the algorithm works for arbitrary functions I added a version that converts a HashMap into a function. Interestingly, in Scala, maps are actually functions and can be passed as such. Something that I find to be an incredibly elegant way to represent index operations.

Here is the code in Rust to turn HashMaps into functions:

pub fn hash_map_to_cyclic_function<T: Eq + Clone + Hash>(
    values: HashMap<T, T>,
) -> impl Fn(&Option<T>) -> Option<T> {
    move |xi: &Option<T>| {
        if let Some(value) = xi {
            let result = values.get(value)?;
            Some(result.clone())
        } else {
            None
        }
    }
}

And here is the code to iterate over various combinations of mu and lambda:

fn gen_test_hash(mu: usize, lambda: usize) -> HashMap<usize, usize> {
    let mut result = HashMap::new();
    for i in 0..mu {
        result.insert(i + 1, i + 2);
    }

    for i in mu..(mu + lambda - 1) {
        result.insert(i + 1, i + 2);
    }
    result.insert(mu + lambda, mu + 1);
    result
}

#[test]
fn iterate_different_vals_test() {
    for lambda in 1..20 {
        for mu in 0..20 {
            let hashvalues = gen_test_hash(mu, lambda);
            println!("{:?}", &hashvalues);
            let fun = hash_map_to_cyclic_function(hashvalues);
            assert_eq!(brents_cycle_detection(&fun, Some(1)), (lambda, mu));
        }
    }
}

Conclusion

It was fun, learning about an entirely new algorithm to solve a problem that I had never considered before. Additionally, I am surprised by how writing this article let me find a way to make the code more readable and logical. It makes me wonder how many times I wrote some piece of code much more complicated than it needed to be and then simply never looked at it again. It also makes me feel that from a mindset perspective there is a certain overlap between writing code and writing text.