## 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], , 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.

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

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));
}
```
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);
}
```
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);
}
```
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)
```