Algos in Plain English – Efficient Division Without Mult, Div, or Mod Operators

I came up with a cute algorithm for arbitrary division with repeated shifts when working on one of my earlier projects, which was an emulator for a trinary computer (where obviously dividing by 3 was a thing of import).

A recursive expression is derived like this

  1     1      b-a
 --- - --- =  ----
  a     b      a b

  1     1    (b-a)  1
 --- = --- + ----- ---
  a     b      b    a

If you select 1/b to be nearby a power of your base, this recursive relationship can be expanded until you get adequate precision.

e.g. to express 1/7 in terms of divisions by 8 (i.e. binary shifts by 3)

  1   1        1
  - = - ( 1 + ---)
  7   8        7

  1   1    1        1   
  - = - + --- (1 + ---) 
  7   8    64       7

  1   1    1     1         1
  - = - + --- + --- ( 1 + --- )
  7   8    64   512        7

So you get v/7 = v>>3 + v>>6 + v>>9 + v>>12 + ... (mind the carry). You sometimes end up needing to do some multiplication too but usually b can be chosen to make the problem a series of trivial operations.

Good expression to be able to derive in case you need to rebuild humanity from a box of nand gates.

Thanks for coming to my TED talk.

I have my own crazy solution to the division problem: https://www.specbranch.com/posts/faster-div8/

This is actually faster than DIV on old architectures, but there are lots of reasons why you shouldn't use it (code cache pollution and pipeline congestion).

I have been working on combining my initial 8-bit precision guess with a few rounds of Goldschmidt division to compete with 64-bit DIV, but I am currently not quite beating Intel (I have 40 cycle latency and 55 cycle recip throughput, compared to 30 and 21 on Haswell).

um... I would have written this same article with the exact opposite slant,

Algos in Plain English – Mult, Div, and Mod make for Efficient Division

The "binary intuition" is that "what you already know from grade school about multiplying and dividing numbers the long way on paper, by lining up and shifting columns of numbers, is even easier in binary because shifting is multiplication and binary only has a 1 or a 0 in every place.

I just think it's a little wrong to say "we're not mulitplying" when we are. And when you use Mult, Div, and Mod operators, that's what they do.

It seems a little funny to say you can't use multiplication or division operators, but then use shift operators to do multiplication and division. Also, the suggested solution uses a `*` in the final return...

It seems like you could instead use addition of a value with itself for the multiplication by 2, and it seems like there isn't any inherent need to divide by 2.

Here's my submission (set to expire after a month). https://pastebin.com/mgvGakLL

This was a great read! I hope you keep up the "Algos in Plain English" series. Its' a great idea. I also enjoyed the one on KMP. I also thought that was well written.

This used to be my go-to interview question, and the binary search option provided is a good solution.

It's possible to do it in constant time for a fixed-size word by using binary long-division too.

Then there's all the crazy solutions that CPUs use to implement division, like Newton-Raphson and Goldschmidt. [1]

[1] https://en.wikipedia.org/wiki/Division_algorithm

After reading the title of the article, I tried to solve it for fun before looking up the solution.

The logic followed what I learned at school about how to do it the long way, but of course with binary numbers it's so much easier.

I ended up with a shorter implementation that follows the same idea, but uses recursion [1]. The recursion is compiled away by Rust [2]

[1] https://play.rust-lang.org/?version=stable&mode=debug&editio... [2] https://godbolt.org/z/bq3fnrE4h

You might remove the use of multiplication at the end:

    return max(min(answer * sign, MAX_INT), MIN_INT)