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