source/maths/Sqrt.cpp

   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 u32 isqrt64(u64 n)
  24 {
  25         u64 op = n;
  26         u64 res = 0;
  27         u64 one = (u64)1 << 62; // highest power of four <= than the argument
  28
  29         while (one > op)
  30                 one >>= 2;
  31
  32         while (one != 0)
  33         {
  34                 if (op >= res + one)
  35                 {
  36                         op -= (res + one);
  37                         res += (one << 1);
  38                 }
  39                 res >>= 1;
  40                 one >>= 2;
  41         }
  42         return (u32)res;
  43 }
  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?