source: NonGTP/Boost/boost/math/common_factor_rt.hpp @ 857

Revision 857, 10.0 KB checked in by igarcia, 19 years ago (diff)
Line 
1//  Boost common_factor_rt.hpp header file  ----------------------------------//
2
3//  (C) Copyright Daryle Walker and Paul Moore 2001-2002.  Permission to copy,
4//  use, modify, sell and distribute this software is granted provided this
5//  copyright notice appears in all copies.  This software is provided "as is"
6//  without express or implied warranty, and with no claim as to its suitability
7//  for any purpose.
8
9//  See http://www.boost.org for updates, documentation, and revision history.
10
11#ifndef BOOST_MATH_COMMON_FACTOR_RT_HPP
12#define BOOST_MATH_COMMON_FACTOR_RT_HPP
13
14#include <boost/math_fwd.hpp>  // self include
15
16#include <boost/config.hpp>  // for BOOST_NESTED_TEMPLATE, etc.
17#include <boost/limits.hpp>  // for std::numeric_limits
18
19
20namespace boost
21{
22namespace math
23{
24
25
26//  Forward declarations for function templates  -----------------------------//
27
28template < typename IntegerType >
29    IntegerType  gcd( IntegerType const &a, IntegerType const &b );
30
31template < typename IntegerType >
32    IntegerType  lcm( IntegerType const &a, IntegerType const &b );
33
34
35//  Greatest common divisor evaluator class declaration  ---------------------//
36
37template < typename IntegerType >
38class gcd_evaluator
39{
40public:
41    // Types
42    typedef IntegerType  result_type, first_argument_type, second_argument_type;
43
44    // Function object interface
45    result_type  operator ()( first_argument_type const &a,
46     second_argument_type const &b ) const;
47
48};  // boost::math::gcd_evaluator
49
50
51//  Least common multiple evaluator class declaration  -----------------------//
52
53template < typename IntegerType >
54class lcm_evaluator
55{
56public:
57    // Types
58    typedef IntegerType  result_type, first_argument_type, second_argument_type;
59
60    // Function object interface
61    result_type  operator ()( first_argument_type const &a,
62     second_argument_type const &b ) const;
63
64};  // boost::math::lcm_evaluator
65
66
67//  Implementation details  --------------------------------------------------//
68
69namespace detail
70{
71    // Greatest common divisor for rings (including unsigned integers)
72    template < typename RingType >
73    RingType
74    gcd_euclidean
75    (
76        RingType  a,
77        RingType  b
78    )
79    {
80        // Avoid repeated construction
81        #ifndef __BORLANDC__
82        RingType const  zero = static_cast<RingType>( 0 );
83        #else
84        RingType  zero = static_cast<RingType>( 0 );
85        #endif
86
87        // Reduce by GCD-remainder property [GCD(a,b) == GCD(b,a MOD b)]
88        while ( true )
89        {
90            if ( a == zero )
91                return b;
92            b %= a;
93
94            if ( b == zero )
95                return a;
96            a %= b;
97        }
98    }
99
100    // Greatest common divisor for (signed) integers
101    template < typename IntegerType >
102    inline
103    IntegerType
104    gcd_integer
105    (
106        IntegerType const &  a,
107        IntegerType const &  b
108    )
109    {
110        // Avoid repeated construction
111        IntegerType const  zero = static_cast<IntegerType>( 0 );
112        IntegerType const  result = gcd_euclidean( a, b );
113
114        return ( result < zero ) ? -result : result;
115    }
116
117    // Least common multiple for rings (including unsigned integers)
118    template < typename RingType >
119    inline
120    RingType
121    lcm_euclidean
122    (
123        RingType const &  a,
124        RingType const &  b
125    )
126    {
127        RingType const  zero = static_cast<RingType>( 0 );
128        RingType const  temp = gcd_euclidean( a, b );
129
130        return ( temp != zero ) ? ( a / temp * b ) : zero;
131    }
132
133    // Least common multiple for (signed) integers
134    template < typename IntegerType >
135    inline
136    IntegerType
137    lcm_integer
138    (
139        IntegerType const &  a,
140        IntegerType const &  b
141    )
142    {
143        // Avoid repeated construction
144        IntegerType const  zero = static_cast<IntegerType>( 0 );
145        IntegerType const  result = lcm_euclidean( a, b );
146
147        return ( result < zero ) ? -result : result;
148    }
149
150    // Function objects to find the best way of computing GCD or LCM
151#ifndef BOOST_NO_LIMITS_COMPILE_TIME_CONSTANTS
152#ifndef BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION
153    template < typename T, bool IsSpecialized, bool IsSigned >
154    struct gcd_optimal_evaluator_helper_t
155    {
156        T  operator ()( T const &a, T const &b )
157        {
158            return gcd_euclidean( a, b );
159        }
160    };
161
162    template < typename T >
163    struct gcd_optimal_evaluator_helper_t< T, true, true >
164    {
165        T  operator ()( T const &a, T const &b )
166        {
167            return gcd_integer( a, b );
168        }
169    };
170#else
171    template < bool IsSpecialized, bool IsSigned >
172    struct gcd_optimal_evaluator_helper2_t
173    {
174        template < typename T >
175        struct helper
176        {
177            T  operator ()( T const &a, T const &b )
178            {
179                return gcd_euclidean( a, b );
180            }
181        };
182    };
183
184    template < >
185    struct gcd_optimal_evaluator_helper2_t< true, true >
186    {
187        template < typename T >
188        struct helper
189        {
190            T  operator ()( T const &a, T const &b )
191            {
192                return gcd_integer( a, b );
193            }
194        };
195    };
196
197    template < typename T, bool IsSpecialized, bool IsSigned >
198    struct gcd_optimal_evaluator_helper_t
199        : gcd_optimal_evaluator_helper2_t<IsSpecialized, IsSigned>
200           ::BOOST_NESTED_TEMPLATE helper<T>
201    {
202    };
203#endif
204
205    template < typename T >
206    struct gcd_optimal_evaluator
207    {
208        T  operator ()( T const &a, T const &b )
209        {
210            typedef ::std::numeric_limits<T>  limits_type;
211
212            typedef gcd_optimal_evaluator_helper_t<T,
213             limits_type::is_specialized, limits_type::is_signed>  helper_type;
214
215            helper_type  solver;
216
217            return solver( a, b );
218        }
219    };
220#else // BOOST_NO_LIMITS_COMPILE_TIME_CONSTANTS
221    template < typename T >
222    struct gcd_optimal_evaluator
223    {
224        T  operator ()( T const &a, T const &b )
225        {
226            return gcd_integer( a, b );
227        }
228    };
229#endif
230
231#ifndef BOOST_NO_LIMITS_COMPILE_TIME_CONSTANTS
232#ifndef BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION
233    template < typename T, bool IsSpecialized, bool IsSigned >
234    struct lcm_optimal_evaluator_helper_t
235    {
236        T  operator ()( T const &a, T const &b )
237        {
238            return lcm_euclidean( a, b );
239        }
240    };
241
242    template < typename T >
243    struct lcm_optimal_evaluator_helper_t< T, true, true >
244    {
245        T  operator ()( T const &a, T const &b )
246        {
247            return lcm_integer( a, b );
248        }
249    };
250#else
251    template < bool IsSpecialized, bool IsSigned >
252    struct lcm_optimal_evaluator_helper2_t
253    {
254        template < typename T >
255        struct helper
256        {
257            T  operator ()( T const &a, T const &b )
258            {
259                return lcm_euclidean( a, b );
260            }
261        };
262    };
263
264    template < >
265    struct lcm_optimal_evaluator_helper2_t< true, true >
266    {
267        template < typename T >
268        struct helper
269        {
270            T  operator ()( T const &a, T const &b )
271            {
272                return lcm_integer( a, b );
273            }
274        };
275    };
276
277    template < typename T, bool IsSpecialized, bool IsSigned >
278    struct lcm_optimal_evaluator_helper_t
279        : lcm_optimal_evaluator_helper2_t<IsSpecialized, IsSigned>
280           ::BOOST_NESTED_TEMPLATE helper<T>
281    {
282    };
283#endif
284
285    template < typename T >
286    struct lcm_optimal_evaluator
287    {
288        T  operator ()( T const &a, T const &b )
289        {
290            typedef ::std::numeric_limits<T>  limits_type;
291
292            typedef lcm_optimal_evaluator_helper_t<T,
293             limits_type::is_specialized, limits_type::is_signed>  helper_type;
294
295            helper_type  solver;
296
297            return solver( a, b );
298        }
299    };
300#else // BOOST_NO_LIMITS_COMPILE_TIME_CONSTANTS
301    template < typename T >
302    struct lcm_optimal_evaluator
303    {
304        T  operator ()( T const &a, T const &b )
305        {
306            return lcm_integer( a, b );
307        }
308    };
309#endif
310
311    // Functions to find the GCD or LCM in the best way
312    template < typename T >
313    inline
314    T
315    gcd_optimal
316    (
317        T const &  a,
318        T const &  b
319    )
320    {
321        gcd_optimal_evaluator<T>  solver;
322
323        return solver( a, b );
324    }
325
326    template < typename T >
327    inline
328    T
329    lcm_optimal
330    (
331        T const &  a,
332        T const &  b
333    )
334    {
335        lcm_optimal_evaluator<T>  solver;
336
337        return solver( a, b );
338    }
339
340}  // namespace detail
341
342
343//  Greatest common divisor evaluator member function definition  ------------//
344
345template < typename IntegerType >
346inline
347typename gcd_evaluator<IntegerType>::result_type
348gcd_evaluator<IntegerType>::operator ()
349(
350    first_argument_type const &   a,
351    second_argument_type const &  b
352) const
353{
354    return detail::gcd_optimal( a, b );
355}
356
357
358//  Least common multiple evaluator member function definition  --------------//
359
360template < typename IntegerType >
361inline
362typename lcm_evaluator<IntegerType>::result_type
363lcm_evaluator<IntegerType>::operator ()
364(
365    first_argument_type const &   a,
366    second_argument_type const &  b
367) const
368{
369    return detail::lcm_optimal( a, b );
370}
371
372
373//  Greatest common divisor and least common multiple function definitions  --//
374
375template < typename IntegerType >
376inline
377IntegerType
378gcd
379(
380    IntegerType const &  a,
381    IntegerType const &  b
382)
383{
384    gcd_evaluator<IntegerType>  solver;
385
386    return solver( a, b );
387}
388
389template < typename IntegerType >
390inline
391IntegerType
392lcm
393(
394    IntegerType const &  a,
395    IntegerType const &  b
396)
397{
398    lcm_evaluator<IntegerType>  solver;
399
400    return solver( a, b );
401}
402
403
404}  // namespace math
405}  // namespace boost
406
407
408#endif  // BOOST_MATH_COMMON_FACTOR_RT_HPP
Note: See TracBrowser for help on using the repository browser.