2 ms·

as with everything written about division there are a host of mistakes. :) i'm still wondering what the "out by 2 case" is for algorithm D... most notably for

as with everything written about division there are a host of mistakes. :) i'm still wondering what the "out by 2 case" is for algorithm D... most notably for 'word-size' remainders the compiler most certainly does not evaluate the division then work out the remainder... it comes all in one on hardware for the simple and most common case, and not far off it for the multi-word numbers stuff like GMP use (with single word divisor) - even stuff like "algorithm D" keeps track of a remainder as it goes (as any long division algorithm must). the find is interesting though. its pleasant to see these kinds of problems continue to see improvement to the solutions available. i was completely expecting yet another "find some inverse" trick.

minitech 5y ago
What is "out by 2 case" quoting? > most notably for 'word-size' remainders the compiler most certainly does not evaluate the division then work out the remainder I guess you're referring to this part of the article: > How do compilers compute the remainder? They first compute the quotient n/d and then they multiply it by the divisor, and subtract all of that from the original value (using the identity n % d = n - (n/d) * d). but the article is correct and is talking about constant divisors and the multiplication-by-inverse optimization here. For example, num % 5 on x86-64 gcc 11.2 -Ofast: foo(int): movsx rax, edi mov edx, edi imul rax, rax, 1717986919 sar edx, 31 sar rax, 33 sub eax, edx lea edx, [rax+rax*4] mov eax, edi sub eax, edx ret