int_sqrt.c 688 Bytes
Newer Older
1
// SPDX-License-Identifier: GPL-2.0
2 3 4 5 6 7
/*
 * 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
8 9

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

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

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

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

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

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