Algos in Plain English – Efficient Division Without Mult, Div, or Mod Operators
1–10 of 17 posts
Re: Algos in Plain English – Efficient Division Without Mult, Div, or Mod Operators
#2This 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.
Re: Algos in Plain English – Efficient Division Without Mult, Div, or Mod Operators
#3It 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
Re: Algos in Plain English – Efficient Division Without Mult, Div, or Mod Operators
#4um... 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.
Re: Algos in Plain English – Efficient Division Without Mult, Div, or Mod Operators
#5I 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
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
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.
Re: Algos in Plain English – Efficient Division Without Mult, Div, or Mod Operators
#6You might remove the use of multiplication at the end:
return max(min(answer * sign, MAX_INT), MIN_INT)Re: Algos in Plain English – Efficient Division Without Mult, Div, or Mod Operators
#7It 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…
Here’s another as valid as given in the post.
A/ b = exp(log(a) - log(b))
No multiplication or division!
Re: Algos in Plain English – Efficient Division Without Mult, Div, or Mod Operators
#8It 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…
Here’s another as valid as given in the post. A/ b = exp(log(a) - log(b)) No multiplication or division!
I think the implied context is "you're only allowed to use instructions that involve simpler circuitry than multiplication or division." Otherwise there's no point in asking the question.
Re: Algos in Plain English – Efficient Division Without Mult, Div, or Mod Operators
#9This 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]
Re: Algos in Plain English – Efficient Division Without Mult, Div, or Mod Operators
#10I 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).