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