| 1 | <!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 3.2//EN"> |
|---|
| 2 | <html> |
|---|
| 3 | <head> |
|---|
| 4 | <title>Boost GCD & LCM Library</title> |
|---|
| 5 | </head> |
|---|
| 6 | |
|---|
| 7 | <body bgcolor="white" text="black" link="blue" alink="red" vlink="purple"> |
|---|
| 8 | <h1> |
|---|
| 9 | <img src="../../../boost.png" alt="boost.png (6897 bytes)" |
|---|
| 10 | align="left" width="277" height="86">Greatest Common Divisor<br> |
|---|
| 11 | Least |
|---|
| 12 | Common Multiple<br> |
|---|
| 13 | </h1> |
|---|
| 14 | |
|---|
| 15 | <p>The class and function templates in <cite><a |
|---|
| 16 | href="../../../boost/math/common_factor.hpp"><boost/math/common_factor.hpp></a> |
|---|
| 17 | </cite> provide run-time and compile-time evaluation of the greatest |
|---|
| 18 | common divisor (GCD) or least common multiple (LCM) of two integers. |
|---|
| 19 | These facilities are useful for many numeric-oriented generic |
|---|
| 20 | programming problems.</p> |
|---|
| 21 | |
|---|
| 22 | <h2><a name="contents">Contents</a></h2> |
|---|
| 23 | |
|---|
| 24 | <ul> |
|---|
| 25 | <li><a href="#contents">Contents</a></li> |
|---|
| 26 | <li>Header <cite><a href="#cf_hpp"><boost/math/common_factor.hpp></a></cite> |
|---|
| 27 | <ul> |
|---|
| 28 | <li><a href="#synopsis">Synopsis</a></li> |
|---|
| 29 | </ul></li> |
|---|
| 30 | <li>Header <cite><a href="#cfrt_hpp"><boost/math/common_factor_rt.hpp></a></cite> |
|---|
| 31 | <ul> |
|---|
| 32 | <li><a href="#gcd_obj">GCD Function Object</a></li> |
|---|
| 33 | <li><a href="#lcm_obj">LCM Function Object</a></li> |
|---|
| 34 | <li><a href="#run_gcd_lcm">Run-time GCD & LCM Determination</a></li> |
|---|
| 35 | </ul></li> |
|---|
| 36 | <li>Header <cite><a href="#cfct_hpp"><boost/math/common_factor_ct.hpp></a></cite></li> |
|---|
| 37 | <li><a href="#example">Example</a></li> |
|---|
| 38 | <li><a href="#demo">Demonstration Program</a></li> |
|---|
| 39 | <li><a href="#rationale">Rationale</a></li> |
|---|
| 40 | <li><a href="#history">History</a></li> |
|---|
| 41 | <li><a href="#credits">Credits</a></li> |
|---|
| 42 | </ul> |
|---|
| 43 | |
|---|
| 44 | <h2>Header <cite><a name="cf_hpp" href="../../../boost/math/common_factor.hpp"><boost/math/common_factor.hpp></a></cite></h2> |
|---|
| 45 | |
|---|
| 46 | <p>This header simply includes the headers <cite><a |
|---|
| 47 | href="../../../boost/math/common_factor_ct.hpp"><boost/math/common_factor_ct.hpp></a></cite> |
|---|
| 48 | and <cite><a |
|---|
| 49 | href="../../../boost/math/common_factor_rt.hpp"><boost/math/common_factor_rt.hpp></a></cite>. |
|---|
| 50 | It used to contain the code, but the compile-time and run-time |
|---|
| 51 | facilities were moved to separate headers (since they were independent), |
|---|
| 52 | and this header maintains compatibility.</p> |
|---|
| 53 | |
|---|
| 54 | <h3><a name="synopsis">Synopsis</a></h3> |
|---|
| 55 | |
|---|
| 56 | <blockquote><pre>namespace boost |
|---|
| 57 | { |
|---|
| 58 | namespace math |
|---|
| 59 | { |
|---|
| 60 | |
|---|
| 61 | template < typename IntegerType > |
|---|
| 62 | class gcd_evaluator; |
|---|
| 63 | template < typename IntegerType > |
|---|
| 64 | class lcm_evaluator; |
|---|
| 65 | |
|---|
| 66 | template < typename IntegerType > |
|---|
| 67 | IntegerType gcd( IntegerType const &a, IntegerType const &b ); |
|---|
| 68 | template < typename IntegerType > |
|---|
| 69 | IntegerType lcm( IntegerType const &a, IntegerType const &b ); |
|---|
| 70 | |
|---|
| 71 | template < unsigned long Value1, unsigned long Value2 > |
|---|
| 72 | struct static_gcd; |
|---|
| 73 | template < unsigned long Value1, unsigned long Value2 > |
|---|
| 74 | struct static_lcm; |
|---|
| 75 | |
|---|
| 76 | } |
|---|
| 77 | } |
|---|
| 78 | </pre></blockquote> |
|---|
| 79 | |
|---|
| 80 | <h2>Header <cite><a name="cfrt_hpp" href="../../../boost/math/common_factor_rt.hpp"><boost/math/common_factor_rt.hpp></a></cite></h2> |
|---|
| 81 | |
|---|
| 82 | <h3><a name="gcd_obj">GCD Function Object</a></h3> |
|---|
| 83 | |
|---|
| 84 | <blockquote><pre>template < typename IntegerType > |
|---|
| 85 | class boost::math::gcd_evaluator |
|---|
| 86 | { |
|---|
| 87 | public: |
|---|
| 88 | // Types |
|---|
| 89 | typedef IntegerType result_type; |
|---|
| 90 | typedef IntegerType first_argument_type; |
|---|
| 91 | typedef IntegerType second_argument_type; |
|---|
| 92 | |
|---|
| 93 | // Function object interface |
|---|
| 94 | result_type operator ()( first_argument_type const &a, |
|---|
| 95 | second_argument_type const &b ) const; |
|---|
| 96 | }; |
|---|
| 97 | </pre></blockquote> |
|---|
| 98 | |
|---|
| 99 | <p>The <code>boost::math::gcd_evaluator</code> class template defines a |
|---|
| 100 | function object class to return the greatest common divisor of two |
|---|
| 101 | integers. The template is parameterized by a single type, called |
|---|
| 102 | <code>IntegerType</code> here. This type should be a numeric type that |
|---|
| 103 | represents integers. The result of the function object is always |
|---|
| 104 | nonnegative, even if either of the operator arguments is negative.</p> |
|---|
| 105 | |
|---|
| 106 | <p>This function object class template is used in the corresponding |
|---|
| 107 | version of the <a href="#run_gcd_lcm">GCD function template</a>. If a |
|---|
| 108 | numeric type wants to customize evaluations of its greatest common |
|---|
| 109 | divisors, then the type should specialize on the |
|---|
| 110 | <code>gcd_evaluator</code> class template.</p> |
|---|
| 111 | |
|---|
| 112 | <h3><a name="lcm_obj">LCM Function Object</a></h3> |
|---|
| 113 | |
|---|
| 114 | <blockquote><pre>template < typename IntegerType > |
|---|
| 115 | class boost::math::lcm_evaluator |
|---|
| 116 | { |
|---|
| 117 | public: |
|---|
| 118 | // Types |
|---|
| 119 | typedef IntegerType result_type; |
|---|
| 120 | typedef IntegerType first_argument_type; |
|---|
| 121 | typedef IntegerType second_argument_type; |
|---|
| 122 | |
|---|
| 123 | // Function object interface |
|---|
| 124 | result_type operator ()( first_argument_type const &a, |
|---|
| 125 | second_argument_type const &b ) const; |
|---|
| 126 | }; |
|---|
| 127 | </pre></blockquote> |
|---|
| 128 | |
|---|
| 129 | <p>The <code>boost::math::lcm_evaluator</code> class template defines a |
|---|
| 130 | function object class to return the least common multiple of two |
|---|
| 131 | integers. The template is parameterized by a single type, called |
|---|
| 132 | <code>IntegerType</code> here. This type should be a numeric type that |
|---|
| 133 | represents integers. The result of the function object is always |
|---|
| 134 | nonnegative, even if either of the operator arguments is negative. If |
|---|
| 135 | the least common multiple is beyond the range of the integer type, the |
|---|
| 136 | results are undefined.</p> |
|---|
| 137 | |
|---|
| 138 | <p>This function object class template is used in the corresponding |
|---|
| 139 | version of the <a href="#run_gcd_lcm">LCM function template</a>. If a |
|---|
| 140 | numeric type wants to customize evaluations of its least common |
|---|
| 141 | multiples, then the type should specialize on the |
|---|
| 142 | <code>lcm_evaluator</code> class template.</p> |
|---|
| 143 | |
|---|
| 144 | <h3><a name="run_gcd_lcm">Run-time GCD & LCM Determination</a></h3> |
|---|
| 145 | |
|---|
| 146 | <blockquote><pre>template < typename IntegerType > |
|---|
| 147 | IntegerType boost::math::gcd( IntegerType const &a, IntegerType const &b ); |
|---|
| 148 | |
|---|
| 149 | template < typename IntegerType > |
|---|
| 150 | IntegerType boost::math::lcm( IntegerType const &a, IntegerType const &b ); |
|---|
| 151 | </pre></blockquote> |
|---|
| 152 | |
|---|
| 153 | <p>The <code>boost::math::gcd</code> function template returns the |
|---|
| 154 | greatest common (nonnegative) divisor of the two integers passed to it. |
|---|
| 155 | The <code>boost::math::lcm</code> function template returns the least |
|---|
| 156 | common (nonnegative) multiple of the two integers passed to it. The |
|---|
| 157 | function templates are parameterized on the function arguments' |
|---|
| 158 | <var>IntegerType</var>, which is also the return type. Internally, |
|---|
| 159 | these function templates use an object of the corresponding version of |
|---|
| 160 | the <code><a href="#gcd_obj">gcd_evaluator</a></code> and <code><a |
|---|
| 161 | href="#lcm_obj">lcm_evaluator</a></code> class templates, |
|---|
| 162 | respectively.</p> |
|---|
| 163 | |
|---|
| 164 | <h2>Header <cite><a name="cfct_hpp" href="../../../boost/math/common_factor_ct.hpp"><boost/math/common_factor_ct.hpp></a></cite></h2> |
|---|
| 165 | |
|---|
| 166 | <blockquote><pre>template < unsigned long Value1, unsigned long Value2 > |
|---|
| 167 | struct boost::math::static_gcd |
|---|
| 168 | { |
|---|
| 169 | static unsigned long const value = <em>implementation_defined</em>; |
|---|
| 170 | }; |
|---|
| 171 | |
|---|
| 172 | template < unsigned long Value1, unsigned long Value2 > |
|---|
| 173 | struct boost::math::static_lcm |
|---|
| 174 | { |
|---|
| 175 | static unsigned long const value = <em>implementation_defined</em>; |
|---|
| 176 | }; |
|---|
| 177 | </pre></blockquote> |
|---|
| 178 | |
|---|
| 179 | <p>The <code>boost::math::static_gcd</code> and |
|---|
| 180 | <code>boost::math::static_lcm</code> class templates take two |
|---|
| 181 | value-based template parameters of the <code>unsigned long</code> type |
|---|
| 182 | and have a single static constant data member, <code>value</code>, of |
|---|
| 183 | that same type. The value of that member is the greatest common factor |
|---|
| 184 | or least common multiple, respectively, of the template arguments. A |
|---|
| 185 | compile-time error will occur if the least common multiple is beyond the |
|---|
| 186 | range of an <code>unsigned long</code>.</p> |
|---|
| 187 | |
|---|
| 188 | <h2><a name="example">Example</a></h2> |
|---|
| 189 | |
|---|
| 190 | <blockquote><pre>#include <boost/math/common_factor.hpp> |
|---|
| 191 | #include <algorithm> |
|---|
| 192 | #include <iterator> |
|---|
| 193 | |
|---|
| 194 | |
|---|
| 195 | int main() |
|---|
| 196 | { |
|---|
| 197 | using std::cout; |
|---|
| 198 | using std::endl; |
|---|
| 199 | |
|---|
| 200 | cout << "The GCD and LCM of 6 and 15 are " |
|---|
| 201 | << boost::math::gcd(6, 15) << " and " |
|---|
| 202 | << boost::math::lcm(6, 15) << ", respectively." |
|---|
| 203 | << endl; |
|---|
| 204 | |
|---|
| 205 | cout << "The GCD and LCM of 8 and 9 are " |
|---|
| 206 | << boost::math::static_gcd<8, 9>::value |
|---|
| 207 | << " and " |
|---|
| 208 | << boost::math::static_lcm<8, 9>::value |
|---|
| 209 | << ", respectively." << endl; |
|---|
| 210 | |
|---|
| 211 | int a[] = { 4, 5, 6 }, b[] = { 7, 8, 9 }, c[3]; |
|---|
| 212 | std::transform( a, a + 3, b, c, boost::math::gcd_evaluator<int>() ); |
|---|
| 213 | std::copy( c, c + 3, std::ostream_iterator<int>(cout, " ") ); |
|---|
| 214 | } |
|---|
| 215 | </pre></blockquote> |
|---|
| 216 | |
|---|
| 217 | <h2><a name="demo">Demonstration Program</a></h2> |
|---|
| 218 | |
|---|
| 219 | <p>The program <a |
|---|
| 220 | href="../test/common_factor_test.cpp">common_factor_test.cpp</a> is a |
|---|
| 221 | demonstration of the results from instantiating various examples of the |
|---|
| 222 | run-time GCD and LCM function templates and the compile-time GCD and |
|---|
| 223 | LCM class templates. (The run-time GCD and LCM class templates are |
|---|
| 224 | tested indirectly through the run-time function templates.)</p> |
|---|
| 225 | |
|---|
| 226 | <h2><a name="rationale">Rationale</a></h2> |
|---|
| 227 | |
|---|
| 228 | <p>The greatest common divisor and least common multiple functions are |
|---|
| 229 | greatly used in some numeric contexts, including some of the other Boost |
|---|
| 230 | libraries. Centralizing these functions to one header improves code |
|---|
| 231 | factoring and eases maintainence.</p> |
|---|
| 232 | |
|---|
| 233 | <h2><a name="history">History</a></h2> |
|---|
| 234 | |
|---|
| 235 | <dl> |
|---|
| 236 | <dt>2 Jul 2002 |
|---|
| 237 | <dd>Compile-time and run-time items separated to new headers. |
|---|
| 238 | |
|---|
| 239 | <dt>7 Nov 2001 |
|---|
| 240 | <dd>Initial version |
|---|
| 241 | </dl> |
|---|
| 242 | |
|---|
| 243 | <h2><a name="credits">Credits</a></h2> |
|---|
| 244 | |
|---|
| 245 | <p>The author of the Boost compilation of GCD and LCM computations is <a |
|---|
| 246 | href="../../../people/daryle_walker.html">Daryle Walker</a>. The code was |
|---|
| 247 | prompted by existing code hiding in the implementations of <a |
|---|
| 248 | href="../../../people/paul_moore.htm">Paul Moore</a>'s <a |
|---|
| 249 | href="../../rational/index.html">rational</a> library and Steve Cleary's <a |
|---|
| 250 | href="../../pool/doc/index.html">pool</a> library. The code had updates by |
|---|
| 251 | Helmut Zeisel.</p> |
|---|
| 252 | |
|---|
| 253 | <hr> |
|---|
| 254 | |
|---|
| 255 | <p>Revised July 2, 2002</p> |
|---|
| 256 | |
|---|
| 257 | <p>© Copyright Daryle Walker 2001-2002. Permission to copy, use, |
|---|
| 258 | modify, sell and distribute this document is granted provided this |
|---|
| 259 | copyright notice appears in all copies. This document is provided |
|---|
| 260 | "as is" without express or implied warranty, and with no claim |
|---|
| 261 | as to its suitability for any purpose.</p> |
|---|
| 262 | </body> |
|---|
| 263 | </html> |
|---|
