sol/math/ratio.hpp

   1 #if !defined(sol_math_ratio_hpp_included)
   2 #define sol_math_ratio_hpp_included
   3 /// \addtogroup sol_math
   4 /// \{
   5
   6
   7 /**
   8  * \file sol/math/ratio.hpp
   9  * \brief Compute rational values at compile time
  10  *
  11  * \see http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2008/n2661.htm#ratio
  12  *
  13  * \todo ratio comparison
  14  */
  15
  16
  17 #include <climits>
  18 #include <sol/cstdint.hpp>
  19 #include <sol/math/abs.hpp>
  20 #include <sol/math/gcd.hpp>
  21 #include <sol/math/sign.hpp>
  22 #include <sol/static_assert.hpp>
  23 #include <sol/utility/integral_constant.hpp>
  24
  25
  26 namespace sol { namespace math {
  27
  28
  29 namespace bits {
  30
  31
  32 #if !defined(INTMAX_MAX)
  33     #define INTMAX_MAX INT_MAX
  34 #endif
  35
  36
  37 template <intmax_t A, intmax_t B, bool IsPositiveB>
  38 struct add_overflow
  39     : integral_constant<bool, (A <= INTMAX_MAX - B)>
  40 {};
  41
  42
  43 template <intmax_t A, intmax_t B>
  44 struct add_overflow<A, B, false>
  45     : integral_constant<bool, (A >= -INTMAX_MAX - B)>
  46 {};
  47
  48
  49 template <intmax_t A, intmax_t B>
  50 struct add_
  51 {
  52     static_assert((add_overflow<A, B, B >= 0>::value == true), "overflow");
  53     static intmax_t const value = A + B;
  54 };
  55
  56
  57 template <intmax_t A, intmax_t B>
  58 struct multiply_
  59 {
  60     static uintmax_t const c = 1UL << (4*sizeof(intmax_t));
  61
  62     static uintmax_t const a0 = abs<A>::value%c;
  63     static uintmax_t const a1 = abs<A>::value/c;
  64     static uintmax_t const b0 = abs<B>::value%c;
  65     static uintmax_t const b1 = abs<B>::value/c;
  66
  67     static_assert(a1 == 0 || b1 == 0, "overflow");
  68     static_assert((a0*b1 + b0*a1) < (c >> 1), "overflow");
  69     static_assert(b0*a0 <= INTMAX_MAX, "overflow");
  70     static_assert((a0*b1 + b0*a1)*c <= INTMAX_MAX - b0*a0, "overflow");
  71
  72     static intmax_t const value = A*B;
  73 };
  74
  75
  76 }   // namespace bits
  77
  78
  79 /// Rational value representation (calculated during compile-time)
  80 template <intmax_t N, intmax_t D=1>
  81 struct ratio
  82 {
  83     static_assert(D != 0, "division by 0");
  84
  85     /// numerator
  86     static intmax_t const num = N*sign<D>::value/gcd<N, D>::value;
  87
  88     /// denominator
  89     static intmax_t const den = abs<D>::value/gcd<N, D>::value;
  90 };
  91
  92
  93 /// rational arithmetic: addition
  94 template <typename R1, typename R2>
  95 struct ratio_add
  96 {
  97 private:
  98
  99     enum { g = gcd<R1::den, R2::den>::value };
 100
 101
 102 public:
 103
 104     /// result
 105     typedef ratio<
 106         bits::add_<
 107             bits::multiply_<R1::num, R2::den/g>::value
 108             , bits::multiply_<R2::num, R1::den/g>::value
 109         >::value
 110         , bits::multiply_<R1::den, R2::den/g>::value
 111     > type;
 112 };
 113
 114
 115 /// rational arithmetic: subtraction
 116 template <typename R1, typename R2>
 117 struct ratio_subtract
 118 {
 119     /// result
 120     typedef typename ratio_add<
 121         R1
 122         , ratio<-R2::num, R2::den>
 123     >::type type;
 124 };
 125
 126
 127 /// rational arithmetic: multiplication
 128 template <typename R1, typename R2>
 129 struct ratio_multiply
 130 {
 131 private:
 132
 133     enum {
 134         g1 = gcd<R1::num, R2::den>::value
 135         , g2 = gcd<R2::num, R1::den>::value
 136     };
 137
 138 public:
 139
 140     /// result
 141     typedef ratio<
 142         bits::multiply_<R1::num/g1, R2::num/g2>::value
 143         , bits::multiply_<R1::den/g2, R2::den/g1>::value
 144     > type;
 145 };
 146
 147
 148 /// rational arithmetic: division
 149 template <typename R1, typename R2>
 150 struct ratio_divide
 151 {
 152     static_assert(R2::num != 0, "division by 0");
 153
 154     /// result
 155     typedef typename ratio_multiply<
 156         R1
 157         , ratio<R2::den, R2::num>
 158     >::type type;
 159 };
 160
 161
 162 /// Comparison: R1 == R2
 163 template <typename R1, typename R2>
 164 struct ratio_equal
 165     : integral_constant<bool, R1::num == R2::num && R1::den == R2::den>
 166 {};
 167
 168
 169 /// Comparison: R1 != R2
 170 template <typename R1, typename R2>
 171 struct ratio_not_equal
 172     : integral_constant<bool, !ratio_equal<R1, R2>::value>
 173 {};
 174
 175
 176 /// Comparison: R1 < R2
 177 template <typename R1, typename R2>
 178 struct ratio_less
 179     : integral_constant<bool
 180         , bits::multiply_<R1::num, R2::den>::value
 181             < bits::multiply_<R2::num, R1::den>::value
 182       >
 183 {};
 184
 185
 186 /// Comparison: R1 <= R2
 187 template <typename R1, typename R2>
 188 struct ratio_less_equal
 189     : integral_constant<bool, !ratio_less<R2, R1>::value>
 190 {};
 191
 192
 193 /// Comparison: R1 > R2
 194 template <typename R1, typename R2>
 195 struct ratio_greater
 196     : integral_constant<bool, ratio_less<R2, R1>::value>
 197 {};
 198
 199
 200 /// Comparison: R1 >= R2
 201 template <typename R1, typename R2>
 202 struct ratio_greater_equal
 203     : integral_constant<bool, !ratio_less<R1, R2>::value>
 204 {};
 205
 206
 207 /// Convenience SI units
 208 /// \{
 209 typedef ratio<1, 1000000000000000000> atto;
 210 typedef ratio<1,    1000000000000000> femto;
 211 typedef ratio<1,       1000000000000> pico;
 212 typedef ratio<1,          1000000000> nano;
 213 typedef ratio<1,             1000000> micro;
 214 typedef ratio<1,                1000> milli;
 215 typedef ratio<1,                 100> centi;
 216 typedef ratio<1,                  10> deci;
 217 typedef ratio<                 10, 1> deca;
 218 typedef ratio<                100, 1> hecto;
 219 typedef ratio<               1000, 1> kilo;
 220 typedef ratio<            1000000, 1> mega;
 221 typedef ratio<         1000000000, 1> giga;
 222 typedef ratio<      1000000000000, 1> tera;
 223 typedef ratio<   1000000000000000, 1> peta;
 224 typedef ratio<1000000000000000000, 1> exa;
 225 /// \}
 226
 227
 228 }}  // namespace sol::math
 229
 230
 231 /// \}
 232 #endif  // sol_math_ratio_hpp_included