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

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

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

Playground https://play.rust-lang.org/?version=stable&mode=debug&edition=2018&gist=e9c9248bfa96af7662e68b01c6195a65

Sorry last post, non-recursive version is simpler and faster:

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

Or, as an iterative version:

Here’s a solution in Python.