← Back to branch summary

~ubuntu-branches/ubuntu/wily/davix/wily

« back to all changes in this revision

Viewing changes to deps/boost_intern/boost/math/common_factor_rt.hpp

  • Committer: Package Import Robot
  • Author(s): Mattias Ellert
  • Date: 2015-07-31 13:17:55 UTC
  • mfrom: (5.1.3 sid)
  • Revision ID: package-import@ubuntu.com-20150731131755-mizprbmn7ogv33te
Tags: 0.4.1-1
* Update to version 0.4.1
* Implement Multi-Arch support

Show diffs side-by-side

added added

removed removed

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