src/core/math_func.cpp

   1 /* $Id: math_func.cpp 25347 2013-06-09 12:50:33Z fonsinchen $ */
   2
   3 /*
   4  * This file is part of OpenTTD.
   5  * 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.
   6  * 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.
   7  * 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/>.
   8  */
   9
  10 /** @file math_func.cpp Math functions. */
  11
  12 #include "../stdafx.h"
  13 #include "math_func.hpp"
  14
  15 #include "../safeguards.h"
  16
  17 /**
  18  * Compute least common multiple (lcm) of arguments \a a and \a b, the smallest
  19  * integer value that is a multiple of both \a a and \a b.
  20  * @param a First number.
  21  * @param b second number.
  22  * @return Least common multiple of values \a a and \a b.
  23  *
  24  * @note This function only works for non-negative values of \a a and \a b.
  25  */
  26 int LeastCommonMultiple(int a, int b)
  27 {
  28         if (a == 0 || b == 0) return 0; // By definition.
  29         if (a == 1 || a == b) return b;
  30         if (b == 1) return a;
  31
  32         return a * b / GreatestCommonDivisor(a, b);
  33 }
  34
  35 /**
  36  * Compute greatest common divisor (gcd) of \a a and \a b.
  37  * @param a First number.
  38  * @param b second number.
  39  * @return Greatest common divisor of \a a and \a b.
  40  */
  41 int GreatestCommonDivisor(int a, int b)
  42 {
  43         while (b != 0) {
  44                 int t = b;
  45                 b = a % b;
  46                 a = t;
  47         }
  48         return a;
  49
  50 }
  51
  52 /**
  53  * Deterministic approximate division.
  54  * Cancels out division errors stemming from the integer nature of the division over multiple runs.
  55  * @param a Dividend.
  56  * @param b Divisor.
  57  * @return a/b or (a/b)+1.
  58  */
  59 int DivideApprox(int a, int b)
  60 {
  61         int random_like = (((int64)(a + b)) * ((int64)(a - b))) % b;
  62
  63         int remainder = a % b;
  64
  65         int ret = a / b;
  66         if (abs(random_like) < abs(remainder)) {
  67                 ret += ((a < 0) ^ (b < 0)) ? -1 : 1;
  68         }
  69
  70         return ret;
  71 }
  72
  73 /**
  74  * Compute the integer square root.
  75  * @param num Radicand.
  76  * @return Rounded integer square root.
  77  * @note Algorithm taken from http://en.wikipedia.org/wiki/Methods_of_computing_square_roots
  78  */
  79 uint32 IntSqrt(uint32 num)
  80 {
  81         uint32 res = 0;
  82         uint32 bit = 1UL << 30; // Second to top bit number.
  83
  84         /* 'bit' starts at the highest power of four <= the argument. */
  85         while (bit > num) bit >>= 2;
  86
  87         while (bit != 0) {
  88                 if (num >= res + bit) {
  89                         num -= res + bit;
  90                         res = (res >> 1) + bit;
  91                 } else {
  92                         res >>= 1;
  93                 }
  94                 bit >>= 2;
  95         }
  96
  97         /* Arithmetic rounding to nearest integer. */
  98         if (num > res) res++;
  99
 100         return res;
 101 }