# 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: