[HN Gopher] Reverse-engineering a carry-lookahead adder in the P...
       ___________________________________________________________________
        
       Reverse-engineering a carry-lookahead adder in the Pentium
        
       Author : DamonHD
       Score  : 29 points
       Date   : 2025-01-18 18:53 UTC (4 hours ago)
        
 (HTM) web link (www.righto.com)
 (TXT) w3m dump (www.righto.com)
        
       | kens wrote:
       | Author here if anyone has questions about the obscure details of
       | Kogge-Stone adders :-)
        
         | kragen wrote:
         | Hmm, I thought you explained the FDIV bug was (in part) because
         | the Boron+ used carry-save adders to generate quotient digits?
         | I don't see how you'd combine carry-save adders and Kogge-Stone
         | carry lookahead. This post does mention the carry-save adder
         | and link the other post, but doesn't explain the relationship
         | between the two adders (are they the same in some galaxy-brain
         | way I can't imagine? does one of them feed the other?)
         | 
         | ______
         | 
         | + https://en.wikipedia.org/wiki/Systematic_element_name
        
           | kens wrote:
           | The short answer is that a large carry-save adder feeds into
           | this 8-bit carry-lookahead adder to generate the table index
           | for division. In more detail, the division algorithm uses a
           | [?]64-bit carry-save adder to hold the partial remainder
           | during a division. The problem is that a carry-save adder
           | holds the result in two pieces, the sum bits and the carry
           | bits, which is what makes it fast. However, the division
           | algorithm needs to use the top 7 bits as an index into the
           | infamous division table, but this won't work if the value is
           | in two pieces. The solution is to add the two pieces together
           | using the carry-lookahead adder and then you have the table
           | index.
           | 
           | The obvious question is why didn't they just use a carry-
           | lookahead adder in the first place? The answer is that a
           | carry-lookahead adder works better for smaller words (e.g. 8
           | bits), since its size is O(N^2) or O(N log N), depending on
           | how you implement it. So you're better off with a large
           | carry-save adder and a small carry-lookahead adder.
        
       ___________________________________________________________________
       (page generated 2025-01-18 23:00 UTC)