Line data Source code
1 : /* Copyright (C) 2010 Wildfire Games.
2 : * This file is part of 0 A.D.
3 : *
4 : * 0 A.D. is free software: you can redistribute it and/or modify
5 : * it under the terms of the GNU General Public License as published by
6 : * the Free Software Foundation, either version 2 of the License, or
7 : * (at your option) any later version.
8 : *
9 : * 0 A.D. is distributed in the hope that it will be useful,
10 : * but WITHOUT ANY WARRANTY; without even the implied warranty of
11 : * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12 : * GNU General Public License for more details.
13 : *
14 : * You should have received a copy of the GNU General Public License
15 : * along with 0 A.D. If not, see <http://www.gnu.org/licenses/>.
16 : */
17 :
18 : #include "precompiled.h"
19 :
20 : #include "Sqrt.h"
21 :
22 : // Based on http://freaknet.org/martin/tape/gos/misc/personal/msc/sqrt/sqrt.html
23 1298 : u32 isqrt64(u64 n)
24 : {
25 1298 : u64 op = n;
26 1298 : u64 res = 0;
27 1298 : u64 one = (u64)1 << 62; // highest power of four <= than the argument
28 :
29 9254 : while (one > op)
30 3978 : one >>= 2;
31 :
32 76414 : while (one != 0)
33 : {
34 37558 : if (op >= res + one)
35 : {
36 19196 : op -= (res + one);
37 19196 : res += (one << 1);
38 : }
39 37558 : res >>= 1;
40 37558 : one >>= 2;
41 : }
42 1298 : return (u32)res;
43 3 : }
44 :
45 : // TODO: This should be equivalent to (u32)sqrt((double)n), and in practice
46 : // that seems to be true for all input, so do we actually need this integer-only
47 : // implementation? i.e. are there any platforms / compiler settings where
48 : // sqrt(double) won't give the correct answer? and is sqrt(double) faster?
|