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.
Programming Praxis 
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
end
Thanks for the creatively challenging problem.
Good try, but floor is a divide operation.
@Pascal. I had no idea. Thank you for your feedback…
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
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
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
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, rOr, 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, nHere’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)