[HN Gopher] Labor of Division: Algorithm D
       ___________________________________________________________________
        
       Labor of Division: Algorithm D
        
       Author : mpweiher
       Score  : 24 points
       Date   : 2021-05-04 13:28 UTC (1 days ago)
        
 (HTM) web link (ridiculousfish.com)
 (TXT) w3m dump (ridiculousfish.com)
        
       | spenczar5 wrote:
       | > 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"?
        
       | oxxoxoxooo wrote:
       | 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...
        
       | Syzygies wrote:
       | 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 wrote:
         | 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
        
       ___________________________________________________________________
       (page generated 2021-05-05 23:01 UTC)