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