[deliverable/linux.git] / lib / int_sqrt.c

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

/**
 * 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 != 0) {
		b = y + m;
		y >>= 1;

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

	return y;
}
EXPORT_SYMBOL(int_sqrt);
Commit	Line	Data
30493cc9 DB	1	/*
	2	* Copyright (C) 2013 Davidlohr Bueso <davidlohr.bueso@hp.com>
	3	*
	4	* Based on the shift-and-subtract algorithm for computing integer
	5	* square root from Guy L. Steele.
	6	*/
1da177e4 LT	7
1da177e4 LT	8	#include <linux/kernel.h>
8bc3bcc9	9	#include <linux/export.h>
1da177e4 LT	10
	11	/**
	12	* int_sqrt - rough approximation to sqrt
	13	* @x: integer of which to calculate the sqrt
	14	*
	15	* A very rough approximation to the sqrt() function.
	16	*/
	17	unsigned long int_sqrt(unsigned long x)
	18	{
30493cc9	19	unsigned long b, m, y = 0;
1da177e4	20
30493cc9 DB	21	if (x <= 1)
30493cc9 DB	22	return x;
1da177e4	23
30493cc9 DB	24	m = 1UL << (BITS_PER_LONG - 2);
	25	while (m != 0) {
	26	b = y + m;
	27	y >>= 1;
1da177e4	28
30493cc9 DB	29	if (x >= b) {
	30	x -= b;
	31	y += m;
1da177e4	32	}
30493cc9	33	m >>= 2;
1da177e4	34	}
30493cc9 DB	35
30493cc9 DB	36	return y;
1da177e4 LT	37	}
1da177e4 LT	38	EXPORT_SYMBOL(int_sqrt);