summaryrefslogtreecommitdiff
path: root/boost/integer
diff options
context:
space:
mode:
Diffstat (limited to 'boost/integer')
-rw-r--r--boost/integer/common_factor.hpp16
-rw-r--r--boost/integer/common_factor_ct.hpp102
-rw-r--r--boost/integer/common_factor_rt.hpp460
3 files changed, 578 insertions, 0 deletions
diff --git a/boost/integer/common_factor.hpp b/boost/integer/common_factor.hpp
new file mode 100644
index 0000000000..fab919937c
--- /dev/null
+++ b/boost/integer/common_factor.hpp
@@ -0,0 +1,16 @@
+// Boost common_factor.hpp header file -------------------------------------//
+
+// (C) Copyright Daryle Walker 2001-2002.
+// Distributed under the Boost Software License, Version 1.0. (See
+// accompanying file LICENSE_1_0.txt or copy at
+// http://www.boost.org/LICENSE_1_0.txt)
+
+// See http://www.boost.org for updates, documentation, and revision history.
+
+#ifndef BOOST_INTEGER_COMMON_FACTOR_HPP
+#define BOOST_INTEGER_COMMON_FACTOR_HPP
+
+#include <boost/integer/common_factor_ct.hpp>
+#include <boost/integer/common_factor_rt.hpp>
+
+#endif // BOOST_INTEGER_COMMON_FACTOR_HPP
diff --git a/boost/integer/common_factor_ct.hpp b/boost/integer/common_factor_ct.hpp
new file mode 100644
index 0000000000..0671d161c3
--- /dev/null
+++ b/boost/integer/common_factor_ct.hpp
@@ -0,0 +1,102 @@
+// Boost common_factor_ct.hpp header file ----------------------------------//
+
+// (C) Copyright Daryle Walker and Stephen Cleary 2001-2002.
+// Distributed under the Boost Software License, Version 1.0. (See
+// accompanying file LICENSE_1_0.txt or copy at
+// http://www.boost.org/LICENSE_1_0.txt)
+
+// See http://www.boost.org for updates, documentation, and revision history.
+
+#ifndef BOOST_INTEGER_COMMON_FACTOR_CT_HPP
+#define BOOST_INTEGER_COMMON_FACTOR_CT_HPP
+
+#include <boost/integer_fwd.hpp> // self include
+#include <boost/config.hpp> // for BOOST_STATIC_CONSTANT, etc.
+
+namespace boost
+{
+namespace integer
+{
+
+// Implementation details --------------------------------------------------//
+
+namespace detail
+{
+ // Build GCD with Euclid's recursive algorithm
+ template < static_gcd_type Value1, static_gcd_type Value2 >
+ struct static_gcd_helper_t
+ {
+ private:
+ BOOST_STATIC_CONSTANT( static_gcd_type, new_value1 = Value2 );
+ BOOST_STATIC_CONSTANT( static_gcd_type, new_value2 = Value1 % Value2 );
+
+ #ifndef __BORLANDC__
+ #define BOOST_DETAIL_GCD_HELPER_VAL(Value) static_cast<static_gcd_type>(Value)
+ #else
+ typedef static_gcd_helper_t self_type;
+ #define BOOST_DETAIL_GCD_HELPER_VAL(Value) (self_type:: Value )
+ #endif
+
+ typedef static_gcd_helper_t< BOOST_DETAIL_GCD_HELPER_VAL(new_value1),
+ BOOST_DETAIL_GCD_HELPER_VAL(new_value2) > next_step_type;
+
+ #undef BOOST_DETAIL_GCD_HELPER_VAL
+
+ public:
+ BOOST_STATIC_CONSTANT( static_gcd_type, value = next_step_type::value );
+ };
+
+ // Non-recursive case
+ template < static_gcd_type Value1 >
+ struct static_gcd_helper_t< Value1, 0UL >
+ {
+ BOOST_STATIC_CONSTANT( static_gcd_type, value = Value1 );
+ };
+
+ // Build the LCM from the GCD
+ template < static_gcd_type Value1, static_gcd_type Value2 >
+ struct static_lcm_helper_t
+ {
+ typedef static_gcd_helper_t<Value1, Value2> gcd_type;
+
+ BOOST_STATIC_CONSTANT( static_gcd_type, value = Value1 / gcd_type::value
+ * Value2 );
+ };
+
+ // Special case for zero-GCD values
+ template < >
+ struct static_lcm_helper_t< 0UL, 0UL >
+ {
+ BOOST_STATIC_CONSTANT( static_gcd_type, value = 0UL );
+ };
+
+} // namespace detail
+
+
+// Compile-time greatest common divisor evaluator class declaration --------//
+
+template < static_gcd_type Value1, static_gcd_type Value2 > struct static_gcd
+{
+ BOOST_STATIC_CONSTANT( static_gcd_type, value = (detail::static_gcd_helper_t<Value1, Value2>::value) );
+}; // boost::integer::static_gcd
+
+#if !defined(BOOST_NO_INCLASS_MEMBER_INITIALIZATION)
+template< static_gcd_type Value1, static_gcd_type Value2 > static_gcd_type const static_gcd< Value1, Value2 >::value;
+#endif
+
+// Compile-time least common multiple evaluator class declaration ----------//
+
+template < static_gcd_type Value1, static_gcd_type Value2 > struct static_lcm
+{
+ BOOST_STATIC_CONSTANT( static_gcd_type, value = (detail::static_lcm_helper_t<Value1, Value2>::value) );
+}; // boost::integer::static_lcm
+
+#if !defined(BOOST_NO_INCLASS_MEMBER_INITIALIZATION)
+template< static_gcd_type Value1, static_gcd_type Value2 > static_gcd_type const static_lcm< Value1, Value2 >::value;
+#endif
+
+} // namespace integer
+} // namespace boost
+
+
+#endif // BOOST_INTEGER_COMMON_FACTOR_CT_HPP
diff --git a/boost/integer/common_factor_rt.hpp b/boost/integer/common_factor_rt.hpp
new file mode 100644
index 0000000000..c2b54db8e8
--- /dev/null
+++ b/boost/integer/common_factor_rt.hpp
@@ -0,0 +1,460 @@
+// Boost common_factor_rt.hpp header file ----------------------------------//
+
+// (C) Copyright Daryle Walker and Paul Moore 2001-2002. Permission to copy,
+// use, modify, sell and distribute this software is granted provided this
+// copyright notice appears in all copies. This software is provided "as is"
+// without express or implied warranty, and with no claim as to its suitability
+// for any purpose.
+
+// boostinspect:nolicense (don't complain about the lack of a Boost license)
+// (Paul Moore hasn't been in contact for years, so there's no way to change the
+// license.)
+
+// See http://www.boost.org for updates, documentation, and revision history.
+
+#ifndef BOOST_INTEGER_COMMON_FACTOR_RT_HPP
+#define BOOST_INTEGER_COMMON_FACTOR_RT_HPP
+
+#include <boost/integer_fwd.hpp> // self include
+
+#include <boost/config.hpp> // for BOOST_NESTED_TEMPLATE, etc.
+#include <boost/limits.hpp> // for std::numeric_limits
+#include <climits> // for CHAR_MIN
+#include <boost/detail/workaround.hpp>
+
+#ifdef BOOST_MSVC
+#pragma warning(push)
+#pragma warning(disable:4127 4244) // Conditional expression is constant
+#endif
+
+namespace boost
+{
+namespace integer
+{
+
+
+// Forward declarations for function templates -----------------------------//
+
+template < typename IntegerType >
+ IntegerType gcd( IntegerType const &a, IntegerType const &b );
+
+template < typename IntegerType >
+ IntegerType lcm( IntegerType const &a, IntegerType const &b );
+
+
+// Greatest common divisor evaluator class declaration ---------------------//
+
+template < typename IntegerType >
+class gcd_evaluator
+{
+public:
+ // Types
+ typedef IntegerType result_type, first_argument_type, second_argument_type;
+
+ // Function object interface
+ result_type operator ()( first_argument_type const &a,
+ second_argument_type const &b ) const;
+
+}; // boost::integer::gcd_evaluator
+
+
+// Least common multiple evaluator class declaration -----------------------//
+
+template < typename IntegerType >
+class lcm_evaluator
+{
+public:
+ // Types
+ typedef IntegerType result_type, first_argument_type, second_argument_type;
+
+ // Function object interface
+ result_type operator ()( first_argument_type const &a,
+ second_argument_type const &b ) const;
+
+}; // boost::integer::lcm_evaluator
+
+
+// Implementation details --------------------------------------------------//
+
+namespace detail
+{
+ // Greatest common divisor for rings (including unsigned integers)
+ template < typename RingType >
+ RingType
+ gcd_euclidean
+ (
+ RingType a,
+ RingType b
+ )
+ {
+ // Avoid repeated construction
+ #ifndef __BORLANDC__
+ RingType const zero = static_cast<RingType>( 0 );
+ #else
+ RingType zero = static_cast<RingType>( 0 );
+ #endif
+
+ // Reduce by GCD-remainder property [GCD(a,b) == GCD(b,a MOD b)]
+ while ( true )
+ {
+ if ( a == zero )
+ return b;
+ b %= a;
+
+ if ( b == zero )
+ return a;
+ a %= b;
+ }
+ }
+
+ // Greatest common divisor for (signed) integers
+ template < typename IntegerType >
+ inline
+ IntegerType
+ gcd_integer
+ (
+ IntegerType const & a,
+ IntegerType const & b
+ )
+ {
+ // Avoid repeated construction
+ IntegerType const zero = static_cast<IntegerType>( 0 );
+ IntegerType const result = gcd_euclidean( a, b );
+
+ return ( result < zero ) ? static_cast<IntegerType>(-result) : result;
+ }
+
+ // Greatest common divisor for unsigned binary integers
+ template < typename BuiltInUnsigned >
+ BuiltInUnsigned
+ gcd_binary
+ (
+ BuiltInUnsigned u,
+ BuiltInUnsigned v
+ )
+ {
+ if ( u && v )
+ {
+ // Shift out common factors of 2
+ unsigned shifts = 0;
+
+ while ( !(u & 1u) && !(v & 1u) )
+ {
+ ++shifts;
+ u >>= 1;
+ v >>= 1;
+ }
+
+ // Start with the still-even one, if any
+ BuiltInUnsigned r[] = { u, v };
+ unsigned which = static_cast<bool>( u & 1u );
+
+ // Whittle down the values via their differences
+ do
+ {
+#if BOOST_WORKAROUND(__BORLANDC__, BOOST_TESTED_AT(0x582))
+ while ( !(r[ which ] & 1u) )
+ {
+ r[ which ] = (r[which] >> 1);
+ }
+#else
+ // Remove factors of two from the even one
+ while ( !(r[ which ] & 1u) )
+ {
+ r[ which ] >>= 1;
+ }
+#endif
+
+ // Replace the larger of the two with their difference
+ if ( r[!which] > r[which] )
+ {
+ which ^= 1u;
+ }
+
+ r[ which ] -= r[ !which ];
+ }
+ while ( r[which] );
+
+ // Shift-in the common factor of 2 to the residues' GCD
+ return r[ !which ] << shifts;
+ }
+ else
+ {
+ // At least one input is zero, return the other
+ // (adding since zero is the additive identity)
+ // or zero if both are zero.
+ return u + v;
+ }
+ }
+
+ // Least common multiple for rings (including unsigned integers)
+ template < typename RingType >
+ inline
+ RingType
+ lcm_euclidean
+ (
+ RingType const & a,
+ RingType const & b
+ )
+ {
+ RingType const zero = static_cast<RingType>( 0 );
+ RingType const temp = gcd_euclidean( a, b );
+
+ return ( temp != zero ) ? ( a / temp * b ) : zero;
+ }
+
+ // Least common multiple for (signed) integers
+ template < typename IntegerType >
+ inline
+ IntegerType
+ lcm_integer
+ (
+ IntegerType const & a,
+ IntegerType const & b
+ )
+ {
+ // Avoid repeated construction
+ IntegerType const zero = static_cast<IntegerType>( 0 );
+ IntegerType const result = lcm_euclidean( a, b );
+
+ return ( result < zero ) ? static_cast<IntegerType>(-result) : result;
+ }
+
+ // Function objects to find the best way of computing GCD or LCM
+#ifndef BOOST_NO_LIMITS_COMPILE_TIME_CONSTANTS
+ template < typename T, bool IsSpecialized, bool IsSigned >
+ struct gcd_optimal_evaluator_helper_t
+ {
+ T operator ()( T const &a, T const &b )
+ {
+ return gcd_euclidean( a, b );
+ }
+ };
+
+ template < typename T >
+ struct gcd_optimal_evaluator_helper_t< T, true, true >
+ {
+ T operator ()( T const &a, T const &b )
+ {
+ return gcd_integer( a, b );
+ }
+ };
+
+ template < typename T >
+ struct gcd_optimal_evaluator
+ {
+ T operator ()( T const &a, T const &b )
+ {
+ typedef ::std::numeric_limits<T> limits_type;
+
+ typedef gcd_optimal_evaluator_helper_t<T,
+ limits_type::is_specialized, limits_type::is_signed> helper_type;
+
+ helper_type solver;
+
+ return solver( a, b );
+ }
+ };
+#else // BOOST_NO_LIMITS_COMPILE_TIME_CONSTANTS
+ template < typename T >
+ struct gcd_optimal_evaluator
+ {
+ T operator ()( T const &a, T const &b )
+ {
+ return gcd_integer( a, b );
+ }
+ };
+#endif
+
+ // Specialize for the built-in integers
+#define BOOST_PRIVATE_GCD_UF( Ut ) \
+ template < > struct gcd_optimal_evaluator<Ut> \
+ { Ut operator ()( Ut a, Ut b ) const { return gcd_binary( a, b ); } }
+
+ BOOST_PRIVATE_GCD_UF( unsigned char );
+ BOOST_PRIVATE_GCD_UF( unsigned short );
+ BOOST_PRIVATE_GCD_UF( unsigned );
+ BOOST_PRIVATE_GCD_UF( unsigned long );
+
+#ifdef BOOST_HAS_LONG_LONG
+ BOOST_PRIVATE_GCD_UF( boost::ulong_long_type );
+#elif defined(BOOST_HAS_MS_INT64)
+ BOOST_PRIVATE_GCD_UF( unsigned __int64 );
+#endif
+
+#if CHAR_MIN == 0
+ BOOST_PRIVATE_GCD_UF( char ); // char is unsigned
+#endif
+
+#undef BOOST_PRIVATE_GCD_UF
+
+#define BOOST_PRIVATE_GCD_SF( St, Ut ) \
+ template < > struct gcd_optimal_evaluator<St> \
+ { St operator ()( St a, St b ) const { Ut const a_abs = \
+ static_cast<Ut>( a < 0 ? -a : +a ), b_abs = static_cast<Ut>( \
+ b < 0 ? -b : +b ); return static_cast<St>( \
+ gcd_optimal_evaluator<Ut>()(a_abs, b_abs) ); } }
+
+ BOOST_PRIVATE_GCD_SF( signed char, unsigned char );
+ BOOST_PRIVATE_GCD_SF( short, unsigned short );
+ BOOST_PRIVATE_GCD_SF( int, unsigned );
+ BOOST_PRIVATE_GCD_SF( long, unsigned long );
+
+#if CHAR_MIN < 0
+ BOOST_PRIVATE_GCD_SF( char, unsigned char ); // char is signed
+#endif
+
+#ifdef BOOST_HAS_LONG_LONG
+ BOOST_PRIVATE_GCD_SF( boost::long_long_type, boost::ulong_long_type );
+#elif defined(BOOST_HAS_MS_INT64)
+ BOOST_PRIVATE_GCD_SF( __int64, unsigned __int64 );
+#endif
+
+#undef BOOST_PRIVATE_GCD_SF
+
+#ifndef BOOST_NO_LIMITS_COMPILE_TIME_CONSTANTS
+ template < typename T, bool IsSpecialized, bool IsSigned >
+ struct lcm_optimal_evaluator_helper_t
+ {
+ T operator ()( T const &a, T const &b )
+ {
+ return lcm_euclidean( a, b );
+ }
+ };
+
+ template < typename T >
+ struct lcm_optimal_evaluator_helper_t< T, true, true >
+ {
+ T operator ()( T const &a, T const &b )
+ {
+ return lcm_integer( a, b );
+ }
+ };
+
+ template < typename T >
+ struct lcm_optimal_evaluator
+ {
+ T operator ()( T const &a, T const &b )
+ {
+ typedef ::std::numeric_limits<T> limits_type;
+
+ typedef lcm_optimal_evaluator_helper_t<T,
+ limits_type::is_specialized, limits_type::is_signed> helper_type;
+
+ helper_type solver;
+
+ return solver( a, b );
+ }
+ };
+#else // BOOST_NO_LIMITS_COMPILE_TIME_CONSTANTS
+ template < typename T >
+ struct lcm_optimal_evaluator
+ {
+ T operator ()( T const &a, T const &b )
+ {
+ return lcm_integer( a, b );
+ }
+ };
+#endif
+
+ // Functions to find the GCD or LCM in the best way
+ template < typename T >
+ inline
+ T
+ gcd_optimal
+ (
+ T const & a,
+ T const & b
+ )
+ {
+ gcd_optimal_evaluator<T> solver;
+
+ return solver( a, b );
+ }
+
+ template < typename T >
+ inline
+ T
+ lcm_optimal
+ (
+ T const & a,
+ T const & b
+ )
+ {
+ lcm_optimal_evaluator<T> solver;
+
+ return solver( a, b );
+ }
+
+} // namespace detail
+
+
+// Greatest common divisor evaluator member function definition ------------//
+
+template < typename IntegerType >
+inline
+typename gcd_evaluator<IntegerType>::result_type
+gcd_evaluator<IntegerType>::operator ()
+(
+ first_argument_type const & a,
+ second_argument_type const & b
+) const
+{
+ return detail::gcd_optimal( a, b );
+}
+
+
+// Least common multiple evaluator member function definition --------------//
+
+template < typename IntegerType >
+inline
+typename lcm_evaluator<IntegerType>::result_type
+lcm_evaluator<IntegerType>::operator ()
+(
+ first_argument_type const & a,
+ second_argument_type const & b
+) const
+{
+ return detail::lcm_optimal( a, b );
+}
+
+
+// Greatest common divisor and least common multiple function definitions --//
+
+template < typename IntegerType >
+inline
+IntegerType
+gcd
+(
+ IntegerType const & a,
+ IntegerType const & b
+)
+{
+ gcd_evaluator<IntegerType> solver;
+
+ return solver( a, b );
+}
+
+template < typename IntegerType >
+inline
+IntegerType
+lcm
+(
+ IntegerType const & a,
+ IntegerType const & b
+)
+{
+ lcm_evaluator<IntegerType> solver;
+
+ return solver( a, b );
+}
+
+
+} // namespace integer
+} // namespace boost
+
+#ifdef BOOST_MSVC
+#pragma warning(pop)
+#endif
+
+#endif // BOOST_INTEGER_COMMON_FACTOR_RT_HPP