1 2[section:gcd_lcm Greatest Common Divisor and Least Common Multiple] 3 4[section Introduction] 5 6The class and function templates in <boost/math/common_factor.hpp> 7provide run-time and compile-time evaluation of the greatest common divisor 8(GCD) or least common multiple (LCM) of two integers. 9These facilities are useful for many numeric-oriented generic 10programming problems. 11 12[endsect] 13 14[section Synopsis] 15 16 namespace boost 17 { 18 namespace integer 19 { 20 21 template < typename IntegerType > 22 class gcd_evaluator; 23 template < typename IntegerType > 24 class lcm_evaluator; 25 26 template < typename IntegerType > 27 constexpr IntegerType gcd( IntegerType const &a, IntegerType const &b ); 28 template < typename IntegerType > 29 constexpr IntegerType lcm( IntegerType const &a, IntegerType const &b ); 30 template < typename IntegerType, typename... Args > 31 constexpr IntegerType gcd( IntegerType const &a, IntegerType const &b, Args const&... ); 32 template < typename IntegerType, typename... Args > 33 constexpr IntegerType lcm( IntegerType const &a, IntegerType const &b, Args const&... ); 34 35 template <typename I> 36 std::pair<typename std::iterator_traits<I>::value_type, I> 37 gcd_range(I first, I last); 38 template <typename I> 39 std::pair<typename std::iterator_traits<I>::value_type, I> 40 lcm_range(I first, I last); 41 42 typedef ``['see-below]`` static_gcd_type; 43 44 template < static_gcd_type Value1, static_gcd_type Value2 > 45 struct static_gcd; 46 template < static_gcd_type Value1, static_gcd_type Value2 > 47 struct static_lcm; 48 49 } 50 } 51 52[endsect] 53 54[section GCD Function Object] 55 56[*Header: ] [@../../../../boost/integer/common_factor_rt.hpp <boost/integer/common_factor_rt.hpp>] 57 58 template < typename IntegerType > 59 class boost::integer::gcd_evaluator 60 { 61 public: 62 // Types 63 typedef IntegerType result_type; 64 typedef IntegerType first_argument_type; 65 typedef IntegerType second_argument_type; 66 67 // Function object interface 68 constexpr result_type operator ()( 69 first_argument_type const &a, 70 second_argument_type const &b ) const; 71 }; 72 73The boost::integer::gcd_evaluator class template defines a function object 74class to return the greatest common divisor of two integers. 75The template is parameterized by a single type, called IntegerType here. 76This type should be a numeric type that represents integers. 77The result of the function object is always nonnegative, even if either of 78the operator arguments is negative. 79 80This function object class template is used in the corresponding version of 81the GCD function template. If a numeric type wants to customize evaluations 82of its greatest common divisors, then the type should specialize on the 83gcd_evaluator class template. 84 85Note that these function objects are `constexpr` in C++14 and later only. 86They are also declared `noexcept` when appropriate. 87 88[endsect] 89 90[section LCM Function Object] 91 92[*Header: ] [@../../../../boost/integer/common_factor_rt.hpp <boost/integer/common_factor_rt.hpp>] 93 94 template < typename IntegerType > 95 class boost::integer::lcm_evaluator 96 { 97 public: 98 // Types 99 typedef IntegerType result_type; 100 typedef IntegerType first_argument_type; 101 typedef IntegerType second_argument_type; 102 103 // Function object interface 104 constexpr result_type operator ()( 105 first_argument_type const &a, 106 second_argument_type const &b ) const; 107 }; 108 109The boost::integer::lcm_evaluator class template defines a function object 110class to return the least common multiple of two integers. The template 111is parameterized by a single type, called IntegerType here. This type 112should be a numeric type that represents integers. The result of the 113function object is always nonnegative, even if either of the operator 114arguments is negative. If the least common multiple is beyond the range 115of the integer type, the results are undefined. 116 117This function object class template is used in the corresponding version 118of the LCM function template. If a numeric type wants to customize 119evaluations of its least common multiples, then the type should 120specialize on the lcm_evaluator class template. 121 122Note that these function objects are constexpr in C++14 and later only. 123They are also declared `noexcept` when appropriate. 124 125[endsect] 126 127[section:run_time Run-time GCD & LCM Determination] 128 129[*Header: ] [@../../../../boost/integer/common_factor_rt.hpp <boost/integer/common_factor_rt.hpp>] 130 131 template < typename IntegerType > 132 constexpr IntegerType boost::integer::gcd( IntegerType const &a, IntegerType const &b ); 133 134 template < typename IntegerType > 135 constexpr IntegerType boost::integer::lcm( IntegerType const &a, IntegerType const &b ); 136 137 template < typename IntegerType, typename... Args > 138 constexpr IntegerType gcd( IntegerType const &a, IntegerType const &b, Args const&... ); 139 140 template < typename IntegerType, typename... Args > 141 constexpr IntegerType lcm( IntegerType const &a, IntegerType const &b, Args const&... ); 142 143 template <typename I> 144 std::pair<typename std::iterator_traits<I>::value_type, I> 145 gcd_range(I first, I last); 146 147 template <typename I> 148 std::pair<typename std::iterator_traits<I>::value_type, I> 149 lcm_range(I first, I last); 150 151The boost::integer::gcd function template returns the greatest common 152(nonnegative) divisor of the two integers passed to it. 153`boost::integer::gcd_range` is the iteration of the above gcd algorithm over a 154range, returning the greatest common divisor of all the elements. The algorithm 155terminates when the gcd reaches unity or the end of the range. Thus it also 156returns the iterator after the last element inspected because this may not be 157equal to the end of the range. The variadic version of `gcd` behaves similarly 158but does not indicate which input value caused the gcd to reach unity. 159 160The boost::integer::lcm function template returns the least common 161(nonnegative) multiple of the two integers passed to it. 162As with gcd, there are range and variadic versions of the function for 163more than 2 arguments. 164 165Note that these functions are constexpr in C++14 and later only. 166They are also declared `noexcept` when appropriate. 167 168[endsect] 169 170[section:compile_time Compile time GCD and LCM determination] 171 172[note These functions are deprecated in favor of constexpr `gcd` and `lcm` on C++14 capable compilers.] 173 174[*Header: ] [@../../../../boost/integer/common_factor_ct.hpp <boost/integer/common_factor_ct.hpp>] 175 176 typedef ``['unspecified]`` static_gcd_type; 177 178 template < static_gcd_type Value1, static_gcd_type Value2 > 179 struct boost::integer::static_gcd : public mpl::integral_c<static_gcd_type, implementation_defined> 180 { 181 }; 182 183 template < static_gcd_type Value1, static_gcd_type Value2 > 184 struct boost::integer::static_lcm : public mpl::integral_c<static_gcd_type, implementation_defined> 185 { 186 }; 187 188The type `static_gcd_type` is the widest unsigned-integer-type that is supported 189for use in integral-constant-expressions by the compiler. Usually this 190the same type as `boost::uintmax_t`, but may fall back to being `unsigned long` 191for some older compilers. 192 193The boost::integer::static_gcd and boost::integer::static_lcm class templates 194take two value-based template parameters of the ['static_gcd_type] type 195and inherit from the type `boost::mpl::integral_c`. 196Inherited from the base class, they have a member /value/ 197that is the greatest common factor or least 198common multiple, respectively, of the template arguments. 199A compile-time error will occur if the least common multiple 200is beyond the range of `static_gcd_type`. 201 202[h3 Example] 203 204 #include <boost/integer/common_factor.hpp> 205 #include <algorithm> 206 #include <iterator> 207 #include <iostream> 208 209 int main() 210 { 211 using std::cout; 212 using std::endl; 213 214 cout << "The GCD and LCM of 6 and 15 are " 215 << boost::integer::gcd(6, 15) << " and " 216 << boost::integer::lcm(6, 15) << ", respectively." 217 << endl; 218 219 cout << "The GCD and LCM of 8 and 9 are " 220 << boost::integer::static_gcd<8, 9>::value 221 << " and " 222 << boost::integer::static_lcm<8, 9>::value 223 << ", respectively." << endl; 224 225 int a[] = { 4, 5, 6 }, b[] = { 7, 8, 9 }, c[3]; 226 std::transform( a, a + 3, b, c, boost::integer::gcd_evaluator<int>() ); 227 std::copy( c, c + 3, std::ostream_iterator<int>(cout, " ") ); 228 } 229 230[endsect] 231 232[section:gcd_header Header <boost/integer/common_factor.hpp>] 233 234This header simply includes the headers 235[@../../../../boost/integer/common_factor_ct.hpp <boost/integer/common_factor_ct.hpp>] 236and [@../../../../boost/integer/common_factor_rt.hpp <boost/integer/common_factor_rt.hpp>]. 237 238Note this is a legacy header: it used to contain the actual implementation, 239but the compile-time and run-time facilities 240were moved to separate headers (since they were independent of each other). 241 242[endsect] 243 244[section:demo Demonstration Program] 245 246The program [@../../../../libs/integer/test/common_factor_test.cpp common_factor_test.cpp] is a demonstration of the results from 247instantiating various examples of the run-time GCD and LCM function 248templates and the compile-time GCD and LCM class templates. 249(The run-time GCD and LCM class templates are tested indirectly through 250the run-time function templates.) 251 252[endsect] 253 254[section Rationale] 255 256The greatest common divisor and least common multiple functions are 257greatly used in some numeric contexts, including some of the other 258Boost libraries. Centralizing these functions to one header improves 259code factoring and eases maintenance. 260 261[endsect] 262 263[section:gcd_history History] 264 265* 24th April 2017 Moved to Jeremy Murphy's improved algorithms, added constexpr and noexcept support, 266added compiler intrinsic support, added variadic and range based versions of the algorithms. 267* 13 May 2013 Moved into main Boost.Math Quickbook documentation. 268* 17 Dec 2005: Converted documentation to Quickbook Format. 269* 2 Jul 2002: Compile-time and run-time items separated to new headers. 270* 7 Nov 2001: Initial version 271 272[endsect] 273 274[section:gcd_credits Credits] 275 276The author of the Boost compilation of GCD and LCM computations is 277Daryle Walker. The code was prompted by existing code hiding in the 278implementations of Paul Moore's rational library and Steve Cleary's 279pool library. The code had updates by Helmut Zeisel. 280 281[endsect] 282 283[endsect] 284 285[/ 286Copyright 2005, 2013 Daryle Walker. 287Distributed under the Boost Software License, Version 1.0. 288(See accompanying file LICENSE_1_0.txt or copy at 289http://www.boost.org/LICENSE_1_0.txt). 290] 291