[git commit] factor: don't be too clever in isqrt - be small instead

Denys Vlasenko vda.linux at googlemail.com
Mon Apr 10 16:30:35 UTC 2017


commit: https://git.busybox.net/busybox/commit/?id=cc1f8ba489b809d2c859276ef10094df4bcc74ea
branch: https://git.busybox.net/busybox/commit/?id=refs/heads/master

function                                             old     new   delta
isqrt_odd                                            111      70     -41

Signed-off-by: Denys Vlasenko <vda.linux at googlemail.com>
---
 coreutils/factor.c | 22 ++++++++++++----------
 1 file changed, 12 insertions(+), 10 deletions(-)

diff --git a/coreutils/factor.c b/coreutils/factor.c
index 7400174..11097c1 100644
--- a/coreutils/factor.c
+++ b/coreutils/factor.c
@@ -47,25 +47,27 @@ typedef unsigned long half_t;
 /* Returns such x that x+1 > sqrt(N) */
 static inline half_t isqrt(wide_t N)
 {
-	wide_t mask_2bits;
 	half_t x;
 
-// Never called with N < 1
-//	if (N == 0)
-//		return 0;
+	// Never called with N < 1
+	//if (N == 0)
+	//	return 0;
 
+	x = HALF_MAX;
 	/* First approximation of x+1 > sqrt(N) - all-ones, half as many bits:
 	 * 1xxxxx -> 111 (six bits to three)
 	 * 01xxxx -> 111
 	 * 001xxx -> 011
 	 * 0001xx -> 011 and so on.
 	 */
-	x = HALF_MAX;
-	mask_2bits = TOPMOST_WIDE_BIT | (TOPMOST_WIDE_BIT >> 1);
-	while (!(N & mask_2bits)) {
-		x >>= 1;
-		mask_2bits >>= 2;
-	}
+	// It is actually not performance-critical at all.
+	// Can simply start Newton loop with very conservative x=0xffffffff.
+	//wide_t mask_2bits;
+	//mask_2bits = TOPMOST_WIDE_BIT | (TOPMOST_WIDE_BIT >> 1);
+	//while (!(N & mask_2bits)) {
+	//	x >>= 1;
+	//	mask_2bits >>= 2;
+	//}
 	dbg("x:%"HALF_FMT"x", x);
 
 	for (;;) {


More information about the busybox-cvs mailing list