Dividing Without Divide

June 25, 2019

We write in Python because the original question specified Python.

The official solution is just an inefficient implementation of repeated subtraction that replaces a simple subtraction with a more-complicated multiplication; if you’re going to use repeated subtraction, you should at least get rid of the multiplication:

def divide(num, div):
    quot = 0
    while div <= num:
        quot += 1
        num -= div
    return quot, num

Repeated subtraction is not “optimized for speed,” as you will see if you call divide(1000000000,3). We could instead use repeated subtraction of squares of the divisor, or squares of squares of the divisor, or …, going on until the square of the square of the … divisor exceeds the number. As an example, consider the problem divide(1000000000,3) mentioned above. We first make a list of squares:

3 * 3 = 9
9 * 9 = 81
81 * 81 = 6561
6561 * 6561 = 43046721

And we stop there because the next squaring exceeds the target. Now we call the naive divide-by-repeated-subtraction algorithm repeatedly on each remainder:

divide(1000000000, 43046721) = (23, 9925417)
divide(9925417, 6561) = (1512, 5185)
divide(5185, 81) = (64, 1)
divide(1, 9) = (0, 1)
divide(1, 3) = (0, 1)

The final remainder is 1. The quotient is:

0*3/3 + 0*9/3 + 64*81/3 + 1512*6561/3 + 23*43046721/3 = 333333333

and we performed only 23 + 1512 + 64 = 1599 subtractions instead of the 333,333,333 subtractions of the official solution. Here’s the code:

def divide(num, div):
    divs, sqs, sum = [div], [1], 0
    while divs[-1] * divs[-1] < num:
        divs.append(divs[-1] * divs[-1])
        sqs.append(sqs[-1] * sqs[-1] * div)
    while divs:
        div, sq = divs.pop(), sqs.pop()
        quot = 0
        while div <= num:
            quot += 1
            num -= div
        sum += (quot * sq)
    return sum, num

The first while computes and stacks the squares, and also each of the squares divided by div. After the first while, the divs and sqs stacks look like this:

divs = [3, 9, 81, 6561, 43046721]
sqs  = [1, 3, 27, 2187, 14348907]

The second while repeatedly pops the two stacks, performs the naive divide-by-repeated-subtraction algorithm, and accumulates the sum. That’s very much faster than the official solution, and not much more complicated.

You can run the program at https://ideone.com/CgVT1i.

Posted by programmingpraxis

Filed in Exercises

8 Comments »

8 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

Daniel said

August 16, 2019 at 12:23 AM

Here’s a solution in Python.

def divmod_(n, d):
    q = 0
    while n >= d:
        q_ = 1
        d_ = d
        while d_ << 1 <= n:
            q_ <<= 1
            d_ <<= 1
        q += q_
        n -= d_
    return q, n

for x in range(20):
    assert divmod(x, 10) == divmod_(x, 10)
    if x > 0:
        assert divmod(10, x) == divmod_(10, x)

Programming Praxis