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

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.