1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
|
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 3.2//EN">
<html>
<head>
<title>Boost GCD & LCM Library</title>
</head>
<body bgcolor="white" text="black" link="blue" alink="red" vlink="purple">
<h1>
<img src="../../../c++boost.gif" alt="c++boost.gif (8819 bytes)"
align="left" width="277" height="86">Greatest Common Divisor<br>
Least
Common Multiple<br>
</h1>
<p>The class and function templates in <cite><a
href="../../../boost/math/common_factor.hpp"><boost/math/common_factor.hpp></a>
</cite> 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.</p>
<h2><a name="contents">Contents</a></h2>
<ul>
<li><a href="#contents">Contents</a></li>
<li><a href="#synopsis">Synopsis</a></li>
<li><a href="#gcd_obj">GCD Function Object</a></li>
<li><a href="#lcm_obj">LCM Function Object</a></li>
<li><a href="#run_gcd_lcm">Run-time GCD & LCM
Determination</a></li>
<li><a href="#ct_gcd_lcm">Compile-time GCD & LCM
Determination</a></li>
<li><a href="#example">Example</a></li>
<li><a href="#demo">Demonstration Program</a></li>
<li><a href="#rationale">Rationale</a></li>
<li><a href="#credits">Credits</a></li>
</ul>
<h2><a name="synopsis">Synopsis</a></h2>
<blockquote><pre>namespace boost
{
namespace math
{
template < typename IntegerType >
class gcd_evaluator;
template < typename IntegerType >
class lcm_evaluator;
template < typename IntegerType >
IntegerType gcd( IntegerType const &a, IntegerType const &b );
template < typename IntegerType >
IntegerType lcm( IntegerType const &a, IntegerType const &b );
template < unsigned long Value1, unsigned long Value2 >
struct static_gcd;
template < unsigned long Value1, unsigned long Value2 >
struct static_lcm;
}
}
</pre></blockquote>
<h2><a name="gcd_obj">GCD Function Object</a></h2>
<blockquote><pre>template < typename IntegerType >
class boost::math::gcd_evaluator
{
public:
// Types
typedef IntegerType result_type;
typedef IntegerType first_argument_type;
typedef IntegerType second_argument_type;
// Function object interface
result_type operator ()( first_argument_type const &a,
second_argument_type const &b ) const;
};
</pre></blockquote>
<p>The <code>boost::math::gcd_evaluator</code> 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
<code>IntegerType</code> 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.</p>
<p>This function object class template is used in the corresponding
version of the <a href="#run_gcd_lcm">GCD function template</a>. If
a numeric type wants to customize evaluations of its greatest common
divisors, then the type should specialize on the <code>gcd_evaluator</code>
class template.</p>
<h2><a name="lcm_obj">LCM Function Object</a></h2>
<blockquote><pre>template < typename IntegerType >
class boost::math::lcm_evaluator
{
public:
// Types
typedef IntegerType result_type;
typedef IntegerType first_argument_type;
typedef IntegerType second_argument_type;
// Function object interface
result_type operator ()( first_argument_type const &a,
second_argument_type const &b ) const;
};
</pre></blockquote>
<p>The <code>boost::math::lcm_evaluator</code> 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
<code>IntegerType</code> 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.</p>
<p>This function object class template is used in the corresponding
version of the <a href="#run_gcd_lcm">LCM function template</a>. If a
numeric type wants to customize evaluations of its least common
multiples, then the type should specialize on the <code>lcm_evaluator</code>
class template.</p>
<h2><a name="run_gcd_lcm">Run-time GCD & LCM Determination</a></h2>
<blockquote><pre>template < typename IntegerType >
IntegerType boost::math::gcd( IntegerType const &a, IntegerType const &b );
template < typename IntegerType >
IntegerType boost::math::lcm( IntegerType const &a, IntegerType const &b );
</pre></blockquote>
<p>The <code>boost::math::gcd</code> function template returns the greatest
common (nonnegative) divisor of the two integers passed to it. The
<code>boost::math::lcm</code> function template returns the least common
(nonnegative) multiple of the two integers passed to it. The function
templates are parameterized on the function arguments' <var>IntegerType</var>,
which is also the return type. Internally, these function templates use
an object of the corresponding version of the <code><a
href="#gcd_obj">gcd_evaluator</a></code> and <code><a
href="#lcm_obj">lcm_evaluator</a></code> class templates, respectively.</p>
<h2><a name="ct_gcd_lcm">Compile-time GCD & LCM Determination</a></h2>
<blockquote><pre>template < unsigned long Value1, unsigned long Value2 >
struct boost::math::static_gcd
{
static unsigned long const value = <em>implementation_defined</em>;
};
template < unsigned long Value1, unsigned long Value2 >
struct boost::math::static_lcm
{
static unsigned long const value = <em>implementation_defined</em>;
};
</pre></blockquote>
<p>The <code>boost::math::static_gcd</code> and <code>boost::math::static_lcm</code>
class templates take two value-based template parameters of the
<code>unsigned long</code> type and have a single static constant data
member, <code>value</code>, of that same type. The value of that member
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 an <code>unsigned long</code>.</p>
<h2><a name="example">Example</a></h2>
<blockquote><pre>#include <boost/math/common_factor.hpp>
#include <algorithm>
#include <iterator>
int main()
{
using std::cout;
using std::endl;
cout << "The GCD and LCM of 6 and 15 are "
<< boost::math::gcd(6, 15) << " and "
<< boost::math::lcm(6, 15) << ", respectively."
<< endl;
cout << "The GCD and LCM of 8 and 9 are "
<< boost::math::static_gcd<8, 9>::value
<< " and "
<< boost::math::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::math::gcd_evaluator<int>() );
std::copy( c, c + 3, std::ostream_iterator<int>(cout, " ") );
}
</pre></blockquote>
<h2><a name="demo">Demonstration Program</a></h2>
<p>The program <a
href="../test/common_factor_test.cpp">common_factor_test.cpp</a> 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.)</p>
<h2><a name="rationale">Rationale</a></h2>
<p>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 maintainence.</p>
<h2><a name="credits">Credits</a></h2>
<p>The author of the Boost compilation of GCD and LCM computations is <a
href="../../../people/daryle_walker.html">Daryle Walker</a>. The code was
prompted by existing code hiding in the implementations of <a
href="../../../people/paul_moore.htm">Paul Moore</a>'s <a
href="../../rational/index.html">rational</a> library and Steve Cleary's <a
href="../../pool/doc/index.html">pool</a> library. The code had updates by
Helmut Zeisel.</p>
<hr>
<p>Revised November 7, 2001</p>
<p>© Copyright Daryle Walker 2001. Permission to copy, use,
modify, sell and distribute this document is granted provided this
copyright notice appears in all copies. This document is provided
"as is" without express or implied warranty, and with no claim
as to its suitability for any purpose.</p>
</body>
</html>
|
