Re: [PATCH] lib/int_sqrt.c: Optimize square root function

[Anshul Garg]

On Thu, Feb 5, 2015 at 10:33 AM, Linus Torvalds
<torva...@linux-foundation.org> wrote:
> On Thu, Feb 5, 2015 at 10:20 AM, Linus Torvalds
> <torva...@linux-foundation.org> wrote:
>>
>> Hmm. I did that too [..]
>
> Side note: one difference in our results (apart from possibly just CPU
> uarch details) is that my loop goes to 100M to make it easier to just
> time it. Which means that my load essentially had about three more
> iterations over nonzero data.
>
>                          Linus

I have also done the same testing on 100 million numbers.
Attaching source codes.

Below is the result ::

int_sqrt_old - current
int_sqrt_new -  With proposed change

anshul@ubuntu:~/kernel_latest/sqrt$ time ./int_sqrt_old

real    0m41.895s
user    0m36.490s
sys    0m0.365s

anshul@ubuntu:~/kernel_latest/sqrt$ time ./int_sqrt_new

real    0m39.491s
user    0m36.495s
sys    0m0.338s


I have run this test on Intel(R) Core(TM) i3-4000M CPU @ 2.40GHz VMWare Machine.
Please check if i am doing anything wrong.

NOTE ::
I have not used gcc optimizations while compilation.
With O2 level optimization proposed solution is taking more time.

/*
 * Copyright (C) 2013 Davidlohr Bueso <davidlohr.bu...@hp.com>
 *
 *  Based on the shift-and-subtract algorithm for computing integer
 *  square root from Guy L. Steele.
 */

#include <stdio.h>
/**
 * int_sqrt - rough approximation to sqrt
 * @x: integer of which to calculate the sqrt
 *
 * A very rough approximation to the sqrt() function.
 */
#define BITS_PER_LONG (8*sizeof(long))

unsigned long int_sqrt(unsigned long x)
{
	unsigned long b, m, y = 0;

	if (x <= 1)
		return x;

	m = 1UL << (BITS_PER_LONG - 2);
	while (m != 0) {
		b = y + m;
		y >>= 1;

		if (x >= b) {
			x -= b;
			y += m;
		}
		m >>= 2;
	}

	return y;
}

int main()
{
	unsigned long n = 1;
	for(;n<=100000000;++n)
		int_sqrt(n);
	return 0;
}

/*
 * Copyright (C) 2013 Davidlohr Bueso <davidlohr.bu...@hp.com>
 *
 *  Based on the shift-and-subtract algorithm for computing integer
 *  square root from Guy L. Steele.
 */

#include <stdio.h>

#define BITS_PER_LONG (8*sizeof(long))

/**
 * int_sqrt - rough approximation to sqrt
 * @x: integer of which to calculate the sqrt
 *
 * A very rough approximation to the sqrt() function.
 */
unsigned long int_sqrt(unsigned long x)
{
	unsigned long b, m, y = 0;

	if (x <= 1)
		return x;

	m = 1UL << (BITS_PER_LONG - 2);

	while(m > x )
		m >>= 2;

	while (m != 0) {
		b = y + m;
		y >>= 1;

		if (x >= b) {
			x -= b;
			y += m;
		}
		m >>= 2;
	}

	return y;
}

int main()
{
	unsigned long n = 1;
	for(;n<=100000000;++n)
		int_sqrt(n);
	return 0;
}