No post body was provided.
Algos in Plain English – Efficient Division Without Mult, Div, or Mod Operators
11–17 of 17 posts
Re: Algos in Plain English – Efficient Division Without Mult, Div, or Mod Operators
#12I 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 qui…
Very impressive.
Re: Algos in Plain English – Efficient Division Without Mult, Div, or Mod Operators
#13It 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…
[deleted]
Re: Algos in Plain English – Efficient Division Without Mult, Div, or Mod Operators
#14um... 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 i…
Perpetuating some programmer mystique that binary operators are somehow different when really they are the same algebraic operations but mod 2.
Re: Algos in Plain English – Efficient Division Without Mult, Div, or Mod Operators
#15This 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
I don't believe the article is using a binary search technique, but rather is indeed doing binary long division (it's not particularly succinct about it, though.)
It seems like a binary search would be logarithmic on the possible range of values, which for a fixed-size word is constant. Wouldn't you need a multiply, though? That would also be constant time complexity, but with a very large overhead.
Re: Algos in Plain English – Efficient Division Without Mult, Div, or Mod Operators
#16Earlier quoted context omitted.
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.
This is actually a common implementation for multiplication in the finite field GF(8), using 2x256 byte exp/log lookup tables.
Re: Algos in Plain English – Efficient Division Without Mult, Div, or Mod Operators
#17After 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