3 ms·
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
by arcticbull 4y ago
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 https://en.wikipedia.org/wiki/Division_algorithm
- sgtnoodle 4y agoI 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.