ceph/src/boost/libs/integer/doc/gcd/math-gcd.qbk

   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