<p>I read somewhere once that the modulus operator is inefficient on small embedded devices like 8 bit micro-controllers that do not have integer division instruction. Perhaps someone can confirm this but I thought the difference is 5-10 time slower than with an integer division operation.</p>

<p>Is there another way to do this other than keeping a counter variable and manually overflowing to 0 at the mod point?<p></p>

<pre><code>const int FIZZ = 6;
for(int x = 0; x &lt; MAXCOUNT; x++)
{
    if(!(x % FIZZ)) print("Fizz\n"); // slow on some systems
}
</code></pre>

<p>vs:</p>

<p>The way I am currently doing it:</p>

<pre><code>const int FIZZ = 6;
int fizzcount = 1;
for(int x = 1; x &lt; MAXCOUNT; x++)
{
    if(fizzcount &gt;= FIZZ) 
    {
        print("Fizz\n");
        fizzcount = 0;
    }
}
</code></pre>

[{'answer_id': 48058, 'author': 'Paul Tomblin', 'author_id': 3333, 'author_profile': 'https://Stackoverflow.com/users/3333', 'pm_score': 1, 'selected': False, 'text': '<p>In the embedded world, the "modulus" operations you need to do are often the ones that break down nicely into bit operations that you can do with <code>&amp;</code>, <code>|</code> and sometimes <code>&gt;&gt;</code>.</p>\n'}, {'answer_id': 48074, 'author': 'shmuelp', 'author_id': 4673, 'author_profile': 'https://Stackoverflow.com/users/4673', 'pm_score': 2, 'selected': False, 'text': "<p>Unless you really need high performance on multiple embedded platforms, don't change how you code for performance reasons until you profile!</p>\n\n<p>Code that's written awkwardly to optimize for performance is hard to debug and hard to maintain.  Write a test case, and profile it on your target.  Once you know the actual cost of modulus, then decide if the alternate solution is worth coding.</p>\n"}, {'answer_id': 48075, 'author': 'Matt Sheppard', 'author_id': 797, 'author_profile': 'https://Stackoverflow.com/users/797', 'pm_score': 0, 'selected': False, 'text': "<p>Not that this is necessarily better, but you could have an inner loop which always goes up to <code>FIZZ</code>, and an outer loop which repeats it all some certain number of times. You've then perhaps got to special case the final few steps if <code>MAXCOUNT</code> is not evenly divisible by <code>FIZZ</code>.</p>\n\n<p>That said, I'd suggest doing some research and performance profiling on your intended platforms to get a clear idea of the performance constraints you're under. There may be much more productive places to spend your optimisation effort.</p>\n"}, {'answer_id': 48078, 'author': 'Rob Rolnick', 'author_id': 4798, 'author_profile': 'https://Stackoverflow.com/users/4798', 'pm_score': 1, 'selected': False, 'text': '<p>Do you have access to any programmable hardware on the embedded device? Like counters and such? If so, you might be able to write a hardware based mod unit, instead of using the simulated %. (I did that once in VHDL. Not sure if I still have the code though.)</p>\n\n<p>Mind you, you did say that division was 5-10 times faster. Have you considered doing a division, multiplication, and subtraction to simulated the mod? (Edit: Misunderstood the original post. I did think it was odd that division was faster than mod, they are the same operation.)</p>\n\n<p>In your specific case, though, you are checking for a mod of 6. 6 = 2*3. So you could MAYBE get some small gains if you first checked if the least significant bit was a 0. Something like:</p>\n\n<pre><code>if((!(x &amp; 1)) &amp;&amp; (x % 3))\n{\n    print("Fizz\\n");\n}\n</code></pre>\n\n<p>If you do that, though, I\'d recommend confirming that you get any gains, yay for profilers. And doing some commenting. I\'d feel bad for the next guy who has to look at the code otherwise.</p>\n'}, {'answer_id': 48079, 'author': 'Matthew Crumley', 'author_id': 2214, 'author_profile': 'https://Stackoverflow.com/users/2214', 'pm_score': 5, 'selected': False, 'text': "<p>If you are calculating a number mod some power of two, you can use the bit-wise and operator. Just subtract one from the second number. For example:</p>\n\n<pre><code>x % 8 == x &amp; 7\nx % 256 == x &amp; 255\n</code></pre>\n\n<p>A few caveats:</p>\n\n<ol>\n<li>This <strong>only works</strong> if the second number is a power of two.</li>\n<li>It's only equivalent if the modulus is always positive. The C and C++ standards don't specify the sign of the modulus when the first number is negative (until C++11, which <em>does</em> guarantee it will be negative, which is what most compilers were already doing). A bit-wise and gets rid of the sign bit, so it will always be positive (i.e. it's a true modulus, not a remainder). It sounds like that's what you want anyway though.</li>\n<li><strong>Your compiler probably already does this when it can, so in most cases it's not worth doing it manually.</strong></li>\n</ol>\n"}, {'answer_id': 48090, 'author': 'hoyhoy', 'author_id': 3499, 'author_profile': 'https://Stackoverflow.com/users/3499', 'pm_score': 2, 'selected': False, 'text': '<p>@Matthew is right.  Try this:</p>\n\n<pre><code>int main() {\n  int i;\n  for(i = 0; i&lt;=1024; i++) {\n    if (!(i &amp; 0xFF)) printf("&amp; i = %d\\n", i);\n    if (!(i % 0x100)) printf("mod i = %d\\n", i);\n  }\n}\n</code></pre>\n'}, {'answer_id': 48091, 'author': 'Rob Rolnick', 'author_id': 4798, 'author_profile': 'https://Stackoverflow.com/users/4798', 'pm_score': 0, 'selected': False, 'text': '<p>@Jeff V: I see a problem with it! (Beyond that your original code was looking for a mod 6 and now you are essentially looking for a mod 8). You keep doing an extra +1! Hopefully your compiler optimizes that away, but why not just test start at 2 and go to MAXCOUNT inclusive? Finally, you are returning true every time that (x+1) is NOT divisible by 8. Is that what you want? (I assume it is, but just want to confirm.)</p>\n'}, {'answer_id': 48093, 'author': 'Vincent Robert', 'author_id': 268, 'author_profile': 'https://Stackoverflow.com/users/268', 'pm_score': 1, 'selected': False, 'text': '<p>You should really check the embedded device you need. All the assembly language I have seen (x86, 68000) implement the modulus using a division.</p>\n\n<p>Actually, the division assembly operation returns the result of the division and the remaining in two different registers.</p>\n'}, {'answer_id': 48103, 'author': 'Adam Davis', 'author_id': 2915, 'author_profile': 'https://Stackoverflow.com/users/2915', 'pm_score': 7, 'selected': True, 'text': '<p>Ah, the joys of bitwise arithmetic. A side effect of many division routines is the modulus - so in few cases should division actually be faster than modulus.  I\'m interested to see the source you got this information from.  Processors with multipliers have interesting division routines using the multiplier, but you can get from division result to modulus with just another two steps (multiply and subtract) so it\'s still comparable.  If the processor has a built in division routine you\'ll likely see it also provides the remainder.</p>\n\n<p>Still, there is a small branch of number theory devoted to <a href="http://en.wikibooks.org/wiki/Discrete_mathematics/Modular_arithmetic" rel="noreferrer">Modular Arithmetic</a> which requires study if you really want to understand how to optimize a modulus operation.  Modular arithmatic, for instance, is very handy for generating <a href="http://www.math.utah.edu/~carlson/mathcircles/magic.pdf" rel="noreferrer">magic squares</a>.</p>\n\n<p>So, in that vein, here\'s a <a href="http://piclist.org/techref/postbot.asp?by=time&amp;id=piclist/2006/08/03/065022a" rel="noreferrer">very low level look</a> at the math of modulus for an example of x, which should show you how simple it can be compared to division:</p>\n\n<hr>\n\n<p>Maybe a better way to think about the problem is in terms of number\nbases and modulo arithmetic. For example, your goal is to compute DOW\nmod 7 where DOW is the 16-bit representation of the day of the\nweek. You can write this as:</p>\n\n<pre><code> DOW = DOW_HI*256 + DOW_LO\n\n DOW%7 = (DOW_HI*256 + DOW_LO) % 7\n       = ((DOW_HI*256)%7  + (DOW_LO % 7)) %7\n       = ((DOW_HI%7 * 256%7)  + (DOW_LO%7)) %7\n       = ((DOW_HI%7 * 4)  + (DOW_LO%7)) %7\n</code></pre>\n\n<p>Expressed in this manner, you can separately compute the modulo 7\nresult for the high and low bytes. Multiply the result for the high by\n4 and add it to the low and then finally compute result modulo 7.</p>\n\n<p>Computing the mod 7 result of an 8-bit number can be performed in a\nsimilar fashion. You can write an 8-bit number in octal like so:</p>\n\n<pre><code>  X = a*64 + b*8 + c\n</code></pre>\n\n<p>Where a, b, and c are 3-bit numbers.</p>\n\n<pre><code>  X%7 = ((a%7)*(64%7) + (b%7)*(8%7) + c%7) % 7\n      = (a%7 + b%7 + c%7) % 7\n      = (a + b + c) % 7\n</code></pre>\n\n<p>since <code>64%7 = 8%7 = 1</code></p>\n\n<p>Of course, a, b, and c are</p>\n\n<pre><code>  c = X &amp; 7\n  b = (X&gt;&gt;3) &amp; 7\n  a = (X&gt;&gt;6) &amp; 7  // (actually, a is only 2-bits).\n</code></pre>\n\n<p>The largest possible value for <code>a+b+c</code> is <code>7+7+3 = 17</code>. So, you\'ll need\none more octal step. The complete (untested) C version could be\nwritten like:</p>\n\n<pre><code>unsigned char Mod7Byte(unsigned char X)\n{\n    X = (X&amp;7) + ((X&gt;&gt;3)&amp;7) + (X&gt;&gt;6);\n    X = (X&amp;7) + (X&gt;&gt;3);\n\n    return X==7 ? 0 : X;\n}\n</code></pre>\n\n<p>I spent a few moments writing a PIC version. The actual implementation\nis slightly different than described above</p>\n\n<pre><code>Mod7Byte:\n       movwf        temp1        ;\n       andlw        7        ;W=c\n       movwf        temp2        ;temp2=c\n       rlncf   temp1,F        ;\n       swapf        temp1,W ;W= a*8+b\n       andlw   0x1F\n       addwf        temp2,W ;W= a*8+b+c\n       movwf        temp2   ;temp2 is now a 6-bit number\n       andlw   0x38    ;get the high 3 bits == a\'\n       xorwf        temp2,F ;temp2 now has the 3 low bits == b\'\n       rlncf   WREG,F  ;shift the high bits right 4\n       swapf   WREG,F  ;\n       addwf        temp2,W ;W = a\' + b\'\n\n ; at this point, W is between 0 and 10\n\n\n       addlw        -7\n       bc      Mod7Byte_L2\nMod7Byte_L1:\n       addlw        7\nMod7Byte_L2:\n       return\n</code></pre>\n\n<p>Here\'s a liitle routine to test the algorithm</p>\n\n<pre><code>       clrf    x\n       clrf    count\n\nTestLoop:\n       movf        x,W\n       RCALL   Mod7Byte\n       cpfseq count\n        bra    fail\n\n       incf        count,W\n       xorlw   7\n       skpz\n        xorlw        7\n       movwf   count\n\n       incfsz        x,F\n       bra        TestLoop\npassed:\n</code></pre>\n\n<p>Finally, for the 16-bit result (which I have not tested), you could\nwrite:</p>\n\n<pre><code>uint16 Mod7Word(uint16 X)\n{\n return Mod7Byte(Mod7Byte(X &amp; 0xff) + Mod7Byte(X&gt;&gt;8)*4);\n}\n</code></pre>\n\n<p>Scott</p>\n\n<hr>\n'}, {'answer_id': 59461, 'author': 'Greg Rogers', 'author_id': 5963, 'author_profile': 'https://Stackoverflow.com/users/5963', 'pm_score': -1, 'selected': False, 'text': '<p>The print statement will take orders of magnitude longer than even the slowest implementation of the modulus operator. So basically the comment "slow on some systems" should be "slow on all systems".</p>\n\n<p>Also, the two code snippets provided don\'t do the same thing. In the second one, the line</p>\n\n<pre>if(fizzcount >= FIZZ)</pre>\n\n<p>is always false so "FIZZ\\n" is never printed.</p>\n'}, {'answer_id': 60873, 'author': 'itj', 'author_id': 888, 'author_profile': 'https://Stackoverflow.com/users/888', 'pm_score': 3, 'selected': False, 'text': '<p>There is an overhead most of the time in using modulo that are not powers of 2.\nThis is regardless of the processor as (AFAIK) even processors with modulus operators are a few cycles slower for divide as opposed to mask operations.</p>\n\n<p>For most cases this is not an optimisation that is worth considering, and certainly not worth calculating your own shortcut operation (especially if it still involves divide or multiply).</p>\n\n<p>However, one rule of thumb is to select array sizes etc. to be powers of 2.</p>\n\n<p>so if calculating day of week, may as well use %7 regardless\nif setting up a circular buffer of around 100 entries... why not make it 128.  You can then write % 128 and most (all) compilers will make this &amp; 0x7F</p>\n'}, {'answer_id': 29655945, 'author': 'Zeeshan', 'author_id': 559017, 'author_profile': 'https://Stackoverflow.com/users/559017', 'pm_score': 2, 'selected': False, 'text': '<pre><code>x%y == (x-(x/y)*y)\n</code></pre>\n\n<p>Hope this helps.</p>\n'}, {'answer_id': 54969894, 'author': 'TigerTV.ru', 'author_id': 9210255, 'author_profile': 'https://Stackoverflow.com/users/9210255', 'pm_score': 0, 'selected': False, 'text': '<p>For modulo 6 you can change the Python code to C/C++:</p>\n\n<pre><code>def mod6(number):\n    while number &gt; 7:\n        number = (number &gt;&gt; 3 &lt;&lt; 1) + (number &amp; 0x7)\n    if number &gt; 5:\n        number -= 6\n    return number\n</code></pre>\n'}]
['https://Stackoverflow.com/questions/48053', 'https://Stackoverflow.com', 'https://Stackoverflow.com/users/445087/']