The Euclidean Division Algorithm in Rust.

The Euclidean division is a well-known method to divide two integers by each other and having the result split into a unique integer part and a unique remainder. In this short story we are going to look at how to implement this algorithm in Rust. But first let us consider some theory behind this division.

The proof of this proposition, as typical for inductive conclusions, actually provides us with an algorithm which we will implement next.

So, for given a the idea is to reduce the problem to a-1 or to use the result for a = 0.

Implementation:

The implementation is done in Rust. In case you need a little wrap-up, feel invited to this introduction.

// Produces a = m * b + r for b > 0 and returns (m, r).
pub fn divide(a: u64, b: u64) -> Result<(u64, u64), String> {
    if b == 0 {
        Err(String::from("Cannot divide by 0!"))
    } else if b > a {
        Ok((0, a))
    } else if a == 1 {
        Ok((1, 0))
    } else {
        match divide(a - 1, b) {
            Ok((m, r)) => {
                if r + 1 == b {
                    Ok((m + 1, 0))
                } else {
                    Ok((m, r + 1))
                }
            }
            Err(s) => Err(s),
        }
    }
}

This code resembles one to one the proof above and it is not hard to adapt the code to also work for negative a, b, i.e. i32, i64, ....

More interesting though is the way how to provide an implementation that supports u32, u64, u128 at the same time. A technique how to accomplish this, can be found here.

You can run the code in this playground.

Thank you for reading!