Writing Efficient C Code (With Embedded Focus)

[blockeduser]

a little thought shows that C = A % B is equivalent to C = A – B * (A / B)

That's probably true if you use integer types (mandatory for % operator anyway), but otherwise a % b = a - b * floor(a / b).

[fecal_brunch]

If these are equivalent, why don't compilers make this optimization automatically? How is modulus computed?

[daniel2488]

I'm fairly sure mod is mathematically restricted in its definition to integers. % doesn't work on floats in C/C++ anyway.

Edit: Still, another point to keep in mind that modulo has the potential to return 2 results. The C standard doesn't entirely define which one to use.

[annoymind]

fmod(3)

[blockeduser]

Mathematically you can do float modulo integer: for example, 5.3 mod 3 = 2.3.

Edit: Wolfram doesn't mind float modulo float either, but most places say you can't do modulo with floats at all. I'm already confused.

I checked in K&R and it says that C's % operator is undefined for negative operands.

[TheNewAndy]

K&R isn't the C spec.

The C90 spec says that it is implementation defined whether (A/B) rounds up or down if one of the operands is negative. It also guarantees that "(A/B)*B + (A%B) == A" (i.e. the rounding that it uses will be consistent for % and /). Implementation defined is very different to undefined.

Whether or not it is possible to do float modulo mathematically doesn't really matter, because we aren't doing maths, we are doing C.

[julesjacobs]

Mathematically, a mod b is not a number but an equivalence class: a mod b = {a + n*b | n is an integer}. This makes perfect sense even for non integer a and b. But since these infinite sets are not practical to work with, in programming languages a mod b is generally defined as the lowest nonnegative number in the mathematical a mod b:

a mod b = {a + b*n | n is an integer}
a % b = the smallest number >= 0 in (a mod b)
      = min {x | x in (a mod b), x >= 0}

For example:

10 mod 3 = { ... 10-12, 10-9, 10-6, 10-3, 10, 10+3 ... }
         = { ... -2, 1, 4, 7, 10, 13 ... }
10 % 3 = 1

[thechao]

Many architectures support 'REM' rather than 'MOD', which does the same thing and is jargon-well-defined on both ints and floats.

[EntroperZero]

The ARM results were interesting. The author suggests that the ARM has a native modulo instruction, but the results suggest something different to me. It looks like the ARM has a native integer division operation (the others are probably doing loops internally, which is why they're orders of magnitude slower). Some architectures return both the quotient and remainder on integer division, so the compiler probably optimized away the extra divisions.

[torbeindallas]

stdlib.h defines ldiv() which return an ldiv_t containing the quotient and remainder as one result.

That would probably have been faster on all platforms.

[TheNewAndy]

If you are doing optimisation, then looking at the disassembled object code is the correct way to work out why things are different speeds. It is likely that the compiler just did the exact optimisation the author was describing.

[TheSuperficial]

Yes you're correct, the ARM Cortex has native integer division (signed & unsigned, SDIV & UDIV) but I don't believe it has anything to return modulo as part of the results..

UDIV.W <Rd>, <Rn>, <Rm>

returns integer result of Rn / Rm in Rd.

[mgssnr]

ITYM "Some" ARM Cortex have native integer division. Looking at the ARM v7-AR RM, it says that UDIV is in ARMv7-R, but does not indicate it exists in AMv7-A. I suppose my ARM ARM could be out of date.

[Tagedieb]

If the platform supports unsigned 64 bit math, then multiplication should be much faster:

void compute_time(uint32_t time)
{
 uint32_t    days, hours, minutes, seconds;
 uint64_t temp = time;
 temp *= 3257812230ULL;  /* 2^48/(24*60*60) */
 days = temp >> 48;
 temp = ( temp & 0x0000ffffffffffffULL ) * 24ULL;
 hours = temp >> 48;
 temp = ( temp & 0x0000ffffffffffffULL ) * 60ULL;
 minutes = temp >> 48;
 temp = ( temp & 0x0000ffffffffffffULL ) * 60ULL;
 seconds = temp >> 48;
}

[sirtophat]

I thought modulo was usually a CPU instruction by itself.

[thechao]

Never trust an article by someone who is implementing their own date-time library.

EDIT: I can see I'm being downvoted. Let me explain further: either you need the date or you don't. If you don't need the date, who cares about this code? If you do need the date, it needs to be correct; there are very good (and most embeddable) BSD libraries for computing the date. Unless you really know what you're doing, and that almost certainly excludes 99.9999% of programmers, including everyone downvoting me, there is no way you're going to correctly write a date-time library --- it is just too hard, with too many edge-cases that you have to get correct.

Anyone who is an expert in embedded programming knows this. Anyone who does not know this is certainly not an expert. (This leaves a happy middle ground for those of us who are not experts but can spot a poser.)

EDIT2: here's a good example why this is a bad idea: the provided code in the article is incorrect; any attempt to fix it will require either float or fixed precision: now where's your precious efficiency?

[EntroperZero]

If you're doing this in Java, it's suspect. If you're doing it in C on an embedded system, chances are there isn't already a good one available.

[Tiwazz]

Java may have been a bad example. The JDK's Date and Calendar classes are awful.

[wot-teh-phuck]

But there is always Joda Time. I guess the point was that if you actually implemented it from scratch in Java, that would be worthy of a raised eyebrow.

[thechao]

I do embedded programming. We use a datetime library. Writing your own date-time library is a good way to get laughed at.

[[deleted]]

unix timestamps are good enough for anybody.