4 ms·

"Hacker's Delight" (https://www.amazon.com/Hackers-Delight-Henry-S-Warren-ebook/dp/B009GMUMTM/ref=sr_1_1?crid=M9M472NU7BWX&keywords=hackers+delight&qid=15496637

• kbenson 8y ago
  As noted by the article in question: The idea is not novel and goes back to at least 1973 (Jacobsohn). However, engineering matters because computer registers have finite number of bits, and multiplications can overflow. I believe that, historically, this was first introduced into a major compiler (the GNU GCC compiler) by Granlund and Montgomery (1994). While GNU GCC and the Go compiler still rely on the approach developed by Granlund and Montgomery, other compilers like LLVM’s clang use a slightly improved version described by Warren in his book Hacker’s Delight.
  • bonzini 8y ago
    The second edition of Hacker's Delight does have a section on "Testing for zero reminders after division by a constant", but it uses the multiplicative inverse.
• yorwba 8y ago
  The article mentions the book and that the method presented therein is used by clang for faster division. The novel part is to adapt the method for faster remainders without calculating the quotient first.
• Iwan-Zotow 8y ago
  see also https://math.stackexchange.com/questions/1251327/is-there-a-fast-divisibility-check-for-a-fixed-divisor https://math.stackexchange.com/questions/1251327/is-there-a-...
  • acqq 8y ago
    Nice! If I'm not wrong, under many conditions this derivation gives even faster divisibility test then the one presented in the article we comment.