Blame view
lib/gcd.c
1.26 KB
d28292246 lib: add lib/gcd.c |
1 2 |
#include <linux/kernel.h> #include <linux/gcd.h> |
8bc3bcc93 lib: reduce the u... |
3 |
#include <linux/export.h> |
d28292246 lib: add lib/gcd.c |
4 |
|
fff7fb0b2 lib/GCD.c: use bi... |
5 6 7 8 9 10 11 12 13 14 15 |
/* * This implements the binary GCD algorithm. (Often attributed to Stein, * but as Knuth has noted, appears in a first-century Chinese math text.) * * This is faster than the division-based algorithm even on x86, which * has decent hardware division. */ #if !defined(CONFIG_CPU_NO_EFFICIENT_FFS) && !defined(CPU_NO_EFFICIENT_FFS) /* If __ffs is available, the even/odd algorithm benchmarks slower. */ |
d28292246 lib: add lib/gcd.c |
16 17 |
unsigned long gcd(unsigned long a, unsigned long b) { |
fff7fb0b2 lib/GCD.c: use bi... |
18 19 20 21 |
unsigned long r = a | b; if (!a || !b) return r; |
d28292246 lib: add lib/gcd.c |
22 |
|
fff7fb0b2 lib/GCD.c: use bi... |
23 24 25 |
b >>= __ffs(b); if (b == 1) return r & -r; |
e96875677 lib/gcd.c: preven... |
26 |
|
fff7fb0b2 lib/GCD.c: use bi... |
27 28 29 30 31 32 33 34 35 36 |
for (;;) { a >>= __ffs(a); if (a == 1) return r & -r; if (a == b) return a << __ffs(r); if (a < b) swap(a, b); a -= b; |
d28292246 lib: add lib/gcd.c |
37 |
} |
d28292246 lib: add lib/gcd.c |
38 |
} |
fff7fb0b2 lib/GCD.c: use bi... |
39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 |
#else /* If normalization is done by loops, the even/odd algorithm is a win. */ unsigned long gcd(unsigned long a, unsigned long b) { unsigned long r = a | b; if (!a || !b) return r; /* Isolate lsbit of r */ r &= -r; while (!(b & r)) b >>= 1; if (b == r) return r; for (;;) { while (!(a & r)) a >>= 1; if (a == r) return r; if (a == b) return a; if (a < b) swap(a, b); a -= b; a >>= 1; if (a & r) a += b; a >>= 1; } } #endif |
d28292246 lib: add lib/gcd.c |
77 |
EXPORT_SYMBOL_GPL(gcd); |