Labor of Division: Algorithm D

Re:Labor of Division: Algorithm D by spenczar5 on Wednesday May 05, 2021 @05:38PM (#27056141)

> 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”?

[ Parent | on HN ]

Re:Labor of Division: Algorithm D by _Microft on Thursday May 06, 2021 @03:31AM (#27060165)

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.

[ Parent | on HN ]