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.

7 Responses to “Dividing Without Divide”

Zack said
June 25, 2019 at 9:33 AM
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.
Pascal Bourguignon (@ogamita) said
June 25, 2019 at 10:30 AM
Good try, but floor is a divide operation.
Zack said
June 25, 2019 at 11:05 AM
@Pascal. I had no idea. Thank you for your feedback…

Bill Wood said

June 25, 2019 at 2:21 PM

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

Bill Wood said

June 25, 2019 at 6:20 PM

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

Bill Wood said

June 25, 2019 at 6:54 PM

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

Mike said

June 25, 2019 at 8:55 PM

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

Programming Praxis