# HG changeset patch
# User rubidium <rubidium@openttd.org>
# Date 2009-03-21 01:34:31
# Node ID 66dd9ef9c484696bdca3e0bfa0857ff80df4947a
# Parent  08bc85c93304cb98f675478339100ac4d27a8ef4

(svn r15777) -Add: helper functions to get the least common multiple and the greatest common divisor (Alberth)

diff --git a/projects/openttd_vs80.vcproj b/projects/openttd_vs80.vcproj
--- a/projects/openttd_vs80.vcproj
+++ b/projects/openttd_vs80.vcproj
@@ -1672,6 +1672,10 @@
 				>
 			</File>
 			<File
+				RelativePath=".\..\src\core\math_func.cpp"
+				>
+			</File>
+			<File
 				RelativePath=".\..\src\core\math_func.hpp"
 				>
 			</File>
diff --git a/projects/openttd_vs90.vcproj b/projects/openttd_vs90.vcproj
--- a/projects/openttd_vs90.vcproj
+++ b/projects/openttd_vs90.vcproj
@@ -1669,6 +1669,10 @@
 				>
 			</File>
 			<File
+				RelativePath=".\..\src\core\math_func.cpp"
+				>
+			</File>
+			<File
 				RelativePath=".\..\src\core\math_func.hpp"
 				>
 			</File>
diff --git a/source.list b/source.list
--- a/source.list
+++ b/source.list
@@ -363,6 +363,7 @@ core/endian_func.hpp
 core/endian_type.hpp
 core/enum_type.hpp
 core/geometry_type.hpp
+core/math_func.cpp
 core/math_func.hpp
 core/mem_func.hpp
 core/overflowsafe_type.hpp
diff --git a/src/core/math_func.cpp b/src/core/math_func.cpp
new file mode 100644
--- /dev/null
+++ b/src/core/math_func.cpp
@@ -0,0 +1,41 @@
+/* $Id$ */
+
+/** @file math_func.cpp Math functions. */
+
+#include "../stdafx.h"
+#include "math_func.hpp"
+
+/**
+ * Compute least common multiple (lcm) of arguments \a a and \a b, the smallest
+ * integer value that is a multiple of both \a a and \a b.
+ * @param a First number.
+ * @param b second number.
+ * @return Least common multiple of values \a a and \a b.
+ *
+ * @note This function only works for non-negative values of \a a and \a b.
+ */
+int LeastCommonMultiple(int a, int b)
+{
+	if (a == 0 || b == 0) return 0; // By definition.
+	if (a == 1 || a == b) return b;
+	if (b == 1) return a;
+
+	return a * b / GreatestCommonDivisor(a, b);
+}
+
+/**
+ * Compute greatest common divisor (gcd) of \a a and \a b.
+ * @param a First number.
+ * @param b second number.
+ * @return Greatest common divisor of \a a and \a b.
+ */
+int GreatestCommonDivisor(int a, int b)
+{
+	while (b != 0) {
+		int t = b;
+		b = a % b;
+		a = t;
+	}
+	return a;
+
+}
diff --git a/src/core/math_func.hpp b/src/core/math_func.hpp
--- a/src/core/math_func.hpp
+++ b/src/core/math_func.hpp
@@ -264,4 +264,7 @@ static FORCEINLINE void Swap(T &a, T &b)
 	b = t;
 }
 
+int LeastCommonMultiple(int a, int b);
+int GreatestCommonDivisor(int a, int b);
+
 #endif /* MATH_FUNC_HPP */