Skip to contentSkip to conversation

: A better approach to compute int_sqrt in lib/int_sqrt.c

PATCH In review Soumyadip Das Mahapatra 2 participants 2 messages Jul 16, 2008 Library code

lore
Share & tools
lore
#0 lore raw

PATCH 1/1 : A better approach to compute int_sqrt in lib/int_sqrt.c

Hello everybody !!
The patch below is what i think is a better approach to
compute int_sqrt().

What about it ?

Thanks !!

---

lib/int_sqrt.c 2008-07-02 11:37:01.000000000 +0530 renamed from lib/int_sqrt.c 2008-04-17 08:19:44.000000000 +0530 +13 -19
@@ -1,4 +1,3 @@
-
 #include <linux/kernel.h>
 #include <linux/module.h>
 
@@ -7,26 +6,21 @@
  * @x: integer of which to calculate the sqrt
  *
  * A very rough approximation to the sqrt() function.
+ * Improved version from the previous one.
  */
 unsigned long int_sqrt(unsigned long x)
 {
-    unsigned long op, res, one;
-
-    op = x;
-    res = 0;
-
-    one = 1UL << (BITS_PER_LONG - 2);
-    while (one > op)
-        one >>= 2;
-
-    while (one != 0) {
-        if (op >= res + one) {
-            op = op - (res + one);
-            res = res +  2 * one;
-        }
-        res /= 2;
-        one /= 4;
-    }
-    return res;
+    unsigned long ub, lb, m;
+    lb = 1;                /* lower bound */
+    ub = (x >> 5) + 8;        /* upper bound */
+    do {
+        m = (ub + lb) >>  1;    /* middle value */
+        if((m * m) > x)
+            ub = m - 1;
+        else
+            lb = m + 1;
+    } while(ub >= lb);
+    
+    return lb - 1;
 }
 EXPORT_SYMBOL(int_sqrt);
#1 lore raw
Quoted 5 lines · Soumyadip Das Mahapatra

Hello everybody !!
The patch below is what i think is a better approach to
compute int_sqrt().

What about it ?

Indeed, what about it?

How is it better;
- is it cheaper
- how so
- on what platform

- it is more accurate
- who needs it

Please provide a little more information about why you suggest this change.

Quoted 11 lines

Thanks !!

---

lib/int_sqrt.c 2008-07-02 11:37:01.000000000 +0530 renamed from lib/int_sqrt.c 2008-04-17 08:19:44.000000000 +0530 +0 -1
@@ -1,4 +1,3 @@
-
 #include <linux/kernel.h>
 #include <linux/module.h>
 

lib/int_sqrt.c 2008-07-02 11:37:01.000000000 +0530 line 9

Quoted 4 lines
lib/int_sqrt.c 2008-07-02 11:37:01.000000000 +0530 renamed from lib/int_sqrt.c 2008-04-17 08:19:44.000000000 +0530 +1 -0
@@ -7,26 +6,21 @@
  * @x: integer of which to calculate the sqrt
  *
  * A very rough approximation to the sqrt() function.
+ * Improved version from the previous one.

With the previuos one being gone, this comment adds little but confusion..

Quoted 45 lines
lib/int_sqrt.c 2008-07-02 11:37:01.000000000 +0530 renamed from lib/int_sqrt.c 2008-04-17 08:19:44.000000000 +0530 +12 -19
  */
 unsigned long int_sqrt(unsigned long x)
 {
-    unsigned long op, res, one;
-
-    op = x;
-    res = 0;
-
-    one = 1UL << (BITS_PER_LONG - 2);
-    while (one > op)
-        one >>= 2;
-
-    while (one != 0) {
-        if (op >= res + one) {
-            op = op - (res + one);
-            res = res +  2 * one;
-        }
-        res /= 2;
-        one /= 4;
-    }
-    return res;
+    unsigned long ub, lb, m;
+    lb = 1;                /* lower bound */
+    ub = (x >> 5) + 8;        /* upper bound */
+    do {
+        m = (ub + lb) >>  1;    /* middle value */
+        if((m * m) > x)
+            ub = m - 1;
+        else
+            lb = m + 1;
+    } while(ub >= lb);
+    
+    return lb - 1;
 }
 EXPORT_SYMBOL(int_sqrt);
 
 
 
 
 
--

To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/