Unnecessary function calls
My quick thought is that you are making an unnecessary function call.
unsigned temp;
while ((temp = a % b)) {
a = b;
b = temp;
}
The thing with the doubled parentheses is a hack to keep some compilers from warning you that you may be doing an unintentional assignment. It should make no functional difference.
This does fewer assignments. Three compared to four in your version. And it makes no function calls. Typically a function call is more involved than an assignment. Because it has to first save the current state, then jump somewhere else and do work, and finally restore the original state. The save and restore steps themselves often involve assignments. And those may be relatively expensive assignments from register to cache or memory. Whereas that loop can be done with three registers (or even two if the compiler optimizes out temp
by doubling the code).
while ((a = a % b)) {
if (!(b = b % a)) {
return a;
}
}
No temp
in that version, but duplicate logic. I wouldn't normally recommend writing that code. But it would be a perfectly legitimate compiler optimization if there is a shortage of available registers.
Note: if you only call this function a few times, this won't make a difference. Use whatever you find more readable. But if you are calling GCD in your main loop, it is possible that efficiency will matter. If efficiency does matter, my revised version (the first one) will (absent compiler optimizations) probably be faster than your version. While premature optimizations are to be avoided, there is little harm in picking the more efficient version if you have two working versions. And GCD is exactly the kind of problem that may be subject to profiling that would lead to that kind of optimization. So many sources may offer the best optimized algorithm rather than an alternative.
I find it a best practice to never use the statement form of control structures and always use the block form. I also prefer the brackets on the same line as the control structure. The latter is very much opinion, but the former is based on actual experience with bugs caused by editing.
Be careful of types
I also find it a bit risky that your variables are unsigned
in the original function but int
in the swap_numbers
function. This presumably works because the unsigned
and int
types use the same storage width. But that's an implementation detail. Is that implementation detail guaranteed always? I don't know off-hand. Perhaps you already did that work and do know. But you don't say that you know and there's no comment explaining when you can and cannot use swap_numbers
.
For example, what would happen if used with an unsigned long
? On some systems, that might work because int
and long
are the same width. On other systems, you may only swap part of the numbers. Possibly only some of the time (because if the bytes that you are swapping happen to be the ones with data, it might not matter).
You might fix this by switching from pointers to handles (pointers to pointers).
void swap_numbers(void **a, void **b)
{
void *temp = *a;
*a = *b;
*b = temp;
}
unsigned euklid_iterative(unsigned *a, unsigned *b)
{
while ((*a = *a % *b))
{
swap_numbers(&a, &b);
}
return *b;
}
But it might be easier just to write a swap_unsigned
function. Or write out the swap entirely as I did originally.
All code in this post is untested. Not even for compilable syntax much less correct logic. Use at your own risk.