Optimized Is divisible by

Question

Let's say I have the number X and I want to see if it is divisible by Y. What would be the most optimized way to do this?

So far I have:

int X = 12;
int Y = 4;
(X ^ Y) & 0b111 ==0    # Check if X XOR Y (mask size Y) == 0

Though I'm hardcoding 0b111 (the mask size of Y). By the way, I don't care about the language, I'm just tagging this with C.

By the way, using Compiler Explorer I get:

int is_divisible_by(int x, int y) {
    return x % y == 0;
};

# -O3
is_divisible_by:
        movl    %edi, %eax
        cltd
        idivl   %esi         # seems to just be doing straight division?
        xorl    %eax, %eax
        testl   %edx, %edx
        sete    %al
        ret

Just do `x % y` and compile with speed optimizations (maybe stop the compiler at the assembler stage `gcc -Ofast -S`): hopefully compiler already uses all the tricks of the trade. — pmg, Sep 17 '20 at 19:33
@pmg exactly -- I mean what would the compiler do at a lower level... — David542, Sep 17 '20 at 19:33
@David542 You can find out by compiling with `-S` and looking at the assembly. Or look at the assembly with a debugger. I would expect to see a division instruction, unless Y is a hardcoded number (e.g. (X % 4) == 0), or the compiler is able to compute the value of Y at compile time. — user3386109, Sep 17 '20 at 19:41
@EugeneSh. could you please explain what you mean, or an example where two different approaches would be required? — David542, Sep 17 '20 at 20:02
Note: if you make the function static (or inline) the function will be possibly be optimised out. (given the predictable/constant arguments) — wildplasser, Sep 17 '20 at 20:07
FYI Mask in java: `(Integer.highestOneBit(y) << 1) - 1` where highestOneBit needs 6 shrift-rights. — Joop Eggen, Sep 17 '20 at 20:08
@David542 I mean that checking if divisible by powers of 2 is way easier than checking if divisible by some other numbers. — Eugene Sh., Sep 17 '20 at 20:08
The XOR trick doesn't work for X = 0, 8, 16 etc and anyway if Y is a power of two then the trick is `(X & (Y - 1)) == 0` — harold, Sep 17 '20 at 20:10
If Y is known but not a power of two then [this answer applies](https://stackoverflow.com/a/49264279/555045) (with the multiplication by the modular inverse and sometimes bitwise rotate). If Y is not known, well, bad luck. — harold, Sep 17 '20 at 20:14
I really doubt there is a universal method not involving division (or some kind of it's indirect implementation such as repeated subtraction) — Eugene Sh., Sep 17 '20 at 20:15

score 9 · Accepted Answer · edited Sep 17 '20 at 20:25

The compiler will use different algorithms depending on arguments. If some are constant expressions or can be predicted before the call it will use much faster way of doing it.


int is_divisible_by(const int x, const int y) {
    return !(x % y);
};

int case1(void)
{
    return is_divisible_by(6,3);
}

int case2(int x)
{
    return is_divisible_by(x,2);
}

int case3(int x)
{
    return is_divisible_by(x,5);
}

int case4(int x)
{
    return is_divisible_by(x,255);
}

int case5(int x)
{
    return is_divisible_by(x,32);
}


int case6(int x, int y)
{
    return is_divisible_by(x,y);
}

is_divisible_by:
        mov     eax, edi
        cdq
        idiv    esi
        xor     eax, eax
        test    edx, edx
        sete    al
        ret
case1:
        mov     eax, 1
        ret
case2:
        mov     eax, edi
        not     eax
        and     eax, 1
        ret
case3:
        imul    edi, edi, -858993459
        xor     eax, eax
        add     edi, 429496729
        cmp     edi, 858993458
        setbe   al
        ret
case4:
        imul    edi, edi, -16843009
        xor     eax, eax
        add     edi, 8421504
        cmp     edi, 16843008
        setbe   al
        ret
case5:
        xor     eax, eax
        and     edi, 31
        sete    al
        ret
case6:
        mov     eax, edi
        cdq
        idiv    esi
        xor     eax, eax
        test    edx, edx
        sete    al
        ret

https://godbolt.org/z/9cxEfe

Optimized Is divisible by

1 Answers1