6 ms·

Faster remainders when the divisor is a constant: beating compilers & libdivide

197 points by matt_d 8y ago

rurban 8y ago
Genius
StefanKarpinski 8y ago
It's astonishing that this method isn't previously widely known and used. It's so simple once you see it.
- vanderZwan 8y ago
  I wouldn't be surprised if some people had already thought of it while coming up with a fast quotient method, but didn't bother to do anything with it because they did not need a remainder.
IshKebab 8y ago
Clever. Is this possible with 64-bit numbers somehow?
- deleted 8y ago
  [deleted]
- bloomer 8y ago
  Yes, the paper is general and covers the case for arbitrary bit size. 64-bit would require a 128-bit approximate inverse in general and the multiplication during computing the mod would extend that out another 64-bits. So would require three registers and two more multiplications on x64 I think. Socidont think it gains you anything in the general case. Bit for some divisors it might beat the traditional Granlund-Montgomery-Warren method when you could use a smaller approximate inverse.
nathan_f77 8y ago
For this equation: n/d = n * (2^N/d) / (2^N) What is "N"? They didn't seem to explain that, although they say "Yet for N large enough", and "drop the least significant N bits". Is it just a very large integer? Or maybe the maximum integer for a certain number of bytes? EDIT: I'm reading this Wikipedia article: https://en.wikipedia.org/wiki/Division_algorithm#Division_by_a_constant https://en.wikipedia.org/wiki/Division_algorithm#Division_by... For a 32-bit unsigned integer, you would use N = 33 when dividing by 3? And N = 35 when dividing by 10? I'm struggling to see how this works. EDIT 2: I think this post helped me understand it: https://forums.parallax.com/discussion/114807/fast-faster-fastest-code-integer-division https://forums.parallax.com/discussion/114807/fast-faster-fa... "The·basic idea is to approximate the ratio (1/constant) by another rational number (numerator/denominator) with a power of two as the denominator." Their example: (n/10) = (n*205) >> 11 Maps to the original example: n/10 = n * (2^11 / 10) / (2^11) 2^11 / 10 = 2048 / 10 = 204.8, which rounds to 205. So N would be 11 in this example, but I guess it could be any value.
- deleted 8y ago
  [deleted]
- deleted 8y ago
  [deleted]
- deleted 8y ago
  [deleted]
- nkurz 8y ago
  The Wikipedia article seems to be using slightly different definitions. For the blog post, the actual article gives better definitions: https://arxiv.org/pdf/1902.01961.pdf https://arxiv.org/pdf/1902.01961.pdf. I'm one of the co-authors, and I believe that in our case, N is always equal to the maximum bitwidth of the numerator. So for a 32-bit integer, N=32. I'll see if Daniel can add some clarification to the blog post.
  - dlemire 8y ago
    (I am the author of the blog post and I am answering here at the request of nkurz.) So nkurz is correct that, in the paper, N is always equal to the maximum bitwidth of the numerator. I was not careful enough to make sure that the notation of the paper matches the notation of the blog post. So the N from the blog post is the F from the paper. I am sorry about this. I added the following footnote. "What is N? If both the numerator n and the divisor d are 32-bit unsigned integers, then you can pick N=64. This is not the smallest possible value. The smallest possible value is given by Algorithm 2 in our paper and it involves a bit of mathematics (note: the notation in my blog post differs from the paper, N becomes F)." To make it super simple, if you have 32-bit values, then pick N (from the blog post) to be 64 and you are all set. You can do better, but this requires knowing what the divisor is.
mjcohen 8y ago
"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=1549663765&s=Kindle+Store&sprefix=hackers+%2Caps%2C192&sr=1-1-catcorr https://www.amazon.com/Hackers-Delight-Henry-S-Warren-ebook/...) has a whole chapter on this. So, yes, it is well known.
- 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.
remcob 8y ago
This is very similar to Montgomery reduction [1]. Both do a multiply taking low bits followed by a multiply taking the high bits to reduce a number. Montgomery reduction requires an augmented number system with conversions to and from. The article's approach works on numbers directly, but if I understand it correctly the multiplications are twice the width. Are these two methods algebraically related? Would it be possible to get fastmod working without the double width? [1]: https://en.wikipedia.org/wiki/Montgomery_modular_multiplication#The_REDC_algorithm https://en.wikipedia.org/wiki/Montgomery_modular_multiplicat...
deleted 8y ago
[deleted]
hoseja 8y ago
> GNU GCC Compiler

197 points by matt_d 8y ago

rurban 8y ago

Genius

StefanKarpinski 8y ago

It's astonishing that this method isn't previously widely known and used. It's so simple once you see it.

vanderZwan 8y ago
I wouldn't be surprised if some people had already thought of it while coming up with a fast quotient method, but didn't bother to do anything with it because they did not need a remainder.

IshKebab 8y ago

Clever. Is this possible with 64-bit numbers somehow?

deleted 8y ago
[deleted]
bloomer 8y ago
Yes, the paper is general and covers the case for arbitrary bit size. 64-bit would require a 128-bit approximate inverse in general and the multiplication during computing the mod would extend that out another 64-bits. So would require three registers and two more multiplications on x64 I think. Socidont think it gains you anything in the general case. Bit for some divisors it might beat the traditional Granlund-Montgomery-Warren method when you could use a smaller approximate inverse.

nathan_f77 8y ago

For this equation: n/d = n * (2^N/d) / (2^N) What is "N"? They didn't seem to explain that, although they say "Yet for N large enough", and "drop the least significant N bits". Is it just a very large integer? Or maybe the maximum integer for a certain number of bytes? EDIT: I'm reading this Wikipedia article: https://en.wikipedia.org/wiki/Division_algorithm#Division_by_a_constant https://en.wikipedia.org/wiki/Division_algorithm#Division_by... For a 32-bit unsigned integer, you would use N = 33 when dividing by 3? And N = 35 when dividing by 10? I'm struggling to see how this works. EDIT 2: I think this post helped me understand it: https://forums.parallax.com/discussion/114807/fast-faster-fastest-code-integer-division https://forums.parallax.com/discussion/114807/fast-faster-fa... "The·basic idea is to approximate the ratio (1/constant) by another rational number (numerator/denominator) with a power of two as the denominator." Their example: (n/10) = (n*205) >> 11 Maps to the original example: n/10 = n * (2^11 / 10) / (2^11) 2^11 / 10 = 2048 / 10 = 204.8, which rounds to 205. So N would be 11 in this example, but I guess it could be any value.

deleted 8y ago
[deleted]
deleted 8y ago
[deleted]
deleted 8y ago
[deleted]
nkurz 8y ago
The Wikipedia article seems to be using slightly different definitions. For the blog post, the actual article gives better definitions: https://arxiv.org/pdf/1902.01961.pdf https://arxiv.org/pdf/1902.01961.pdf. I'm one of the co-authors, and I believe that in our case, N is always equal to the maximum bitwidth of the numerator. So for a 32-bit integer, N=32. I'll see if Daniel can add some clarification to the blog post.
- dlemire 8y ago
  (I am the author of the blog post and I am answering here at the request of nkurz.) So nkurz is correct that, in the paper, N is always equal to the maximum bitwidth of the numerator. I was not careful enough to make sure that the notation of the paper matches the notation of the blog post. So the N from the blog post is the F from the paper. I am sorry about this. I added the following footnote. "What is N? If both the numerator n and the divisor d are 32-bit unsigned integers, then you can pick N=64. This is not the smallest possible value. The smallest possible value is given by Algorithm 2 in our paper and it involves a bit of mathematics (note: the notation in my blog post differs from the paper, N becomes F)." To make it super simple, if you have 32-bit values, then pick N (from the blog post) to be 64 and you are all set. You can do better, but this requires knowing what the divisor is.

mjcohen 8y ago

"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=1549663765&s=Kindle+Store&sprefix=hackers+%2Caps%2C192&sr=1-1-catcorr https://www.amazon.com/Hackers-Delight-Henry-S-Warren-ebook/...) has a whole chapter on this. So, yes, it is well known.

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.

remcob 8y ago

This is very similar to Montgomery reduction [1]. Both do a multiply taking low bits followed by a multiply taking the high bits to reduce a number. Montgomery reduction requires an augmented number system with conversions to and from. The article's approach works on numbers directly, but if I understand it correctly the multiplications are twice the width. Are these two methods algebraically related? Would it be possible to get fastmod working without the double width? [1]: https://en.wikipedia.org/wiki/Montgomery_modular_multiplication#The_REDC_algorithm https://en.wikipedia.org/wiki/Montgomery_modular_multiplicat...

deleted 8y ago

[deleted]

hoseja 8y ago

> GNU GCC Compiler