| |
| [section:gcd_lcm Greatest Common Divisor and Least Common Multiple] |
| |
| [section Introduction] |
| |
| The class and function templates in <boost/math/common_factor.hpp> |
| provide run-time and compile-time evaluation of the greatest common divisor |
| (GCD) or least common multiple (LCM) of two integers. |
| These facilities are useful for many numeric-oriented generic |
| programming problems. |
| |
| [endsect] |
| |
| [section Synopsis] |
| |
| namespace boost |
| { |
| namespace integer |
| { |
| |
| template < typename IntegerType > |
| class gcd_evaluator; |
| template < typename IntegerType > |
| class lcm_evaluator; |
| |
| template < typename IntegerType > |
| constexpr IntegerType gcd( IntegerType const &a, IntegerType const &b ); |
| template < typename IntegerType > |
| constexpr IntegerType lcm( IntegerType const &a, IntegerType const &b ); |
| template < typename IntegerType, typename... Args > |
| constexpr IntegerType gcd( IntegerType const &a, IntegerType const &b, Args const&... ); |
| template < typename IntegerType, typename... Args > |
| constexpr IntegerType lcm( IntegerType const &a, IntegerType const &b, Args const&... ); |
| |
| template <typename I> |
| std::pair<typename std::iterator_traits<I>::value_type, I> |
| gcd_range(I first, I last); |
| template <typename I> |
| std::pair<typename std::iterator_traits<I>::value_type, I> |
| lcm_range(I first, I last); |
| |
| typedef ``['see-below]`` static_gcd_type; |
| |
| template < static_gcd_type Value1, static_gcd_type Value2 > |
| struct static_gcd; |
| template < static_gcd_type Value1, static_gcd_type Value2 > |
| struct static_lcm; |
| |
| } |
| } |
| |
| [endsect] |
| |
| [section GCD Function Object] |
| |
| [*Header: ] [@../../../../boost/integer/common_factor_rt.hpp <boost/integer/common_factor_rt.hpp>] |
| |
| template < typename IntegerType > |
| class boost::integer::gcd_evaluator |
| { |
| public: |
| // Types |
| typedef IntegerType result_type; |
| typedef IntegerType first_argument_type; |
| typedef IntegerType second_argument_type; |
| |
| // Function object interface |
| constexpr result_type operator ()( |
| first_argument_type const &a, |
| second_argument_type const &b ) const; |
| }; |
| |
| The boost::integer::gcd_evaluator class template defines a function object |
| class to return the greatest common divisor of two integers. |
| The template is parameterized by a single type, called IntegerType here. |
| This type should be a numeric type that represents integers. |
| The result of the function object is always nonnegative, even if either of |
| the operator arguments is negative. |
| |
| This function object class template is used in the corresponding version of |
| the GCD function template. If a numeric type wants to customize evaluations |
| of its greatest common divisors, then the type should specialize on the |
| gcd_evaluator class template. |
| |
| Note that these function objects are `constexpr` in C++14 and later only. |
| They are also declared `noexcept` when appropriate. |
| |
| [endsect] |
| |
| [section LCM Function Object] |
| |
| [*Header: ] [@../../../../boost/integer/common_factor_rt.hpp <boost/integer/common_factor_rt.hpp>] |
| |
| template < typename IntegerType > |
| class boost::integer::lcm_evaluator |
| { |
| public: |
| // Types |
| typedef IntegerType result_type; |
| typedef IntegerType first_argument_type; |
| typedef IntegerType second_argument_type; |
| |
| // Function object interface |
| constexpr result_type operator ()( |
| first_argument_type const &a, |
| second_argument_type const &b ) const; |
| }; |
| |
| The boost::integer::lcm_evaluator class template defines a function object |
| class to return the least common multiple of two integers. The template |
| is parameterized by a single type, called IntegerType here. This type |
| should be a numeric type that represents integers. The result of the |
| function object is always nonnegative, even if either of the operator |
| arguments is negative. If the least common multiple is beyond the range |
| of the integer type, the results are undefined. |
| |
| This function object class template is used in the corresponding version |
| of the LCM function template. If a numeric type wants to customize |
| evaluations of its least common multiples, then the type should |
| specialize on the lcm_evaluator class template. |
| |
| Note that these function objects are constexpr in C++14 and later only. |
| They are also declared `noexcept` when appropriate. |
| |
| [endsect] |
| |
| [section:run_time Run-time GCD & LCM Determination] |
| |
| [*Header: ] [@../../../../boost/integer/common_factor_rt.hpp <boost/integer/common_factor_rt.hpp>] |
| |
| template < typename IntegerType > |
| constexpr IntegerType boost::integer::gcd( IntegerType const &a, IntegerType const &b ); |
| |
| template < typename IntegerType > |
| constexpr IntegerType boost::integer::lcm( IntegerType const &a, IntegerType const &b ); |
| |
| template < typename IntegerType, typename... Args > |
| constexpr IntegerType gcd( IntegerType const &a, IntegerType const &b, Args const&... ); |
| |
| template < typename IntegerType, typename... Args > |
| constexpr IntegerType lcm( IntegerType const &a, IntegerType const &b, Args const&... ); |
| |
| template <typename I> |
| std::pair<typename std::iterator_traits<I>::value_type, I> |
| gcd_range(I first, I last); |
| |
| template <typename I> |
| std::pair<typename std::iterator_traits<I>::value_type, I> |
| lcm_range(I first, I last); |
| |
| The boost::integer::gcd function template returns the greatest common |
| (nonnegative) divisor of the two integers passed to it. |
| `boost::integer::gcd_range` is the iteration of the above gcd algorithm over a |
| range, returning the greatest common divisor of all the elements. The algorithm |
| terminates when the gcd reaches unity or the end of the range. Thus it also |
| returns the iterator after the last element inspected because this may not be |
| equal to the end of the range. The variadic version of `gcd` behaves similarly |
| but does not indicate which input value caused the gcd to reach unity. |
| |
| The boost::integer::lcm function template returns the least common |
| (nonnegative) multiple of the two integers passed to it. |
| As with gcd, there are range and variadic versions of the function for |
| more than 2 arguments. |
| |
| Note that these functions are constexpr in C++14 and later only. |
| They are also declared `noexcept` when appropriate. |
| |
| [endsect] |
| |
| [section:compile_time Compile time GCD and LCM determination] |
| |
| [note These functions are deprecated in favor of constexpr `gcd` and `lcm` on C++14 capable compilers.] |
| |
| [*Header: ] [@../../../../boost/integer/common_factor_ct.hpp <boost/integer/common_factor_ct.hpp>] |
| |
| typedef ``['unspecified]`` static_gcd_type; |
| |
| template < static_gcd_type Value1, static_gcd_type Value2 > |
| struct boost::integer::static_gcd : public mpl::integral_c<static_gcd_type, implementation_defined> |
| { |
| }; |
| |
| template < static_gcd_type Value1, static_gcd_type Value2 > |
| struct boost::integer::static_lcm : public mpl::integral_c<static_gcd_type, implementation_defined> |
| { |
| }; |
| |
| The type `static_gcd_type` is the widest unsigned-integer-type that is supported |
| for use in integral-constant-expressions by the compiler. Usually this |
| the same type as `boost::uintmax_t`, but may fall back to being `unsigned long` |
| for some older compilers. |
| |
| The boost::integer::static_gcd and boost::integer::static_lcm class templates |
| take two value-based template parameters of the ['static_gcd_type] type |
| and inherit from the type `boost::mpl::integral_c`. |
| Inherited from the base class, they have a member /value/ |
| that is the greatest common factor or least |
| common multiple, respectively, of the template arguments. |
| A compile-time error will occur if the least common multiple |
| is beyond the range of `static_gcd_type`. |
| |
| [h3 Example] |
| |
| #include <boost/integer/common_factor.hpp> |
| #include <algorithm> |
| #include <iterator> |
| #include <iostream> |
| |
| int main() |
| { |
| using std::cout; |
| using std::endl; |
| |
| cout << "The GCD and LCM of 6 and 15 are " |
| << boost::integer::gcd(6, 15) << " and " |
| << boost::integer::lcm(6, 15) << ", respectively." |
| << endl; |
| |
| cout << "The GCD and LCM of 8 and 9 are " |
| << boost::integer::static_gcd<8, 9>::value |
| << " and " |
| << boost::integer::static_lcm<8, 9>::value |
| << ", respectively." << endl; |
| |
| int a[] = { 4, 5, 6 }, b[] = { 7, 8, 9 }, c[3]; |
| std::transform( a, a + 3, b, c, boost::integer::gcd_evaluator<int>() ); |
| std::copy( c, c + 3, std::ostream_iterator<int>(cout, " ") ); |
| } |
| |
| [endsect] |
| |
| [section:gcd_header Header <boost/integer/common_factor.hpp>] |
| |
| This header simply includes the headers |
| [@../../../../boost/integer/common_factor_ct.hpp <boost/integer/common_factor_ct.hpp>] |
| and [@../../../../boost/integer/common_factor_rt.hpp <boost/integer/common_factor_rt.hpp>]. |
| |
| Note this is a legacy header: it used to contain the actual implementation, |
| but the compile-time and run-time facilities |
| were moved to separate headers (since they were independent of each other). |
| |
| [endsect] |
| |
| [section:demo Demonstration Program] |
| |
| The program [@../../../../libs/integer/test/common_factor_test.cpp common_factor_test.cpp] is a demonstration of the results from |
| instantiating various examples of the run-time GCD and LCM function |
| templates and the compile-time GCD and LCM class templates. |
| (The run-time GCD and LCM class templates are tested indirectly through |
| the run-time function templates.) |
| |
| [endsect] |
| |
| [section Rationale] |
| |
| The greatest common divisor and least common multiple functions are |
| greatly used in some numeric contexts, including some of the other |
| Boost libraries. Centralizing these functions to one header improves |
| code factoring and eases maintenance. |
| |
| [endsect] |
| |
| [section:gcd_history History] |
| |
| * 24th April 2017 Moved to Jeremy Murphy's improved algorithms, added constexpr and noexcept support, |
| added compiler intrinsic support, added variadic and range based versions of the algorithms. |
| * 13 May 2013 Moved into main Boost.Math Quickbook documentation. |
| * 17 Dec 2005: Converted documentation to Quickbook Format. |
| * 2 Jul 2002: Compile-time and run-time items separated to new headers. |
| * 7 Nov 2001: Initial version |
| |
| [endsect] |
| |
| [section:gcd_credits Credits] |
| |
| The author of the Boost compilation of GCD and LCM computations is |
| Daryle Walker. The code was prompted by existing code hiding in the |
| implementations of Paul Moore's rational library and Steve Cleary's |
| pool library. The code had updates by Helmut Zeisel. |
| |
| [endsect] |
| |
| [endsect] |
| |
| [/ |
| Copyright 2005, 2013 Daryle Walker. |
| Distributed under the Boost Software License, Version 1.0. |
| (See accompanying file LICENSE_1_0.txt or copy at |
| https://www.boost.org/LICENSE_1_0.txt). |
| ] |