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 &gt; 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.