diff options
Diffstat (limited to 'lib/int_sqrt.c')
| -rw-r--r-- | lib/int_sqrt.c | 34 |
1 files changed, 20 insertions, 14 deletions
diff --git a/lib/int_sqrt.c b/lib/int_sqrt.c index fd355a99327..1ef4cc34497 100644 --- a/lib/int_sqrt.c +++ b/lib/int_sqrt.c @@ -1,6 +1,12 @@ +/* + * Copyright (C) 2013 Davidlohr Bueso <davidlohr.bueso@hp.com> + * + * Based on the shift-and-subtract algorithm for computing integer + * square root from Guy L. Steele. + */ #include <linux/kernel.h> -#include <linux/module.h> +#include <linux/export.h> /** * int_sqrt - rough approximation to sqrt @@ -10,23 +16,23 @@ */ unsigned long int_sqrt(unsigned long x) { - unsigned long op, res, one; + unsigned long b, m, y = 0; - op = x; - res = 0; + if (x <= 1) + return x; - one = 1UL << (BITS_PER_LONG - 2); - while (one > op) - one >>= 2; + m = 1UL << (BITS_PER_LONG - 2); + while (m != 0) { + b = y + m; + y >>= 1; - while (one != 0) { - if (op >= res + one) { - op = op - (res + one); - res = res + 2 * one; + if (x >= b) { + x -= b; + y += m; } - res /= 2; - one /= 4; + m >>= 2; } - return res; + + return y; } EXPORT_SYMBOL(int_sqrt); |