OpenTTD
math_func.cpp
Go to the documentation of this file.
1 /* $Id: math_func.cpp 26482 2014-04-23 20:13:33Z rubidium $ */
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 
12 #include "../stdafx.h"
13 #include "math_func.hpp"
14 
15 #include "../safeguards.h"
16 
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 
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 
59 int DivideApprox(int a, int b)
60 {
61  int random_like = ((a + b) * (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 
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 }
int DivideApprox(int a, int b)
Deterministic approximate division.
Definition: math_func.cpp:59
int LeastCommonMultiple(int a, int b)
Compute least common multiple (lcm) of arguments a and b, the smallest integer value that is a multip...
Definition: math_func.cpp:26
int GreatestCommonDivisor(int a, int b)
Compute greatest common divisor (gcd) of a and b.
Definition: math_func.cpp:41
Integer math functions.
static T abs(const T a)
Returns the absolute value of (scalar) variable.
Definition: math_func.hpp:83
uint32 IntSqrt(uint32 num)
Compute the integer square root.
Definition: math_func.cpp:79