2
$\begingroup$

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

$\endgroup$
4
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ OK, so that's definition of %. I found this article on binary multiplier on Wikipedia which links to more articles on multiplication. $\endgroup$ – john mangual Jul 30 '18 at 15:48
  • 1
    $\begingroup$ perhaps I should ask at electronics.stackexchange.com ? $\endgroup$ – john mangual Jul 30 '18 at 16:18
  • $\begingroup$ ..which just moves the question on to "algorithm for implementing the / operator". Because gcc on ARM generates a function call for this operator, and the library that's supposed to supply the implementation, libgcc supplies only ARM code not THUMB code rendering / and % unusable on some devices. Still that definition is useful, now I only have to implement one operator. $\endgroup$ – Rodney Jan 12 at 15:22
-1
$\begingroup$

My own mathematical implementation of mod(float x, float y) may be useful in some cases

$$\frac{y}2 - \frac{y}{\pi} \arctan \left ( \cot \left( \frac{x}y\pi \right) \right)$$

https://www.desmos.com/calculator/2uczus4jyr

$\endgroup$
1
  • $\begingroup$ How exactly this answers the question? arctan and cot operations both involve modulus operator on floating point number, which is slower than integer modulus, so it cannot be efficient at all. $\endgroup$ – Evil Aug 11 '20 at 22:23

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.