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.

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.

Just curious, did you try making x an 8-bit integer to see if the compiler chose a different multiplier?

Here's a repo with 2 tests, counting bits, and calculating sine/cosine: https://github.com/Const-me/LookupTables

Neither code is particularly cheap but still faster than RAM.

clang 7

        mov     ecx, edi
        mov     eax, 3435973837
        imul    rax, rcx
        shr     rax, 35

        mov     eax, edi
        mov     edx, -858993459
        mul     edx
        mov     eax, edx
        shr     eax, 3

        mov     eax, -858993459  ; cccccccdH
        mul     edx
        shr     edx, 3
        mov     eax, edx

        mov       eax, 1717986919                               
        imul      edx                                           
        sar       edx, 2                          
        mov       eax, edx

clang 7

        movzx   eax, dil
        imul    eax, eax, 205
        shr     eax, 11

        movzx   edi, dil
        lea     eax, [rdi+rdi*4]
        lea     eax, [rdi+rax*8]
        lea     eax, [rax+rax*4]
        shr     ax, 11
        movzx   eax, al

        movzx   ecx, al
        mov     eax, -858993459  ; cccccccdH
        mul     ecx
        shr     edx, 3
        mov     eax, edx

        mov       eax, 1717986919
        imul      edi            
        sar       edx, 2        
        mov       eax, edx

https://godbolt.org/z/bS2yzB

But also note that when the input is unsigned short we get:

https://godbolt.org/z/sbDbMU

        movzx   eax, di
        imul    eax, eax, 52429
        shr     eax, 19