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

[James Cloos <cloos@jhcloos.com>]

>>>>> "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
-- 
James Cloos <cloos@jhcloos.com>         OpenPGP: 1024D/ED7DAEA6