4 ms·

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 leas

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.
  - mzs 8y ago
    I have not used it in many years, but I have foggy memory of IBM's Power cpu compiler doing similar trick for remainder.
mark-r 8y ago
I recently discovered that x/10 == (x*103)>>10 for the numbers 0-99. Helped speed up something I was working on. The compiler generated a similar multiply/shift for x/10, but mine was faster since it didn't need to work for all possible values of x.
- saagarjha 8y ago
  Does a multiply/shift pair take a different amount of time based on the operands? Otherwise, I don't see how this would make a difference.
  - bdonlan 8y ago
    The compiler has to assume that your operands might be large enough that they would overflow after a straight multiply.
    - saagarjha 8y ago
      As acqq/I have mentioned below, there are ways of telling the compiler that the overflow can't multiply so it can freely optimize these away.
  - nitrogen 8y ago
    It's conceivable that multiplication time might be proportional to the number of 1 bits in the multiplier.
  - mark-r 8y ago
    My code was two instructions: imul eax,ecx,67h sar eax,0Ah. The compiler generated code was mov eax,66666667h imul ecx sar edx,2 mov eax,edx shr eax,1Fh add eax,edx.
    - acqq 8y ago
      When input unsigned but before if < 99, output unsigned int: clang 7 mov ecx, edi mov eax, 3435973837 imul rax, rcx shr rax, 35 gcc 8.2 mov eax, edi mov edx, -858993459 mul edx mov eax, edx shr eax, 3 msvc 19 mov eax, -858993459 ; cccccccdH mul edx shr edx, 3 mov eax, edx icc 19 mov eax, 1717986919 imul edx sar edx, 2 mov eax, edx The same, but when input unsigned char: clang 7 movzx eax, dil imul eax, eax, 205 shr eax, 11 gcc 8.2 movzx edi, dil lea eax, [rdi+rdi*4] lea eax, [rdi+rax*8] lea eax, [rax+rax*4] shr ax, 11 movzx eax, al msvc 19 movzx ecx, al mov eax, -858993459 ; cccccccdH mul ecx shr edx, 3 mov eax, edx icc 19 mov eax, 1717986919 imul edi sar edx, 2 mov eax, edx clang and gcc with -O3, msvc -O2

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.
- mzs 8y ago
  I have not used it in many years, but I have foggy memory of IBM's Power cpu compiler doing similar trick for remainder.

mark-r 8y ago

I recently discovered that x/10 == (x*103)>>10 for the numbers 0-99. Helped speed up something I was working on. The compiler generated a similar multiply/shift for x/10, but mine was faster since it didn't need to work for all possible values of x.

saagarjha 8y ago
Does a multiply/shift pair take a different amount of time based on the operands? Otherwise, I don't see how this would make a difference.
- bdonlan 8y ago
  The compiler has to assume that your operands might be large enough that they would overflow after a straight multiply.
  - saagarjha 8y ago
    As acqq/I have mentioned below, there are ways of telling the compiler that the overflow can't multiply so it can freely optimize these away.
- nitrogen 8y ago
  It's conceivable that multiplication time might be proportional to the number of 1 bits in the multiplier.
- mark-r 8y ago
  My code was two instructions: imul eax,ecx,67h sar eax,0Ah. The compiler generated code was mov eax,66666667h imul ecx sar edx,2 mov eax,edx shr eax,1Fh add eax,edx.
  - acqq 8y ago
    When input unsigned but before if < 99, output unsigned int: clang 7 mov ecx, edi mov eax, 3435973837 imul rax, rcx shr rax, 35 gcc 8.2 mov eax, edi mov edx, -858993459 mul edx mov eax, edx shr eax, 3 msvc 19 mov eax, -858993459 ; cccccccdH mul edx shr edx, 3 mov eax, edx icc 19 mov eax, 1717986919 imul edx sar edx, 2 mov eax, edx The same, but when input unsigned char: clang 7 movzx eax, dil imul eax, eax, 205 shr eax, 11 gcc 8.2 movzx edi, dil lea eax, [rdi+rdi*4] lea eax, [rdi+rax*8] lea eax, [rax+rax*4] shr ax, 11 movzx eax, al msvc 19 movzx ecx, al mov eax, -858993459 ; cccccccdH mul ecx shr edx, 3 mov eax, edx icc 19 mov eax, 1717986919 imul edi sar edx, 2 mov eax, edx clang and gcc with -O3, msvc -O2