williamr@2: //  Boost common_factor_rt.hpp header file  ----------------------------------//
williamr@2: 
williamr@2: //  (C) Copyright Daryle Walker and Paul Moore 2001-2002.  Permission to copy,
williamr@2: //  use, modify, sell and distribute this software is granted provided this
williamr@2: //  copyright notice appears in all copies.  This software is provided "as is"
williamr@2: //  without express or implied warranty, and with no claim as to its suitability
williamr@2: //  for any purpose. 
williamr@2: 
williamr@2: //  See http://www.boost.org for updates, documentation, and revision history. 
williamr@2: 
williamr@2: #ifndef BOOST_MATH_COMMON_FACTOR_RT_HPP
williamr@2: #define BOOST_MATH_COMMON_FACTOR_RT_HPP
williamr@2: 
williamr@2: #include <boost/math_fwd.hpp>  // self include
williamr@2: 
williamr@2: #include <boost/config.hpp>  // for BOOST_NESTED_TEMPLATE, etc.
williamr@2: #include <boost/limits.hpp>  // for std::numeric_limits
williamr@2: 
williamr@2: 
williamr@2: namespace boost
williamr@2: {
williamr@2: namespace math
williamr@2: {
williamr@2: 
williamr@2: 
williamr@2: //  Forward declarations for function templates  -----------------------------//
williamr@2: 
williamr@2: template < typename IntegerType >
williamr@2:     IntegerType  gcd( IntegerType const &a, IntegerType const &b );
williamr@2: 
williamr@2: template < typename IntegerType >
williamr@2:     IntegerType  lcm( IntegerType const &a, IntegerType const &b );
williamr@2: 
williamr@2: 
williamr@2: //  Greatest common divisor evaluator class declaration  ---------------------//
williamr@2: 
williamr@2: template < typename IntegerType >
williamr@2: class gcd_evaluator
williamr@2: {
williamr@2: public:
williamr@2:     // Types
williamr@2:     typedef IntegerType  result_type, first_argument_type, second_argument_type;
williamr@2: 
williamr@2:     // Function object interface
williamr@2:     result_type  operator ()( first_argument_type const &a,
williamr@2:      second_argument_type const &b ) const;
williamr@2: 
williamr@2: };  // boost::math::gcd_evaluator
williamr@2: 
williamr@2: 
williamr@2: //  Least common multiple evaluator class declaration  -----------------------//
williamr@2: 
williamr@2: template < typename IntegerType >
williamr@2: class lcm_evaluator
williamr@2: {
williamr@2: public:
williamr@2:     // Types
williamr@2:     typedef IntegerType  result_type, first_argument_type, second_argument_type;
williamr@2: 
williamr@2:     // Function object interface
williamr@2:     result_type  operator ()( first_argument_type const &a,
williamr@2:      second_argument_type const &b ) const;
williamr@2: 
williamr@2: };  // boost::math::lcm_evaluator
williamr@2: 
williamr@2: 
williamr@2: //  Implementation details  --------------------------------------------------//
williamr@2: 
williamr@2: namespace detail
williamr@2: {
williamr@2:     // Greatest common divisor for rings (including unsigned integers)
williamr@2:     template < typename RingType >
williamr@2:     RingType
williamr@2:     gcd_euclidean
williamr@2:     (
williamr@2:         RingType  a,
williamr@2:         RingType  b
williamr@2:     )
williamr@2:     {
williamr@2:         // Avoid repeated construction
williamr@2:         #ifndef __BORLANDC__
williamr@2:         RingType const  zero = static_cast<RingType>( 0 );
williamr@2:         #else
williamr@2:         RingType  zero = static_cast<RingType>( 0 );
williamr@2:         #endif
williamr@2: 
williamr@2:         // Reduce by GCD-remainder property [GCD(a,b) == GCD(b,a MOD b)]
williamr@2:         while ( true )
williamr@2:         {
williamr@2:             if ( a == zero )
williamr@2:                 return b;
williamr@2:             b %= a;
williamr@2: 
williamr@2:             if ( b == zero )
williamr@2:                 return a;
williamr@2:             a %= b;
williamr@2:         }
williamr@2:     }
williamr@2: 
williamr@2:     // Greatest common divisor for (signed) integers
williamr@2:     template < typename IntegerType >
williamr@2:     inline
williamr@2:     IntegerType
williamr@2:     gcd_integer
williamr@2:     (
williamr@2:         IntegerType const &  a,
williamr@2:         IntegerType const &  b
williamr@2:     )
williamr@2:     {
williamr@2:         // Avoid repeated construction
williamr@2:         IntegerType const  zero = static_cast<IntegerType>( 0 );
williamr@2:         IntegerType const  result = gcd_euclidean( a, b );
williamr@2: 
williamr@2:         return ( result < zero ) ? -result : result;
williamr@2:     }
williamr@2: 
williamr@2:     // Least common multiple for rings (including unsigned integers)
williamr@2:     template < typename RingType >
williamr@2:     inline
williamr@2:     RingType
williamr@2:     lcm_euclidean
williamr@2:     (
williamr@2:         RingType const &  a,
williamr@2:         RingType const &  b
williamr@2:     )
williamr@2:     {
williamr@2:         RingType const  zero = static_cast<RingType>( 0 );
williamr@2:         RingType const  temp = gcd_euclidean( a, b );
williamr@2: 
williamr@2:         return ( temp != zero ) ? ( a / temp * b ) : zero;
williamr@2:     }
williamr@2: 
williamr@2:     // Least common multiple for (signed) integers
williamr@2:     template < typename IntegerType >
williamr@2:     inline
williamr@2:     IntegerType
williamr@2:     lcm_integer
williamr@2:     (
williamr@2:         IntegerType const &  a,
williamr@2:         IntegerType const &  b
williamr@2:     )
williamr@2:     {
williamr@2:         // Avoid repeated construction
williamr@2:         IntegerType const  zero = static_cast<IntegerType>( 0 );
williamr@2:         IntegerType const  result = lcm_euclidean( a, b );
williamr@2: 
williamr@2:         return ( result < zero ) ? -result : result;
williamr@2:     }
williamr@2: 
williamr@2:     // Function objects to find the best way of computing GCD or LCM
williamr@2: #ifndef BOOST_NO_LIMITS_COMPILE_TIME_CONSTANTS
williamr@2: #ifndef BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION
williamr@2:     template < typename T, bool IsSpecialized, bool IsSigned >
williamr@2:     struct gcd_optimal_evaluator_helper_t
williamr@2:     {
williamr@2:         T  operator ()( T const &a, T const &b )
williamr@2:         {
williamr@2:             return gcd_euclidean( a, b );
williamr@2:         }
williamr@2:     };
williamr@2: 
williamr@2:     template < typename T >
williamr@2:     struct gcd_optimal_evaluator_helper_t< T, true, true >
williamr@2:     {
williamr@2:         T  operator ()( T const &a, T const &b )
williamr@2:         {
williamr@2:             return gcd_integer( a, b );
williamr@2:         }
williamr@2:     };
williamr@2: #else
williamr@2:     template < bool IsSpecialized, bool IsSigned >
williamr@2:     struct gcd_optimal_evaluator_helper2_t
williamr@2:     {
williamr@2:         template < typename T >
williamr@2:         struct helper
williamr@2:         {
williamr@2:             T  operator ()( T const &a, T const &b )
williamr@2:             {
williamr@2:                 return gcd_euclidean( a, b );
williamr@2:             }
williamr@2:         };
williamr@2:     };
williamr@2: 
williamr@2:     template < >
williamr@2:     struct gcd_optimal_evaluator_helper2_t< true, true >
williamr@2:     {
williamr@2:         template < typename T >
williamr@2:         struct helper
williamr@2:         {
williamr@2:             T  operator ()( T const &a, T const &b )
williamr@2:             {
williamr@2:                 return gcd_integer( a, b );
williamr@2:             }
williamr@2:         };
williamr@2:     };
williamr@2: 
williamr@2:     template < typename T, bool IsSpecialized, bool IsSigned >
williamr@2:     struct gcd_optimal_evaluator_helper_t
williamr@2:         : gcd_optimal_evaluator_helper2_t<IsSpecialized, IsSigned>
williamr@2:            ::BOOST_NESTED_TEMPLATE helper<T>
williamr@2:     {
williamr@2:     };
williamr@2: #endif
williamr@2: 
williamr@2:     template < typename T >
williamr@2:     struct gcd_optimal_evaluator
williamr@2:     {
williamr@2:         T  operator ()( T const &a, T const &b )
williamr@2:         {
williamr@2:             typedef ::std::numeric_limits<T>  limits_type;
williamr@2: 
williamr@2:             typedef gcd_optimal_evaluator_helper_t<T,
williamr@2:              limits_type::is_specialized, limits_type::is_signed>  helper_type;
williamr@2: 
williamr@2:             helper_type  solver;
williamr@2: 
williamr@2:             return solver( a, b );
williamr@2:         }
williamr@2:     };
williamr@2: #else // BOOST_NO_LIMITS_COMPILE_TIME_CONSTANTS
williamr@2:     template < typename T >
williamr@2:     struct gcd_optimal_evaluator
williamr@2:     {
williamr@2:         T  operator ()( T const &a, T const &b )
williamr@2:         {
williamr@2:             return gcd_integer( a, b );
williamr@2:         }
williamr@2:     };
williamr@2: #endif
williamr@2: 
williamr@2: #ifndef BOOST_NO_LIMITS_COMPILE_TIME_CONSTANTS
williamr@2: #ifndef BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION
williamr@2:     template < typename T, bool IsSpecialized, bool IsSigned >
williamr@2:     struct lcm_optimal_evaluator_helper_t
williamr@2:     {
williamr@2:         T  operator ()( T const &a, T const &b )
williamr@2:         {
williamr@2:             return lcm_euclidean( a, b );
williamr@2:         }
williamr@2:     };
williamr@2: 
williamr@2:     template < typename T >
williamr@2:     struct lcm_optimal_evaluator_helper_t< T, true, true >
williamr@2:     {
williamr@2:         T  operator ()( T const &a, T const &b )
williamr@2:         {
williamr@2:             return lcm_integer( a, b );
williamr@2:         }
williamr@2:     };
williamr@2: #else
williamr@2:     template < bool IsSpecialized, bool IsSigned >
williamr@2:     struct lcm_optimal_evaluator_helper2_t
williamr@2:     {
williamr@2:         template < typename T >
williamr@2:         struct helper
williamr@2:         {
williamr@2:             T  operator ()( T const &a, T const &b )
williamr@2:             {
williamr@2:                 return lcm_euclidean( a, b );
williamr@2:             }
williamr@2:         };
williamr@2:     };
williamr@2: 
williamr@2:     template < >
williamr@2:     struct lcm_optimal_evaluator_helper2_t< true, true >
williamr@2:     {
williamr@2:         template < typename T >
williamr@2:         struct helper
williamr@2:         {
williamr@2:             T  operator ()( T const &a, T const &b )
williamr@2:             {
williamr@2:                 return lcm_integer( a, b );
williamr@2:             }
williamr@2:         };
williamr@2:     };
williamr@2: 
williamr@2:     template < typename T, bool IsSpecialized, bool IsSigned >
williamr@2:     struct lcm_optimal_evaluator_helper_t
williamr@2:         : lcm_optimal_evaluator_helper2_t<IsSpecialized, IsSigned>
williamr@2:            ::BOOST_NESTED_TEMPLATE helper<T>
williamr@2:     {
williamr@2:     };
williamr@2: #endif
williamr@2: 
williamr@2:     template < typename T >
williamr@2:     struct lcm_optimal_evaluator
williamr@2:     {
williamr@2:         T  operator ()( T const &a, T const &b )
williamr@2:         {
williamr@2:             typedef ::std::numeric_limits<T>  limits_type;
williamr@2: 
williamr@2:             typedef lcm_optimal_evaluator_helper_t<T,
williamr@2:              limits_type::is_specialized, limits_type::is_signed>  helper_type;
williamr@2: 
williamr@2:             helper_type  solver;
williamr@2: 
williamr@2:             return solver( a, b );
williamr@2:         }
williamr@2:     };
williamr@2: #else // BOOST_NO_LIMITS_COMPILE_TIME_CONSTANTS
williamr@2:     template < typename T >
williamr@2:     struct lcm_optimal_evaluator
williamr@2:     {
williamr@2:         T  operator ()( T const &a, T const &b )
williamr@2:         {
williamr@2:             return lcm_integer( a, b );
williamr@2:         }
williamr@2:     };
williamr@2: #endif
williamr@2: 
williamr@2:     // Functions to find the GCD or LCM in the best way
williamr@2:     template < typename T >
williamr@2:     inline
williamr@2:     T
williamr@2:     gcd_optimal
williamr@2:     (
williamr@2:         T const &  a,
williamr@2:         T const &  b
williamr@2:     )
williamr@2:     {
williamr@2:         gcd_optimal_evaluator<T>  solver;
williamr@2: 
williamr@2:         return solver( a, b );
williamr@2:     }
williamr@2: 
williamr@2:     template < typename T >
williamr@2:     inline
williamr@2:     T
williamr@2:     lcm_optimal
williamr@2:     (
williamr@2:         T const &  a,
williamr@2:         T const &  b
williamr@2:     )
williamr@2:     {
williamr@2:         lcm_optimal_evaluator<T>  solver;
williamr@2: 
williamr@2:         return solver( a, b );
williamr@2:     }
williamr@2: 
williamr@2: }  // namespace detail
williamr@2: 
williamr@2: 
williamr@2: //  Greatest common divisor evaluator member function definition  ------------//
williamr@2: 
williamr@2: template < typename IntegerType >
williamr@2: inline
williamr@2: typename gcd_evaluator<IntegerType>::result_type
williamr@2: gcd_evaluator<IntegerType>::operator ()
williamr@2: (
williamr@2:     first_argument_type const &   a,
williamr@2:     second_argument_type const &  b
williamr@2: ) const
williamr@2: {
williamr@2:     return detail::gcd_optimal( a, b );
williamr@2: }
williamr@2: 
williamr@2: 
williamr@2: //  Least common multiple evaluator member function definition  --------------//
williamr@2: 
williamr@2: template < typename IntegerType >
williamr@2: inline
williamr@2: typename lcm_evaluator<IntegerType>::result_type
williamr@2: lcm_evaluator<IntegerType>::operator ()
williamr@2: (
williamr@2:     first_argument_type const &   a,
williamr@2:     second_argument_type const &  b
williamr@2: ) const
williamr@2: {
williamr@2:     return detail::lcm_optimal( a, b );
williamr@2: }
williamr@2: 
williamr@2: 
williamr@2: //  Greatest common divisor and least common multiple function definitions  --//
williamr@2: 
williamr@2: template < typename IntegerType >
williamr@2: inline
williamr@2: IntegerType
williamr@2: gcd
williamr@2: (
williamr@2:     IntegerType const &  a,
williamr@2:     IntegerType const &  b
williamr@2: )
williamr@2: {
williamr@2:     gcd_evaluator<IntegerType>  solver;
williamr@2: 
williamr@2:     return solver( a, b );
williamr@2: }
williamr@2: 
williamr@2: template < typename IntegerType >
williamr@2: inline
williamr@2: IntegerType
williamr@2: lcm
williamr@2: (
williamr@2:     IntegerType const &  a,
williamr@2:     IntegerType const &  b
williamr@2: )
williamr@2: {
williamr@2:     lcm_evaluator<IntegerType>  solver;
williamr@2: 
williamr@2:     return solver( a, b );
williamr@2: }
williamr@2: 
williamr@2: 
williamr@2: }  // namespace math
williamr@2: }  // namespace boost
williamr@2: 
williamr@2: 
williamr@2: #endif  // BOOST_MATH_COMMON_FACTOR_RT_HPP