8

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?

Charles
  • 50,943
  • 13
  • 104
  • 142
pNok
  • 113
  • 2
  • 7
  • 2
    @BlackBear, not if it's doing integer math. If a is 8 and b is 3, then a/b is 2, so a-(a/b)*b = 8 - 2*3 = 2. – Paul Tomblin Oct 09 '11 at 13:24
  • @BlackBear Sorry, I should have made it clear ,that the / and * is the integer operator thing which means 9/2==4 and (9/2)*2==8, as in C language. ;) – pNok Oct 09 '11 at 13:27
  • 3
    @0ADD: I thnk it's a different question. The link you provide is asking about what the operator does. This one seems to ask how it is implemented in a processor. – tinman Oct 09 '11 at 13:28

2 Answers2

8

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.)

Paul Tomblin
  • 179,021
  • 58
  • 319
  • 408
  • Then I`m afraid the general method to cope with modulo operator would be the same way as divide-and-remain when the mod number is not the powers of 2.Thank you for reply~ – pNok Oct 09 '11 at 13:35
  • Not really, see for instance IDIV (x86), [here is a page](http://www.cs.virginia.edu/~evans/cs216/guides/x86.html). – H H Oct 09 '11 at 13:59
  • @HenkHolterman, I updated my answer to contain parts of your answer. – Paul Tomblin Oct 09 '11 at 14:13
5

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

Steve Wellens
  • 20,506
  • 2
  • 28
  • 69
  • 3
    I doubt it will do that on an ARM or Motorola CPU. But it is a valid example. – H H Oct 09 '11 at 14:00
  • I'd be interested to know what that special case that they're checking for an calling something is for. Am I right in thinking it's MIN_INT % MAX_INT? – Paul Tomblin Oct 09 '11 at 14:08
  • @HenkHolterman @Steve Wellens :Well,maybe the idiv here renders another level of abstraction?Cuz this would lead to another question of how the idiv instruction is implemented.As i mentioned above, the division thing is deducted to multiple substractions.And when we say the cpu do the modulo thing with the microcode ,we`re actually answering the question who does this and which level it is, rather than how it is done.Even when the microcode does it,i doubt whether it undertakes the same mechanism we use in higher level, or not. – pNok Oct 10 '11 at 03:24
  • 2
    That would be a hardware question. You would need to post that question on another forum. – Steve Wellens Oct 10 '11 at 04:19
  • @pNok You seem to be wondering about how a modulo is actually computed in the level of hardware. That short answer is that it's complicated. The long answer is that you need to learn about abstraction layers. http://en.wikipedia.org/wiki/Abstraction_layer . For a friendly introduction, watch 'How the CPU Works' http://www.youtube.com/watch?v=cNN_tTXABUA – hexicle Jun 07 '13 at 00:03
  • This answer is specific to the x86 architecture. – Nirvana Oct 03 '22 at 07:30