# Algorithm for implementing the modulus “%” operator?

How can an efficient modulus operator be implemented?

Here's a naive way of defining A % B:

given $(a,b) \in \mathbb{Z}$ (represented as int)

while $a > b$ : $(a,b) \mapsto (a-b,b)$

return $a$

This could be very slow. E.g. $(a,b) = (10^7, 13)$. I could be subtracting 13's for a long time.

One more possibility is that % is defined in terms of another infix operator / as well as the int function (here in C and verbatim in Python):

a % b = a - (b * int(a/b))

This is probably not how Python implements it's modulus operator (as it makes a call to C or Fortran). The % operator is need to reduce fractions or compute GCD's.

Here are some examples of truncation and division from Wikipedia:

You don’t “implement the modulus operator”. You check wit the standards for your programming language how it is defined, and that’s what you implement. For languages like C, C++, Objective-C, Swift and many others, a % b is defined as a - b * (a/ b). And that’s what you implement.

To be efficient: Most processors have built-in division and multiplication. Many support faster implementation of division if b is known. And at last if you want to know whether a % b = 0, you can do that without calculating a / b exactly which makes it a bit faster.