Translations update
[openttd/fttd.git] / src / core / math_func.cpp
blob8c136c0bb6516e330c6ac5f45f6a166191dae8c1
1 /* $Id$ */
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 */
10 /** @file math_func.cpp Math functions. */
12 #include "../stdafx.h"
13 #include "math_func.hpp"
15 /**
16 * Compute least common multiple (lcm) of arguments \a a and \a b, the smallest
17 * integer value that is a multiple of both \a a and \a b.
18 * @param a First number.
19 * @param b second number.
20 * @return Least common multiple of values \a a and \a b.
22 * @note This function only works for non-negative values of \a a and \a b.
24 int LeastCommonMultiple(int a, int b)
26 if (a == 0 || b == 0) return 0; // By definition.
27 if (a == 1 || a == b) return b;
28 if (b == 1) return a;
30 return a * b / GreatestCommonDivisor(a, b);
33 /**
34 * Compute greatest common divisor (gcd) of \a a and \a b.
35 * @param a First number.
36 * @param b second number.
37 * @return Greatest common divisor of \a a and \a b.
39 int GreatestCommonDivisor(int a, int b)
41 while (b != 0) {
42 int t = b;
43 b = a % b;
44 a = t;
46 return a;
50 /**
51 * Deterministic approximate division.
52 * Cancels out division errors stemming from the integer nature of the division over multiple runs.
53 * @param a Dividend.
54 * @param b Divisor.
55 * @return a/b or (a/b)+1.
57 int DivideApprox(int a, int b)
59 int random_like = ((a + b) * (a - b)) % b;
61 int remainder = a % b;
63 int ret = a / b;
64 if (abs(random_like) < abs(remainder)) {
65 ret += ((a < 0) ^ (b < 0)) ? -1 : 1;
68 return ret;
71 /**
72 * Compute the integer square root.
73 * @param num Radicand.
74 * @return Rounded integer square root.
75 * @note Algorithm taken from http://en.wikipedia.org/wiki/Methods_of_computing_square_roots
77 uint32 IntSqrt(uint32 num)
79 uint32 res = 0;
80 uint32 bit = 1UL << 30; // Second to top bit number.
82 /* 'bit' starts at the highest power of four <= the argument. */
83 while (bit > num) bit >>= 2;
85 while (bit != 0) {
86 if (num >= res + bit) {
87 num -= res + bit;
88 res = (res >> 1) + bit;
89 } else {
90 res >>= 1;
92 bit >>= 2;
95 /* Arithmetic rounding to nearest integer. */
96 if (num > res) res++;
98 return res;