Advertisement
Guest User

Untitled

a guest
Aug 1st, 2011
263
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.82 KB | None | 0 0
  1.     template <int64_t m, int64_t n>
  2.     struct nod;
  3.  
  4.     template <int64_t n>
  5.     struct nod<0, n>
  6.     {
  7.       static const int64_t value = n;
  8.     };
  9.     template <int64_t m>
  10.     struct nod<m, 0>
  11.     {
  12.       static const int64_t value = m;
  13.     };
  14.     template <int64_t m>
  15.     struct nod<m, m>
  16.     {
  17.       static const int64_t value = m;
  18.     };
  19.     template <int64_t m>
  20.     struct nod<m, 1>
  21.     {
  22.       static const int64_t value = 1;
  23.     };
  24.     template <int64_t n>
  25.     struct nod<1, n>
  26.     {
  27.       static const int64_t value = 1;
  28.     };
  29.  
  30.     template <bool m_odd, bool n_odd, int64_t m, int64_t n>
  31.     struct nod_calc;
  32.  
  33.     template <int64_t m, int64_t n>
  34.     struct nod
  35.     {
  36.       static const bool m_odd = m & 1;
  37.       static const bool n_odd = n & 1;
  38.       static const int64_t value = nod_calc<m_odd, n_odd, m, n>::value;
  39.     };
  40.  
  41.     // Если m, n чётные, то НОД(m, n) = 2*НОД(m/2, n/2);
  42.     template <int64_t m, int64_t n>
  43.     struct nod_calc<false, false, m, n>
  44.     {
  45.       static const int64_t value = 2 * nod<m/2, n/2>::value;
  46.     };
  47.     // Если m чётное, n нечётное, то НОД(m, n) = НОД(m/2, n);
  48.     template <int64_t m, int64_t n>
  49.     struct nod_calc<false, true, m, n>
  50.     {
  51.       static const int64_t value = nod<m/2, n>::value;
  52.     };
  53.     // Если n чётное, m нечётное, то НОД(m, n) = НОД(m, n/2);
  54.     template <int64_t m, int64_t n>
  55.     struct nod_calc<true, false, m, n>
  56.     {
  57.       static const int64_t value = nod<m, n/2>::value;
  58.     };
  59.     // Если m, n нечётные, то НОД(m, n) = НОД(n, |m - n|).
  60.     template <int64_t m, int64_t n>
  61.     struct nod_calc<true, true, m, n>
  62.     {
  63.       static const int64_t mod = n>m ? n-m : m-n;
  64.       static const int64_t value = nod<n, mod>::value;
  65.     };
  66.  
  67.  
  68.     template <bool, class R>
  69.     struct reduce_accurate;
  70.  
  71.     template <bool, class R>
  72.     struct reduce_inaccurate
  73.     {
  74.       typedef rational_t<(R::a >> 1), (R::b >> 1)> type_;
  75.       typedef typename reduce_accurate<require_reduce<type_>::value, type_>::type type;
  76.     };
  77.  
  78.     template <class R>
  79.     struct reduce_inaccurate<false, R>
  80.     {
  81.       typedef R type;
  82.     };
  83.  
  84.     template <bool, class R>
  85.     struct reduce_accurate
  86.     {
  87.       const static int64_t new_a = R::a / nod<R::a, R::b>::value;
  88.       const static int64_t new_b = R::b / nod<R::a, R::b>::value;
  89.  
  90.       typedef rational_t<new_a, new_b> new_type;
  91.       typedef typename reduce_accurate<false, new_type>::type type;
  92.     };
  93.  
  94.     template <class R>
  95.     struct reduce_accurate<false, R>
  96.     {
  97.       typedef typename reduce_inaccurate<require_reduce<R>::value, R>::type type;
  98.     };
  99.  
  100.     template <class R>
  101.     struct reduce
  102.     {
  103.       typedef typename reduce_accurate<require_reduce<R>::value, R>::type type;
  104.     };
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement