291 lines
10 KiB
Plaintext
291 lines
10 KiB
Plaintext
|
|
[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
|
|
http://www.boost.org/LICENSE_1_0.txt).
|
|
]
|