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?