0

I am relatively new to programming, and after going through some of the questions asked on this subject, I still could not find an answer.

As I understand it, the % operator in C++ can be rewritten in a number of ways, some of which seem to perform better as indicated by some users here:

Built-in mod ('%') vs custom mod function: improve the performance of modulus operation

Now if I understand correctly, arithmetic operations on integers - such as + and - are faster than * and / when we think about multiplication as repeated addition for instance( this is commonly mentioned in threads I have read).

So, why wouldn't something like the following function be faster than % :

int mod(int a, int b)
{
   int s = a;

   while(s < b)
   {
     s += a;
   }
   return a - (s - b);
}

As I am quite new to programming and have little knowledge in how things are implemented by compilers- I am not sure what way would be appropriate to test this, and whether results might vary greatly depending on the compiler and implementations.

dvd280
  • 876
  • 6
  • 11
  • "_when we think about multiplication as repeated addition_" - This is however not how anyone making multiplications only using a pen an paper thinks about it. Neither does your CPU. As to your question: Test it: https://quick-bench.com/ – Ted Lyngmo Oct 10 '20 at 09:26
  • Create a simple program doing both variants (using your function and the `%` operator) a million times each. Build it with optimizations enabled. Then time each variant. That will tell you how each is doing on your platform using your compiler. You can also compare the generated machine code for both variants (using e.g. [the compiler explorer](https://godbolt.org/) is very good for this). But remember, for any kind of benchmarking always build with optimizations enabled. – Some programmer dude Oct 10 '20 at 09:26

1 Answers1

2

Moulo usually is implemented through one or a couple CPU operations, so in general it's single operation: not counting auxilary instructions.

But by definition it should be quite simple:

int mult = a / b; 
return a - mult * b;

E.g. on x86-64 clang compiles

int mod(int a, int b)
{
   return a % b;
}

into following code, the actual operation is integer division, which returns remainder in EDX

mod(int, int):                               # @mod(int, int)
        push    rbp
        mov     rbp, rsp
        mov     dword ptr [rbp - 4], edi
        mov     dword ptr [rbp - 8], esi
        mov     eax, dword ptr [rbp - 4]
        cdq
        idiv    dword ptr [rbp - 8]
        mov     eax, edx
        pop     rbp
        ret

Your version:

mod(int, int):                               # @mod(int, int)
        push    rbp
        mov     rbp, rsp
        mov     dword ptr [rbp - 4], edi
        mov     dword ptr [rbp - 8], esi
        mov     eax, dword ptr [rbp - 4]
        mov     dword ptr [rbp - 12], eax
.LBB0_1:                                # =>This Inner Loop Header: Depth=1
        mov     eax, dword ptr [rbp - 12]
        cmp     eax, dword ptr [rbp - 8]
        jge     .LBB0_3
        mov     eax, dword ptr [rbp - 4]
        add     eax, dword ptr [rbp - 12]
        mov     dword ptr [rbp - 12], eax
        jmp     .LBB0_1
.LBB0_3:
        mov     eax, dword ptr [rbp - 4]
        mov     ecx, dword ptr [rbp - 12]
        sub     ecx, dword ptr [rbp - 8]
        sub     eax, ecx
        pop     rbp
        ret

THat's quite a bunch of operations performed in loop, it's doubtful that it can be faster/

Swift - Friday Pie
  • 12,777
  • 2
  • 19
  • 42