CODEWITHSUNDEEP
language-agnosticmodulo
pNok
pNok

Reputation: 123

How is the modulo operator (%) actually computed?

Recently I've been confused about the modulo operator, %.

It's known that a % b == a-a/b*b when we have integers a and b where a > b, and we can do this calculation by hand if a and b are small enough.

However, when it comes to the way a processor computes it, does the processor use the same method as previously mentioned, a-a/b*b? Maybe just by translating the division into subtraction or addition, or is there some shifting involved perhaps?

Upvotes: 9

Views: 3840

Answers (2)

Paul Tomblin
Paul Tomblin

Reputation: 182802

Except for powers of 2, where the modulo operator can (and in most optimizing compilers is) be turned into a simple bitwise operation, I'm afraid the only way to do it is the hard way. Explanation is http://en.wikipedia.org/wiki/Modulo_operation

In another answer, @Henk Holterman points out that some CPUs do it in the microcode, leaving the remainder in a register while doing an integer divide, which means the modulo instruction can be reduced to an integer divide and return the remainder. (I'm adding that information here because this answer has already been accepted.)

Upvotes: 8

Steve Wellens
Steve Wellens

Reputation: 20640

It uses the idiv assembly instruction:

    int x = a % b;
00000050  cmp         dword ptr [rsp+20h],80000000h 
00000058  jne         0000000000000061 
0000005a  cmp         dword ptr [rsp+24h],0FFFFFFFFh 
0000005f  je          0000000000000070 
00000061  mov         eax,dword ptr [rsp+20h] 
00000065  cdq              
00000066  idiv        eax,dword ptr [rsp+24h] 
0000006a  mov         dword ptr [rsp+2Ch],edx 
0000006e  jmp         0000000000000075 
00000070  call        FFFFFFFFF2620E70 
00000075  mov         eax,dword ptr [rsp+2Ch] 
00000079  mov         dword ptr [rsp+28h],eax

idiv stores the remainder in a register.
http://pdos.csail.mit.edu/6.828/2007/readings/i386/IDIV.htm

Upvotes: 5

Related Questions