3 ms·

Labor of Division: Algorithm D

• oxxoxoxooo 6y ago
  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-episode-v.html https://ridiculousfish.com/blog/posts/labor-of-division-epis...
• Syzygies 6y ago
  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.
  • oxxoxoxooo 6y ago
    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
• spenczar5 6y ago
  > 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”?
  • _Microft 6y ago
    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.