src/core/math_func.cpp

   1 /*
   2  * This file is part of OpenTTD.
   3  * OpenTTD is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation, version 2.
   4  * OpenTTD is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
   5  * See the GNU General Public License for more details. You should have received a copy of the GNU General Public License along with OpenTTD. If not, see <http://www.gnu.org/licenses/>.
   6  */
   7
   8 /** @file math_func.cpp Math functions. */
   9
  10 #include "../stdafx.h"
  11 #include "math_func.hpp"
  12
  13 #include "../safeguards.h"
  14
  15 /**
  16  * Deterministic approximate division.
  17  * Cancels out division errors stemming from the integer nature of the division over multiple runs.
  18  * @param a Dividend.
  19  * @param b Divisor.
  20  * @return a/b or (a/b)+1.
  21  */
  22 int DivideApprox(int a, int b)
  23 {
  24         int random_like = ((a + b) * (a - b)) % b;
  25
  26         int remainder = a % b;
  27
  28         int ret = a / b;
  29         if (abs(random_like) < abs(remainder)) {
  30                 ret += ((a < 0) ^ (b < 0)) ? -1 : 1;
  31         }
  32
  33         return ret;
  34 }
  35
  36 /**
  37  * Compute the integer square root.
  38  * @param num Radicand.
  39  * @return Rounded integer square root.
  40  * @note Algorithm taken from http://en.wikipedia.org/wiki/Methods_of_computing_square_roots
  41  */
  42 uint32_t IntSqrt(uint32_t num)
  43 {
  44         uint32_t res = 0;
  45         uint32_t bit = 1UL << 30; // Second to top bit number.
  46
  47         /* 'bit' starts at the highest power of four <= the argument. */
  48         while (bit > num) bit >>= 2;
  49
  50         while (bit != 0) {
  51                 if (num >= res + bit) {
  52                         num -= res + bit;
  53                         res = (res >> 1) + bit;
  54                 } else {
  55                         res >>= 1;
  56                 }
  57                 bit >>= 2;
  58         }
  59
  60         /* Arithmetic rounding to nearest integer. */
  61         if (num > res) res++;
  62
  63         return res;
  64 }