This is because the right shift , just like any other integer division, truncates, and thus rounds downwards. on the call to a function, then step over the function and get a direct read of how many cycles the function took. This is ridiculous. The second operator yields 1. I looked at some code generated by GCC and it appears that the divide routine produces the modulus simultaneously. seconds = seconds -86400*days If the first number (a) is non-zero and the second number is 0, it gives an error at compile time. All rights reserved. Operations: 7 multiplications, 7 shifts, 6 add or sub, total 20. If 8 shifts have taken place, the BCD number is in the Hundreds, Tens, and Units column. uint_fast8_t hours, minutes, seconds; and ) The modulus operator works with two operands received by the end-user. ^ Whenever one needs to do integer multiplications starting with an integer whose range is not limited, if the incoming number is high, multiplying it by any number greater than 1 will cause an overflow. Again we multiply the decimal part (0.269629..) by 2^32 and round it upwards. { When the compiler’s behavior is undefined, it is is free to do just about anything. It is enough when the variable is uint16_t, so why not uint8_t? To demonstrate what I mean, some background information is in order as to how this blog posting came about. FWIW C does have a divide with remainder function. 8 /16 bit architectures lack a divide instruction. The modulus operator. 3) In general you replace a/b with (a * b) >> c, where b is pre-calculated as ceil( (1<> 32) >> 5; // IAR EWARM compiler calculates only the upper 32 bits of p minutes = (279621 * seconds) >> 24 The second line has an unexpected start: a constant 7 is added. ‘David. “i & n – 1” is equivalent to “i % n” (Knuth 4A, 136). It’s obviously more for speed and micro-optimization junkies, but you’ll see several different faster ways than the straight modulus operation. If the variable a is completely divisible by the second number (b), it returns zero (0), or the remainder becomes 0. remainder = dividend % divisor; Finally, the quotient and remainder are displayed using printf( ) . When writing firmware (e.g. “LINT: D:\temp\junk.c (6, 37) Warning 564: variable ‘a’ depends on order of evaluation”, Thank you, Mr Nigel Jones. It is used to perform different operations (+, -, … This allowed me to check that the code was producing the correct answers. The method works by avoiding the divide operation: rather than dividing by a constant K, you multiply by a pre-calculated ciel(2^32 / K ) and then look at the more significant 32-bits of the result. Oops, actually the #define will be 32 bit. seconds = seconds – 60* minutes. Except these four basic operators, there are some other operators such as modulus operator (%), scope resolution operator (::), etc. Most older 8bit software probably uses custom representation for date-time stuff, allocating, for example, 1 byte for each component and instead using custom addition-subtraction subroutines instead of more general approach. it’s so slow, it gets compiled from c into multiplication by a fraction. The modulo division operator produces the remainder of an integer division. On an ARM M3, the div operation is good: 2 to 12 cycles depending on the data, in which case, the line I wrote: a = seconds >> 7; days = (7 +97*a + ((93*a)>>10) –((59*a)>>17) ) >>16. Following is the pseudo-code for the chaining of modulus operator, as given below. hours = (74566 * (seconds >>4)) >>24 The scale factor of ceiling(2^32 * 32 / 60) can be considered a 32-bit unsigned binary fraction representing (32/60). This modulus operator added to arithmetic operators. Let's consider the program of Chaining of Modulus Operator to take more than two operands. hundreds = (i*656) >> 16 Only shifts, compares, and adds (and increment to keep track of the number of shifts). not even “if x>….” since ifs are expensive for modern instruction-caching cpus. With the constants ready at compile time, at run time we do this: days =( (seconds * DaysDecMul ) >> 32 ) + seconds * DaysIntMul) >> 32 I recorded the number of cycles in this second case. Line 6: Warning[Pa081]: undefined behavior: the order of read and modification of variable “a” (or a value reached by some form of indirection through it) is undefined in this statement. 4 % 2 = 0 4 is even as remainder is 0. bro, you know that mod is very efficient for all operands of powers of 2 due to optimized instructions for this special binary case. I could of course just stop at this point. Let’s say A was 6 and B was 4. Very interesting post Jacob. uint8_t q2, q3; In C++, Modulus is performed using arithmetic operator %. How about not using a single variable for keeping time? So we can split it into an integer and a decimal part. b = a++ + ++a; Explain to me please how if C=A%B, C is also equal to A – B*(A/B). It determines the remainder. –. The modulus operator is a symbol used in various programming languages. I use IAR’s compilers – and all their simulators I’ve used have the feature. As mentioned in the introduction,  C = A % B is equivalent to C = A – B * (A / B). Writing a single piece of code for all three architectures and and expect it to give optimal performance is a little naive, IMHO. Also, I believe that the second equation given, C = A – B *(A/B), will always produce zero if you were to write it out. modulus sometimes come for free if the two operators (% and /) are in the same block in the source and use the same operands, . It’s not undefined in C, C99 specifies the following: “When integers are divided, the result of the / operator is the algebraic quotient with any fractional part discarded. However your point that the remainder (modulus) inherently falls out of the division operator is valid. Therefore, 7 % 4 = 3. 19, Jul 12. you should’ve analyzed the asm generated by the compilers as well, no t just simply the run times. / Division of left operand by the right operand: a / b. will give. 4 multiplies, 2 subtracts, maybe 2 shifts if your compiler isn’t too smart. And MinutesMul =ceil(2^32 / 60) = 71582789. In this problem, we are given two numbers, N and D. Our task is to create a Program to find remainder without using modulo or % operator in C++.. The following table shows all the arithmetic operators supported by the C language. Jacob is correct to point out that the division by 60 or modulo 60 operation can also be transformed into a multiplication by the reciprocal of 60 with scaling. However examination of attempt 2 shows that further optimizations are possible by observing that if seconds is a 32 bit variable, then days can be at most a 16 bit variable. Now my question: Does this approach make any difference in the performance of the code? This is what PC-Lint had to say: PC-lint for C/C++ (NT) Vers. Go to 1. Perhaps this is clearer A – B * INT(A/B) where INT(A/B) is taken to mean perform integer arithmetic. I do not know of a “C” compiler that provides access to the remainder. This is a list of operators in the C and C++ programming languages.All the operators listed exist in C++; the fourth column "Included in C", states whether an operator is also present in C. Note that C does not support operator overloading.. q2 = q1 >> 3; Assume variable A holds 10 and variable Bholds 20 then − Show Examples seconds = time – 60UL * stime; The modulus operator in C is denoted by % (percentile) operator. b : c; parses as (std:: cout << a)? The 7 will be lost by the large right shift unless the incoming number is very large., in which case it compensates for the imprecision of the integer approximation. IAR gives the correct answer and Lint gives an incomplete one. Thus my claim that the modulus operator can be very inefficient is true for some architectures – but not all.  Thus if you are using the modulus operator on an ARM processor then it’s probably not worth worrying about. Nigel Jones is an embedded systems consultant with over 20 years of experience designing electronic circuits and firmware. I have found that the IAR Embedded Workbench for ARM compiler does exactly this. Jacob: You might find this posting interesting. The number of cycles quoted are for 10 invocations of the test code and include the test harness overhead: No that isn’t a misprint. Shift the binary number left one bit. { Remainder always integer number only. – Subtraction of right operand from the left operand: a – b will give5. Modifying a variable twice without sequence points in between is undefined behavior (ISO 9899:1999 6.5 §2). Altogether 5 multiplies, three subtracts, one add, and if the compiler is good, the shifts are just an address selection and do not take machine cycles at all. on Tuesday, February 8th, 2011 at 9:21 am and is filed under Algorithms, Efficient C/C++, General C issues. Thus this suggests a simple optimization to the algorithm. – Explicit typecast on “minutes” in the last line, to avoid implicit integer promotions. seconds = seconds – 3600 * hours Even for CPU that do not have a native / or %, the cost is the same as the % is calculated intrisicly, at no extra cost, as the / is performed. The % (modulo operator) is an example of such an operator, as it is not defined the same way in all programming languages. Maybe you’d like to benchmark this? It's important to know the difference and what the language being used uses. This is what my IAR AVR compiler had to say (line 5 is the assignment to b, line 6 is the printf): Let's understand the following example that illustrates the functionality of the modulus operator. uint_fast16_t days; As far as I know, there are instruction set extensions with division for some members of different MCU families. Prepare to multiply by 2^32 / (24 * 60*60) which we can pre-calculate. It doesn’t does it. For 8 and 16 bit MCUs using 32-bit math is wrong approach altogether, and benchmarks show it quite clearly, no matter what “optimizations” you try to apply. The key to this is to round UPWARDS when pre-calculating the constants. value -=10; void display_time(uint32_t time) } Notwithstanding the ARM results, it’s clear that at least in this example, it’s possible to significantly speed up an algorithm by eliminating the modulus operator. If you have to do it by hand it cost one comparison (besides the increments) per second, one comparison per minute, per hour, and so on… If you have to update your display once a second anyway (displaying time), you’d certainly win. hours = (seconds * Hours_Mul) >> 32 Some compilers can do this for open-coded use of / and % too (gcc, at least recent-ish versions, does so). You can find modulus operator in almost all programming language. while (value>99) So the register situation would be the same, but the optimizer would replace the mod to a mask. So, on 2 different architectures (ARM and Intel for example), % will give different results depending on the sign of the inputs! In some cases, the remainder may be 0, it means the number is completely divisible by the divisor. In all three cases I used an IAR compiler with full speed optimization. Each programming language has same usage of modulus operator and in C++ this operator is also called as remainder operator. A useful scale factor is ceiling(2^32 * 2^n / 60), where n is the largest integer such that (2^n / 60) < 1. In the case of integer for display, I believe you could use the double-dabble algorithm: 1. printf(“%d %d %d %d”,b,a++,a,++a); Is it right? { An arithmetic operator performs mathematical operations such as addition, subtraction, multiplication, division etc on numerical values (constants and variables). Line 5: Warning[Pa079]: undefined behavior: variable “a” (or a value reached by some form of indirection through it) is modified more than once without an intervening sequence point in this statement I do quite a lot of this type of benchmarking and one of the problems you immediately run into is that your test code gets optimized away. minutes = stime – 60UL * time; If we compare this to the code in attempt 1, then it should be apparent that the intermediate value (A/B) computed as part of the modulus operation is in fact needed in the next line of code. A similar problem (with a similar solution) occurs when one wants to display integers on a display. You can write it this way: 13 % 4 = 1. Find the largest n where (2^n / K) < 1, then scale the result by (2^-n), which is just a right shift by n bits (for unsigned operands). ?divu32_a seconds = seconds – hours * SecondsInHour hours = (uint_fast8_t)(time / 3600UL); MOV R1,#+3600 ^ The method works by avoiding the divide operation: rather than dividing by a constant K, you multiply by a pre-calculated ciel(2^32 / K ) and then look at the more significant 32-bits of the result. Here’s one more idea for converting a 32-bit integer of seconds into days, hours, minutes and seconds. Yes we can check a number is even or odd without using division and modulus operators for that we need to use & operator; number &1 ==1 then it is an even number. _BLF ??divu32_a,??rA? In programming, the operator symbol tells the compiler to perform a particular operation at a given number based on the passed operation. Modulo can be easily translated into a bitwise AND if the divisor is a power of two. Following are the possibilities when the first number is divided by the second number to return only a remainder value. In C99, a mask and a modulo don’t get the same result for negative numbers (eg -3 % 2 == -1).