boost/math/common_factor_rt.hpp

   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 // boostinspect:nolicense (don't complain about the lack of a Boost license)
  10 // (Paul Moore hasn't been in contact for years, so there's no way to change the
  11 // license.)
  12
  13 //  See http://www.boost.org for updates, documentation, and revision history.
  14
  15 #ifndef BOOST_MATH_COMMON_FACTOR_RT_HPP
  16 #define BOOST_MATH_COMMON_FACTOR_RT_HPP
  17
  18 #include <boost/math_fwd.hpp>  // self include
  19
  20 #include <boost/config.hpp>  // for BOOST_NESTED_TEMPLATE, etc.
  21 #include <boost/limits.hpp>  // for std::numeric_limits
  22 #include <boost/detail/workaround.hpp>
  23
  24
  25 namespace boost
  26 {
  27 namespace math
  28 {
  29
  30
  31 //  Forward declarations for function templates  -----------------------------//
  32
  33 template < typename IntegerType >
  34     IntegerType  gcd( IntegerType const &a, IntegerType const &b );
  35
  36 template < typename IntegerType >
  37     IntegerType  lcm( IntegerType const &a, IntegerType const &b );
  38
  39
  40 //  Greatest common divisor evaluator class declaration  ---------------------//
  41
  42 template < typename IntegerType >
  43 class gcd_evaluator
  44 {
  45 public:
  46     // Types
  47     typedef IntegerType  result_type, first_argument_type, second_argument_type;
  48
  49     // Function object interface
  50     result_type  operator ()( first_argument_type const &a,
  51      second_argument_type const &b ) const;
  52
  53 };  // boost::math::gcd_evaluator
  54
  55
  56 //  Least common multiple evaluator class declaration  -----------------------//
  57
  58 template < typename IntegerType >
  59 class lcm_evaluator
  60 {
  61 public:
  62     // Types
  63     typedef IntegerType  result_type, first_argument_type, second_argument_type;
  64
  65     // Function object interface
  66     result_type  operator ()( first_argument_type const &a,
  67      second_argument_type const &b ) const;
  68
  69 };  // boost::math::lcm_evaluator
  70
  71
  72 //  Implementation details  --------------------------------------------------//
  73
  74 namespace detail
  75 {
  76     // Greatest common divisor for rings (including unsigned integers)
  77     template < typename RingType >
  78     RingType
  79     gcd_euclidean
  80     (
  81         RingType  a,
  82         RingType  b
  83     )
  84     {
  85         // Avoid repeated construction
  86         #ifndef __BORLANDC__
  87         RingType const  zero = static_cast<RingType>( 0 );
  88         #else
  89         RingType  zero = static_cast<RingType>( 0 );
  90         #endif
  91
  92         // Reduce by GCD-remainder property [GCD(a,b) == GCD(b,a MOD b)]
  93         while ( true )
  94         {
  95             if ( a == zero )
  96                 return b;
  97             b %= a;
  98
  99             if ( b == zero )
 100                 return a;
 101             a %= b;
 102         }
 103     }
 104
 105     // Greatest common divisor for (signed) integers
 106     template < typename IntegerType >
 107     inline
 108     IntegerType
 109     gcd_integer
 110     (
 111         IntegerType const &  a,
 112         IntegerType const &  b
 113     )
 114     {
 115         // Avoid repeated construction
 116         IntegerType const  zero = static_cast<IntegerType>( 0 );
 117         IntegerType const  result = gcd_euclidean( a, b );
 118
 119         return ( result < zero ) ? -result : result;
 120     }
 121
 122     // Greatest common divisor for unsigned binary integers
 123     template < typename BuiltInUnsigned >
 124     BuiltInUnsigned
 125     gcd_binary
 126     (
 127         BuiltInUnsigned  u,
 128         BuiltInUnsigned  v
 129     )
 130     {
 131         if ( u && v )
 132         {
 133             // Shift out common factors of 2
 134             unsigned  shifts = 0;
 135
 136             while ( !(u & 1u) && !(v & 1u) )
 137             {
 138                 ++shifts;
 139                 u >>= 1;
 140                 v >>= 1;
 141             }
 142
 143             // Start with the still-even one, if any
 144             BuiltInUnsigned  r[] = { u, v };
 145             unsigned         which = static_cast<bool>( u & 1u );
 146
 147             // Whittle down the values via their differences
 148             do
 149             {
 150 #if BOOST_WORKAROUND(__BORLANDC__, BOOST_TESTED_AT(0x582))
 151                 while ( !(r[ which ] & 1u) )
 152                 {
 153                     r[ which ] = (r[which] >> 1);
 154                 }
 155 #else
 156                 // Remove factors of two from the even one
 157                 while ( !(r[ which ] & 1u) )
 158                 {
 159                     r[ which ] >>= 1;
 160                 }
 161 #endif
 162
 163                 // Replace the larger of the two with their difference
 164                 if ( r[!which] > r[which] )
 165                 {
 166                     which ^= 1u;
 167                 }
 168
 169                 r[ which ] -= r[ !which ];
 170             }
 171             while ( r[which] );
 172
 173             // Shift-in the common factor of 2 to the residues' GCD
 174             return r[ !which ] << shifts;
 175         }
 176         else
 177         {
 178             // At least one input is zero, return the other
 179             // (adding since zero is the additive identity)
 180             // or zero if both are zero.
 181             return u + v;
 182         }
 183     }
 184
 185     // Least common multiple for rings (including unsigned integers)
 186     template < typename RingType >
 187     inline
 188     RingType
 189     lcm_euclidean
 190     (
 191         RingType const &  a,
 192         RingType const &  b
 193     )
 194     {
 195         RingType const  zero = static_cast<RingType>( 0 );
 196         RingType const  temp = gcd_euclidean( a, b );
 197
 198         return ( temp != zero ) ? ( a / temp * b ) : zero;
 199     }
 200
 201     // Least common multiple for (signed) integers
 202     template < typename IntegerType >
 203     inline
 204     IntegerType
 205     lcm_integer
 206     (
 207         IntegerType const &  a,
 208         IntegerType const &  b
 209     )
 210     {
 211         // Avoid repeated construction
 212         IntegerType const  zero = static_cast<IntegerType>( 0 );
 213         IntegerType const  result = lcm_euclidean( a, b );
 214
 215         return ( result < zero ) ? -result : result;
 216     }
 217
 218     // Function objects to find the best way of computing GCD or LCM
 219 #ifndef BOOST_NO_LIMITS_COMPILE_TIME_CONSTANTS
 220 #ifndef BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION
 221     template < typename T, bool IsSpecialized, bool IsSigned >
 222     struct gcd_optimal_evaluator_helper_t
 223     {
 224         T  operator ()( T const &a, T const &b )
 225         {
 226             return gcd_euclidean( a, b );
 227         }
 228     };
 229
 230     template < typename T >
 231     struct gcd_optimal_evaluator_helper_t< T, true, true >
 232     {
 233         T  operator ()( T const &a, T const &b )
 234         {
 235             return gcd_integer( a, b );
 236         }
 237     };
 238 #else
 239     template < bool IsSpecialized, bool IsSigned >
 240     struct gcd_optimal_evaluator_helper2_t
 241     {
 242         template < typename T >
 243         struct helper
 244         {
 245             T  operator ()( T const &a, T const &b )
 246             {
 247                 return gcd_euclidean( a, b );
 248             }
 249         };
 250     };
 251
 252     template < >
 253     struct gcd_optimal_evaluator_helper2_t< true, true >
 254     {
 255         template < typename T >
 256         struct helper
 257         {
 258             T  operator ()( T const &a, T const &b )
 259             {
 260                 return gcd_integer( a, b );
 261             }
 262         };
 263     };
 264
 265     template < typename T, bool IsSpecialized, bool IsSigned >
 266     struct gcd_optimal_evaluator_helper_t
 267         : gcd_optimal_evaluator_helper2_t<IsSpecialized, IsSigned>
 268            ::BOOST_NESTED_TEMPLATE helper<T>
 269     {
 270     };
 271 #endif
 272
 273     template < typename T >
 274     struct gcd_optimal_evaluator
 275     {
 276         T  operator ()( T const &a, T const &b )
 277         {
 278             typedef ::std::numeric_limits<T>  limits_type;
 279
 280             typedef gcd_optimal_evaluator_helper_t<T,
 281              limits_type::is_specialized, limits_type::is_signed>  helper_type;
 282
 283             helper_type  solver;
 284
 285             return solver( a, b );
 286         }
 287     };
 288 #else // BOOST_NO_LIMITS_COMPILE_TIME_CONSTANTS
 289     template < typename T >
 290     struct gcd_optimal_evaluator
 291     {
 292         T  operator ()( T const &a, T const &b )
 293         {
 294             return gcd_integer( a, b );
 295         }
 296     };
 297 #endif
 298
 299     // Specialize for the built-in integers
 300 #define BOOST_PRIVATE_GCD_UF( Ut )                  \
 301     template < >  struct gcd_optimal_evaluator<Ut>  \
 302     {  Ut  operator ()( Ut a, Ut b ) const  { return gcd_binary( a, b ); }  }
 303
 304     BOOST_PRIVATE_GCD_UF( unsigned char );
 305     BOOST_PRIVATE_GCD_UF( unsigned short );
 306     BOOST_PRIVATE_GCD_UF( unsigned );
 307     BOOST_PRIVATE_GCD_UF( unsigned long );
 308
 309 #ifdef BOOST_HAS_LONG_LONG
 310     BOOST_PRIVATE_GCD_UF( boost::ulong_long_type );
 311 #elif defined(BOOST_HAS_MS_INT64)
 312     BOOST_PRIVATE_GCD_UF( unsigned __int64 );
 313 #endif
 314
 315 #undef BOOST_PRIVATE_GCD_UF
 316
 317 #define BOOST_PRIVATE_GCD_SF( St, Ut )                            \
 318     template < >  struct gcd_optimal_evaluator<St>                \
 319     {  St  operator ()( St a, St b ) const  { Ut const  a_abs =   \
 320     static_cast<Ut>( a < 0 ? -a : +a ), b_abs = static_cast<Ut>(  \
 321     b < 0 ? -b : +b ); return static_cast<St>(                    \
 322     gcd_optimal_evaluator<Ut>()(a_abs, b_abs) ); }  }
 323
 324     BOOST_PRIVATE_GCD_SF( signed char, unsigned char );
 325     BOOST_PRIVATE_GCD_SF( short, unsigned short );
 326     BOOST_PRIVATE_GCD_SF( int, unsigned );
 327     BOOST_PRIVATE_GCD_SF( long, unsigned long );
 328
 329     BOOST_PRIVATE_GCD_SF( char, unsigned char ); // should work even if unsigned
 330
 331 #ifdef BOOST_HAS_LONG_LONG
 332     BOOST_PRIVATE_GCD_SF( boost::long_long_type, boost::ulong_long_type );
 333 #elif defined(BOOST_HAS_MS_INT64)
 334     BOOST_PRIVATE_GCD_SF( __int64, unsigned __int64 );
 335 #endif
 336
 337 #undef BOOST_PRIVATE_GCD_SF
 338
 339 #ifndef BOOST_NO_LIMITS_COMPILE_TIME_CONSTANTS
 340 #ifndef BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION
 341     template < typename T, bool IsSpecialized, bool IsSigned >
 342     struct lcm_optimal_evaluator_helper_t
 343     {
 344         T  operator ()( T const &a, T const &b )
 345         {
 346             return lcm_euclidean( a, b );
 347         }
 348     };
 349
 350     template < typename T >
 351     struct lcm_optimal_evaluator_helper_t< T, true, true >
 352     {
 353         T  operator ()( T const &a, T const &b )
 354         {
 355             return lcm_integer( a, b );
 356         }
 357     };
 358 #else
 359     template < bool IsSpecialized, bool IsSigned >
 360     struct lcm_optimal_evaluator_helper2_t
 361     {
 362         template < typename T >
 363         struct helper
 364         {
 365             T  operator ()( T const &a, T const &b )
 366             {
 367                 return lcm_euclidean( a, b );
 368             }
 369         };
 370     };
 371
 372     template < >
 373     struct lcm_optimal_evaluator_helper2_t< true, true >
 374     {
 375         template < typename T >
 376         struct helper
 377         {
 378             T  operator ()( T const &a, T const &b )
 379             {
 380                 return lcm_integer( a, b );
 381             }
 382         };
 383     };
 384
 385     template < typename T, bool IsSpecialized, bool IsSigned >
 386     struct lcm_optimal_evaluator_helper_t
 387         : lcm_optimal_evaluator_helper2_t<IsSpecialized, IsSigned>
 388            ::BOOST_NESTED_TEMPLATE helper<T>
 389     {
 390     };
 391 #endif
 392
 393     template < typename T >
 394     struct lcm_optimal_evaluator
 395     {
 396         T  operator ()( T const &a, T const &b )
 397         {
 398             typedef ::std::numeric_limits<T>  limits_type;
 399
 400             typedef lcm_optimal_evaluator_helper_t<T,
 401              limits_type::is_specialized, limits_type::is_signed>  helper_type;
 402
 403             helper_type  solver;
 404
 405             return solver( a, b );
 406         }
 407     };
 408 #else // BOOST_NO_LIMITS_COMPILE_TIME_CONSTANTS
 409     template < typename T >
 410     struct lcm_optimal_evaluator
 411     {
 412         T  operator ()( T const &a, T const &b )
 413         {
 414             return lcm_integer( a, b );
 415         }
 416     };
 417 #endif
 418
 419     // Functions to find the GCD or LCM in the best way
 420     template < typename T >
 421     inline
 422     T
 423     gcd_optimal
 424     (
 425         T const &  a,
 426         T const &  b
 427     )
 428     {
 429         gcd_optimal_evaluator<T>  solver;
 430
 431         return solver( a, b );
 432     }
 433
 434     template < typename T >
 435     inline
 436     T
 437     lcm_optimal
 438     (
 439         T const &  a,
 440         T const &  b
 441     )
 442     {
 443         lcm_optimal_evaluator<T>  solver;
 444
 445         return solver( a, b );
 446     }
 447
 448 }  // namespace detail
 449
 450
 451 //  Greatest common divisor evaluator member function definition  ------------//
 452
 453 template < typename IntegerType >
 454 inline
 455 typename gcd_evaluator<IntegerType>::result_type
 456 gcd_evaluator<IntegerType>::operator ()
 457 (
 458     first_argument_type const &   a,
 459     second_argument_type const &  b
 460 ) const
 461 {
 462     return detail::gcd_optimal( a, b );
 463 }
 464
 465
 466 //  Least common multiple evaluator member function definition  --------------//
 467
 468 template < typename IntegerType >
 469 inline
 470 typename lcm_evaluator<IntegerType>::result_type
 471 lcm_evaluator<IntegerType>::operator ()
 472 (
 473     first_argument_type const &   a,
 474     second_argument_type const &  b
 475 ) const
 476 {
 477     return detail::lcm_optimal( a, b );
 478 }
 479
 480
 481 //  Greatest common divisor and least common multiple function definitions  --//
 482
 483 template < typename IntegerType >
 484 inline
 485 IntegerType
 486 gcd
 487 (
 488     IntegerType const &  a,
 489     IntegerType const &  b
 490 )
 491 {
 492     gcd_evaluator<IntegerType>  solver;
 493
 494     return solver( a, b );
 495 }
 496
 497 template < typename IntegerType >
 498 inline
 499 IntegerType
 500 lcm
 501 (
 502     IntegerType const &  a,
 503     IntegerType const &  b
 504 )
 505 {
 506     lcm_evaluator<IntegerType>  solver;
 507
 508     return solver( a, b );
 509 }
 510
 511
 512 }  // namespace math
 513 }  // namespace boost
 514
 515
 516 #endif  // BOOST_MATH_COMMON_FACTOR_RT_HPP