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

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