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:

enter image description here


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.