123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290 |
- [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).
- ]
|