int_sqrt.c 652 Bytes
Newer Older
1 2 3 4 5 6
/*
 * 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.
 */
Linus Torvalds's avatar
Linus Torvalds committed
7 8

#include <linux/kernel.h>
9
#include <linux/export.h>
Linus Torvalds's avatar
Linus Torvalds committed
10 11 12 13 14 15 16 17 18

/**
 * 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)
{
19
	unsigned long b, m, y = 0;
Linus Torvalds's avatar
Linus Torvalds committed
20

21 22
	if (x <= 1)
		return x;
Linus Torvalds's avatar
Linus Torvalds committed
23

24 25 26 27
	m = 1UL << (BITS_PER_LONG - 2);
	while (m != 0) {
		b = y + m;
		y >>= 1;
Linus Torvalds's avatar
Linus Torvalds committed
28

29 30 31
		if (x >= b) {
			x -= b;
			y += m;
Linus Torvalds's avatar
Linus Torvalds committed
32
		}
33
		m >>= 2;
Linus Torvalds's avatar
Linus Torvalds committed
34
	}
35 36

	return y;
Linus Torvalds's avatar
Linus Torvalds committed
37 38
}
EXPORT_SYMBOL(int_sqrt);