diff options
Diffstat (limited to 'mfbt/MathAlgorithms.h')
-rw-r--r-- | mfbt/MathAlgorithms.h | 47 |
1 files changed, 47 insertions, 0 deletions
diff --git a/mfbt/MathAlgorithms.h b/mfbt/MathAlgorithms.h new file mode 100644 index 0000000..b545fa5 --- /dev/null +++ b/mfbt/MathAlgorithms.h @@ -0,0 +1,47 @@ +/* -*- Mode: C++; tab-width: 2; indent-tabs-mode: nil; c-basic-offset: 2 -*- */ +/* This Source Code Form is subject to the terms of the Mozilla Public + * License, v. 2.0. If a copy of the MPL was not distributed with this + * file, You can obtain one at http://mozilla.org/MPL/2.0/. */ + +/* mfbt maths algorithms. */ + +#ifndef mozilla_MathAlgorithms_h_ +#define mozilla_MathAlgorithms_h_ + +#include "mozilla/Assertions.h" + +namespace mozilla { + +// Greatest Common Divisor +template<typename IntegerType> +MOZ_ALWAYS_INLINE IntegerType +EuclidGCD(IntegerType a, IntegerType b) +{ + // Euclid's algorithm; O(N) in the worst case. (There are better + // ways, but we don't need them for the current use of this algo.) + MOZ_ASSERT(a > 0); + MOZ_ASSERT(b > 0); + + while (a != b) { + if (a > b) { + a = a - b; + } else { + b = b - a; + } + } + + return a; +} + +// Least Common Multiple +template<typename IntegerType> +MOZ_ALWAYS_INLINE IntegerType +EuclidLCM(IntegerType a, IntegerType b) +{ + // Divide first to reduce overflow risk. + return (a / EuclidGCD(a, b)) * b; +} + +} /* namespace mozilla */ + +#endif /* mozilla_MathAlgorithms_h_ */ |