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.

Advertisements

Pages: 1 2

8 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
    
  8. Daniel said

    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)
    

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: