Dividing Without Divide

June 25, 2019

Today’s task comes from a student programmer:

Given a numerator and divisor of unsigned integers, compute the quotient and remainder. You cannot use divide, cannot use mod, and you want to optimize for speed.

After a while, the student programmer looked up the official solution:

def divide_problem(num, div):
    quotient = 1
    while num - (quotient * div) >= div:
        print(num - (quotient * div), "loop")
        quotient += 1
    remainder = num - (quotient * div)
    return quotient, remainder

Your task is to comment on the official solution and write a better one. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Advertisements

Pages: 1 2

7 Responses to “Dividing Without Divide”

  1. Zack said

    I sure hope this “official solution” was not what was expected for the best possible solution to this! It’s unnecessary long and void of any creativity. Anyway, here is my take on this using Julia 1.0.2:

    function divide(n::Int64, d::Int64)
    q = floor(Int64, exp(log(n) – log(d)))
    r = n – q*d

    if r == d
        r = 0
        q += 1
    end
    
    return q, r # quotient, remainder
    

    end

    Thanks for the creatively challenging problem.

  2. Good try, but floor is a divide operation.

  3. Zack said

    @Pascal. I had no idea. Thank you for your feedback…

  4. Bill Wood said

    Simple Rust version without multiplication (faster):

    fn divide(mut num: usize, div: usize) -> (usize, usize) {
        let mut q = 0;
        while num >= div {
            num -= div;
            q += 1;
        }
        (q, num)
    }
    fn main() {
        dbg!(divide(120, 3));
        dbg!(divide(121, 3));
        dbg!(divide(1, 3));
    }
    

    Playground: https://play.rust-lang.org/?version=stable&mode=debug&edition=2018&gist=dc817f9b2d6eede71bc8f01565e00707

  5. Bill Wood said

    This recursive Rust version using the left shift operator is much faster than the above when the numerator is a big multiple of the divisor (5 times faster in the benchmark below vs the subtraction-based version above).

    fn divide(num: usize, div: usize) -> (usize, usize) {
        if num < div {
            (0, num)
        } else {
            let mut e = 0;
            while num >= (div << e + 1) {
                e += 1;
            }
            let (e2, r) = divide(num - (div << e), div);
            ((1 << e) + e2, r)
        }
    }
    
    fn main() {
        let mut sum: usize = 0; 
        for i in 0..100_000 {
            for j in 1..1_000 {
                sum += divide(i, j).0;
            }
        }
        println!("sum = {}", sum);
    }
    

    Playground https://play.rust-lang.org/?version=stable&mode=debug&edition=2018&gist=e9c9248bfa96af7662e68b01c6195a65

  6. Bill Wood said

    Sorry last post, non-recursive version is simpler and faster:

    fn divide(mut num: usize, div: usize) -> (usize, usize) {
        let mut q = 0;
        while num >= div {
            let mut e = 0;
            while num >= (div << e + 1) {
                e += 1;
            }
            q += 1 << e;
            num -= div << e;
        }
        (q, num)
    }
    
    fn main() {
        let mut sum: usize = 0;
        for i in 0..100_000 {
            for j in 1..1_000 {
                sum += divide(i, j).0;
            }
        }
        println!("sum = {}", sum);
    }
    

    Playground: https://play.rust-lang.org/?version=stable&mode=debug&edition=2018&gist=71ce4d75d6b16522c3cf8edbbc6b5518

  7. Mike said

    There are at least 2 problems with the “official” solution:

    It gives an incorrect answer if div > num. For example, divide_problem(3,5) returns quotient = 1 with remainder = -2.
    It runs as O(quotient). E.g., for divide_problem(100,3) the loop runs 33 times.

    This recursive Python solution runs as O(log2(quotient)):

    def divide_problem(n, d):
        if d > n:
            return 0, n
        
        else:
            q,r = divide_problem(n, 2*d)
            
            if d <= r:
                return 2*q+1, r-d
            
            else:
                return 2*q, r
    

    Or, as an iterative version:

    def divide_problem2(n, d):
        f = d
        while f < n:
            f <<= 1
        
        q = 0
        while f >= d:
            if f <= n:
                q = 2*q + 1
                n -= f
            else:
                q = 2*q
                
            f >>= 1
            
        return q, n
    

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: