ceph/src/boost/libs/math/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 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