Re: [PATCH 1/8] add lib/gcd.c

James Cloos
2009-06-13T12:23:17Z

>>>>> "Florian" == Florian Fainelli <florian@openwrt.org> writes:

Florian> This patch adds lib/gcd.c which contains a greatest
Florian> common divider implementation taken from
Florian> sound/core/pcm_timer.c

Would the binary gcd algorithm not be a better fit for the kernel?

It avoids division, using only shifts and subtraction:

unsigned long gcd (unsigned long a, unsigned long b) {
unsigned int shift;
unsigned long d;

if (a == 0 || b == 0)
return a | b;

for (shift = 0; ((a | b) & 1) == 0; ++shift) {
a >>= 1;
b >>= 1;
}

while ((a & 1) == 0)
a >>= 1;

do {
while ((b & 1) == 0)
b >>= 1;

if (a < b) {
b -= a;
} else {
d = a - b;
a = b; b = d;
}
b >>= 1;
} while (b != 0);

return a << shift;
}

-JimC
--