2

When I write code like this:

int a = 7
int b = 2
int c = a/b
int r = a%b

Does the chip use the remainder while calculating c or does it redo the entire calculation?

  • The Atmega328 does not have an intrinsic divide instruction so one has to be implemented by a sequence of other instructions. So the chip doesn't even know about a divide instruction. – Kevin White Oct 16 at 0:12
  • 1
    Ah, so the division itself is done by a series of assembly instructions, not just one :) Then I would hope the compiler is smart enough to save the remainder :) – Beacon of Wierd Oct 16 at 0:23
  • Why do you need to know this? To divide by 2 the compiler merely has to shift right one, and the remainder is simply the low-order bit. These are very fast things to do. The "chip" does what it is told to do. – Nick Gammon Oct 16 at 9:49
  • @NickGammon I'm solving Differential equations in real time with integers to predict the behaviour of a system and I need to know if it's worth to keep track of the remainders to account for them or not, so far it's looking like it's not worth it though, but I want to explore my options to increase accuracy :) – Beacon of Wierd Oct 16 at 17:23
3

If using optimization, the compiler is smart enough to recognize this.

Since your example is so short, it could be optimized away entirely. To ensure that doesn't happen, the results in c and r have to be used in some way. Also, if a and b could never change, the values of c and r would be calculated during compilation. Therefore, I put the calculation in its own function.

From godbolt.com, using AVR-GCC 9.2.0:

#include<stdint.h>
#include<stdio.h>

uint8_t a = 0;
uint8_t b = 2;
uint8_t c = 0;
uint8_t r = 0;

void calculate() {
    c = a / b;
    r = a % b;
}

int main() {
    a = 7;
    b = 2;

    calculate();

    printf("%d %d", c, r);
}

compiles the calculate() function into

calculate():
        lds r24,a
        lds r22,b
        rcall __udivmodqi4
        sts c,r24
        sts r,r25
        ret

The results, stored in r24 and r25 respectively, are re-used from the same division operation.

| improve this answer | |
  • By having optimizations turned off, you are asking the compiler to not be smart. And it dutifully obeys. No one would ever compile Arduino code this way. The standard Arduino optimization level is -Os, and at this level the compiler is smart enough to optimize your code to the equivalent of return 0;. – Edgar Bonet Oct 16 at 8:05
  • You're right. Though even when making sure the results are used (even by the same statement), and the variables a and b are not constant, it doesn't seem to remember the remainder of the first operation directly: godbolt.org/z/Edzq54 – towe Oct 16 at 8:19
  • 1
    Your new test is flawed again. By having a and b volatile, you tell the compiler that it should not assume their values to be stable. Thus a/b and a%b are two different divisions. – Edgar Bonet Oct 16 at 8:23
  • Ugh, I'm crap at this. You're right, optimization does use only one division if you make sure the variables can't change and also prevent it from calculating it all during compilation. godbolt.org/z/bG4cG6 – towe Oct 16 at 8:58
  • 1
    Using volatile was not a bad idea: it's a convenient way to simulate side-effects, like I/O. You just have to make sure the numbers you are dividing are not themselves volatile. See for example: godbolt.org/z/zGefj9 – Edgar Bonet Oct 16 at 12:11
1

The compiler is only as smart as you provide it the necessary information.

  1. It is good to examine code on godbolt.com. But use it wisely.
    Noone should ever compile without optimizations. In the example above the code is not optimized and thus would never been used as such on a board.
  2. The example is so artificial that the compiler optimizes it away into just 2 instructions. So the code should be representative for the intended usage.
    A better godbolt would be:
#include<stdint.h>
#include<stdlib.h>

void myDiv(uint8_t * c, uint8_t * r, const uint8_t a, const uint8_t b) {
    *c = a/b;
    *r = a%b;
}

So the input is not predetermined and also the resulting numbers are returned and not thrown away. Which translates with -Os to:

myDiv(unsigned char*, unsigned char*, unsigned char, unsigned char):
        mov r27,r25
        mov r26,r24
        mov r31,r23
        mov r30,r22
        mov r24,r20
        mov r22,r18
        rcall __udivmodqi4
        st X,r24
        st Z,r25
        ret
  1. There is the div(numerator, denominator) function in stdlib.h. This function performs a division and returns both the dividend and the remainder. It is optimized for each platform and uses the best available method to get both. In Godbolt it would look like this:
#include<stdint.h>
#include<stdlib.h>

void myDiv2(uint8_t * c, uint8_t * r, const uint8_t a, const uint8_t b) {
    div_t d = div(a, b);
    *c = d.quot;
    *r = d.rem;
}

But what surprise, with -Os the resulting assembly looks exactly the same! (I leave it to the reader to try it on godbolt).

That means, the compiler is smart enough to:

a. recognise the intention when calling division and modulo an the same operands successively.
b. will use the best available method to achieve the intended calculation for you.


EDIT after Edgar Bonet's comment:
While playing around in godbolt I made a copy-paste mistake. div only applies to int values. That makes the resulting assembly code larger as there has twice the data to be shoveld around. After changing both examples to int they look almost similar. The only difference is:

The result is stored in d first and then copied to c and r.
So the division/modulo code is more efficient in that regard as the resulting values are copied directly from the registers used in the calling convention.

https://godbolt.org/z/61exz7

| improve this answer | |
  • Very interesting, +1 Declaring an optimization in my code gets rid of almost all the code, but declaring the variables as volatile prevents that. Even when "volatile", it still does not recognize the potential savings as such, and calculated the division twice. – towe Oct 16 at 6:57
  • if you read the assembler code carefuly you will see that it is not the case. – Kwasmich Oct 16 at 7:00
  • Sorry, I was still talking about my (close to the question) code: godbolt.org/z/jWqdv4 – towe Oct 16 at 7:01
  • I take the code in question as a sample that shows the intention and not the question to be answered. Making everything voaltile forbids optimizations by the compiler. So there is no point in doing so and having -Os. If we stick to the exact code in question then the result would be just two instructions because the input is known at compile time, it does not change and the results of the computations are discarded. – Kwasmich Oct 16 at 7:07
  • +1. In the second example, you mean *c = d.quot; *r = d.rem;. – Edgar Bonet Oct 16 at 8:28

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.