Davidlohr Bueso | 30493cc | 2013-04-29 16:18:09 -0700 | [diff] [blame] | 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 | */ | ||||
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 7 | |
8 | #include <linux/kernel.h> | ||||
Paul Gortmaker | 8bc3bcc | 2011-11-16 21:29:17 -0500 | [diff] [blame] | 9 | #include <linux/export.h> |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 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 | { | ||||
Davidlohr Bueso | 30493cc | 2013-04-29 16:18:09 -0700 | [diff] [blame] | 19 | unsigned long b, m, y = 0; |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 20 | |
Davidlohr Bueso | 30493cc | 2013-04-29 16:18:09 -0700 | [diff] [blame] | 21 | if (x <= 1) |
22 | return x; | ||||
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 23 | |
Davidlohr Bueso | 30493cc | 2013-04-29 16:18:09 -0700 | [diff] [blame] | 24 | m = 1UL << (BITS_PER_LONG - 2); |
Peter Zijlstra | e6008a0 | 2017-11-17 15:28:04 -0800 | [diff] [blame] | 25 | while (m > x) |
26 | m >>= 2; | ||||
27 | |||||
Davidlohr Bueso | 30493cc | 2013-04-29 16:18:09 -0700 | [diff] [blame] | 28 | while (m != 0) { |
29 | b = y + m; | ||||
30 | y >>= 1; | ||||
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 31 | |
Davidlohr Bueso | 30493cc | 2013-04-29 16:18:09 -0700 | [diff] [blame] | 32 | if (x >= b) { |
33 | x -= b; | ||||
34 | y += m; | ||||
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 35 | } |
Davidlohr Bueso | 30493cc | 2013-04-29 16:18:09 -0700 | [diff] [blame] | 36 | m >>= 2; |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 37 | } |
Davidlohr Bueso | 30493cc | 2013-04-29 16:18:09 -0700 | [diff] [blame] | 38 | |
39 | return y; | ||||
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 40 | } |
41 | EXPORT_SYMBOL(int_sqrt); |