/*
 * 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.
 */

#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 __attribute__((noinline)) int_sqrt(unsigned long x)
{
	unsigned long b, m, y = 0;

	if (x <= 1)
		return x;

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

#ifdef REDUCE
	while (m > x)
		m >>= 2;
#elif defined(ONCE)
	{
		unsigned long n = m >> (BITS_PER_LONG/2);
		m = (n >= x) ? n : m;
	}
#endif
	while (m != 0) {
		b = y + m;
		y >>= 1;

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

	return y;
}

int main(int argc, char **argv)
{
	unsigned long i;

	for (i = 0; i < 100000000; i++) {
		unsigned long a = int_sqrt(i);
		asm volatile("": : "r" (a));
	}
	return 0;
}