3

is there any alternative of % operator in embedded c ? there are some other ways of doing it such as using while loops in c++. but is it true that modulo operators slow down microcontroller systems ?

leppie
  • 115,091
  • 17
  • 196
  • 297
user3739922
  • 100
  • 1
  • 2
  • 7
  • this seems to be like a duplicate question, http://stackoverflow.com/questions/48053/is-there-an-alternative-to-using-modulus-in-c-c – user3740045 Jun 14 '14 at 11:42
  • 1
    What do you want to do with the modulo operator? – starblue Jun 15 '14 at 14:07
  • there is two approachs to calculation of modulo function: - **Barrett Reduction** - **Montgomery Reduction** [enter image description here](https://i.stack.imgur.com/I7gyz.png) – Morteza Djebeli Apr 03 '19 at 18:14

2 Answers2

4

Whether or not the modulo operator slows down embedded systems depends a lot on which embedded systems you're discussing.

For example, the MPS430 CPU doesn't actually have a native divide instruction so, if you're using that, it will need to revert to a software-based calculation.

However, CPUs that do have a native divide will generally be okay, so it's best to first test whether you have a problem before you attempt to solve it.

Without a native divide instruction, your first attempt will be something like (C, for unsigned only and ignoring issues where div is zero for now):

unsigned modulo (unsigned num, unsigned div) {
    while (num >= div)
        num -= div;
    return num;
}

In other words, using repeated subtraction, something that's not going to be blindingly fast if num is large and div is small.

However, you can considerably ramp up the speed of that function if you just realise that a % b is exactly the same as a % 2b, provided that 2b <= a.

Or that it's the same as a % 4b, provided that 4b <= a. Ditto for a % 8b, provided that 8b <= a.

So, with a little recursive magic, we can adjust num so that it reduces very fast to the point where repeated subtractions won't be a major issue.

unsigned modulo (unsigned num, unsigned div) {
    if (num - div >= div)
        num = modulo (num, div + div);
    while (num >= div)
        num -= div;
    return num;
}

Whereas the naive code sample takes about ten seconds on my system to process a hundred modulo operations (using a random number for num and a random number between one and a hundred for div), the improved solution can get through a million in about a third of a second, a speed-up of some 300,000 times.

You can also speed things up considerably if you know that your divisor is a power of two - there's a much faster way using bitwise operations. Consider that you want to work out:

974 % 16

You can also use the properties of binary numbers and bitwise operations to give you the lower four bits:

num = num & 15;

That's because 15 is 1111 in binary and, if you and any number with that, it will simply clear the top bits, giving you the same result as mod 16. This works for all powers of two such as 2, 4, 8, ... 65536, ..., and so on.

For the specific example of 974 % 16, the binary for 974 bitwise-anded with 15, gives:

1111001110
      1111 &
----------
0000001110 (14)

and 14 is indeed the correct answer.

paxdiablo
  • 854,327
  • 234
  • 1,573
  • 1,953
2

One can divide with the modulo number and the subtract the result from the original number. This is not faster than the original modulo method.

Modulo contains division which can be slow on some embedded processors.

There are exceptions which can be performed faster. Modulo for 2, 4, 8, 16 and so on can be obtained by a simple AND operation which is very fast.

user3613805
  • 21
  • 2