Labor of Division: Algorithm D

ridiculousfish.com

30 points·mpweiher··5 comments

> This is the general irreducible step in long division: if our divisor is N digits, we must work in N+1 digit chunks from the dividend. So our simplified problem is to compute q=⌊n/d⌋, where n has exactly one more digit than d, and q is a single digit.

I don’t understand. Isn’t it possible for n to have the same number of digits as well? For example n=75, d=11. Or, if you like, computing 755 / 11: the problem reduces to computing 75 / 11 first. Why “exactly one more”?

This quote is followed by "If q were not a single digit, then we peeled off too much of the dividend; back up one digit and try again."

q would be larger than one digit with certainty if we were working with chunks of size N+x (with x >= 2). N digits do not necessarily suffice, so N+1 is it, with the caveat that sometimes we have to drop back to the case of just N digits because q turned out to be longer than one digit.

My recollection is that implementing this algorithm is fraught with peril: Some very smart people have coded it with mistakes that only appear for rare bit patterns.

I think that I shall never envision

An op unlovely as division

An op whose answer must be guessed

And then, through multiply, assessed;

An op for which we dearly pay,

In cycles wasted every day.

Division code is often hairy;

Long division's downright scary.

The proofs can overtax your brain,

The ceiling and floor may drive you insane.

Good code to divide takes a Knuthian hero

But even God can't divide by zero!

-- Henry S. Warren Jr.

Hacker's Delight

At the very bottom of the subsequent post [1], is it really possible for the second `qhat` (i.e. `q0`) to be off by 2? Any examples of that?

[1] https://ridiculousfish.com/blog/posts/labor-of-division-epis...

Reply on news.ycombinator.com