48 #ifndef VIGRA_RATIONAL_HPP
49 #define VIGRA_RATIONAL_HPP
55 #include "mathutil.hxx"
56 #include "numerictraits.hxx"
57 #include "metaprogramming.hxx"
80 template <
typename IntType>
81 IntType
gcd(IntType n, IntType m)
121 template <
typename IntType>
122 IntType
lcm(IntType n, IntType m)
127 if (n == zero || m == zero)
140 class bad_rational :
public std::domain_error
143 explicit bad_rational() : std::domain_error(
"bad rational: zero denominator") {}
146 template <
typename IntType>
149 template <
typename IntType>
151 template <
typename IntType>
153 template <
typename IntType>
155 template <
typename IntType>
192 template <
typename IntType>
203 typedef typename If<typename TypeTraits<IntType>::isBuiltinType,
249 : num(IntType(v < 0.0 ?
252 den(IntType(1.0/epsilon + 0.5))
346 return den == zero && num > zero;
354 return den == zero && num < zero;
362 return den == zero && num != zero;
372 return num == zero ? 0 : num < zero ? -1 : 1;
389 template <
typename IntType>
390 inline Rational<IntType>&
401 template <
typename IntType>
409 if(r.den == zero &&
sign()*r.
sign() < 0)
410 throw bad_rational();
415 assign(r.num, zero,
false);
438 IntType r_num = r.num;
439 IntType r_den = r.den;
441 IntType g =
gcd(den, r_den);
443 num = num * (r_den / g) + r_num * den;
451 template <
typename IntType>
459 if(r.den == zero &&
sign()*r.
sign() > 0)
460 throw bad_rational();
465 assign(-r.num, zero,
false);
470 IntType r_num = r.num;
471 IntType r_den = r.den;
475 IntType g =
gcd(den, r_den);
477 num = num * (r_den / g) - r_num * den;
485 template <
typename IntType>
494 throw bad_rational();
501 throw bad_rational();
502 num = r.num *
sign();
508 IntType r_num = r.num;
509 IntType r_den = r.den;
512 IntType gcd1 = gcd<IntType>(num, r_den);
513 IntType gcd2 = gcd<IntType>(r_num, den);
514 num = (num/gcd1) * (r_num/gcd2);
515 den = (den/gcd2) * (r_den/gcd1);
519 template <
typename IntType>
528 throw bad_rational();
536 throw bad_rational();
537 num = IntType(
sign());
546 IntType r_num = r.num;
547 IntType r_den = r.den;
550 IntType gcd1 = gcd<IntType>(num, r_num);
551 IntType gcd2 = gcd<IntType>(r_den, den);
552 num = (num/gcd1) * (r_den/gcd2);
553 den = (den/gcd2) * (r_num/gcd1);
563 template <
typename IntType>
571 template <
typename IntType>
579 template <
typename IntType>
590 throw bad_rational();
600 IntType g =
gcd(i, den);
606 template <
typename IntType>
617 throw bad_rational();
618 num = IntType(
sign());
623 IntType g =
gcd(i, num);
638 template <
typename IntType>
646 template <
typename IntType>
655 template <
typename IntType>
664 throw bad_rational();
678 IntType g = gcd<IntType>(num, den);
738 #ifndef NO_PARTIAL_TEMPLATE_SPECIALIZATION
741 struct NumericTraits<Rational<T> >
743 typedef Rational<T> Type;
744 typedef Rational<typename NumericTraits<T>::Promote> Promote;
745 typedef Rational<typename NumericTraits<T>::RealPromote> RealPromote;
746 typedef std::complex<Rational<RealPromote> > ComplexPromote;
749 typedef typename NumericTraits<T>::isIntegral isIntegral;
750 typedef VigraTrueType isScalar;
751 typedef typename NumericTraits<T>::isSigned isSigned;
752 typedef VigraTrueType isOrdered;
753 typedef VigraFalseType isComplex;
755 static Type zero() {
return Type(0); }
756 static Type one() {
return Type(1); }
757 static Type nonZero() {
return one(); }
759 static Promote toPromote(Type
const & v)
760 {
return Promote(v.numerator(), v.denominator(),
false); }
761 static RealPromote toRealPromote(Type
const & v)
762 {
return RealPromote(v.numerator(), v.denominator(),
false); }
763 static Type fromPromote(Promote
const & v)
764 {
return Type(NumericTraits<T>::fromPromote(v.numerator()),
765 NumericTraits<T>::fromPromote(v.denominator()),
false); }
766 static Type fromRealPromote(RealPromote
const & v)
767 {
return Type(NumericTraits<T>::fromRealPromote(v.numerator()),
768 NumericTraits<T>::fromRealPromote(v.denominator()),
false); }
772 struct NormTraits<Rational<T> >
774 typedef Rational<T> Type;
775 typedef typename NumericTraits<Type>::Promote SquaredNormType;
776 typedef Type NormType;
780 struct PromoteTraits<Rational<T>, Rational<T> >
782 typedef Rational<typename PromoteTraits<T, T>::Promote> Promote;
783 static Promote toPromote(Rational<T>
const & v) {
return v; }
786 template <
class T1,
class T2>
787 struct PromoteTraits<Rational<T1>, Rational<T2> >
789 typedef Rational<typename PromoteTraits<T1, T2>::Promote> Promote;
790 static Promote toPromote(Rational<T1>
const & v) {
return v; }
791 static Promote toPromote(Rational<T2>
const & v) {
return v; }
794 template <
class T1,
class T2>
795 struct PromoteTraits<Rational<T1>, T2 >
797 typedef Rational<typename PromoteTraits<T1, T2>::Promote> Promote;
798 static Promote toPromote(Rational<T1>
const & v) {
return v; }
799 static Promote toPromote(T2
const & v) {
return Promote(v); }
802 template <
class T1,
class T2>
803 struct PromoteTraits<T1, Rational<T2> >
805 typedef Rational<typename PromoteTraits<T1, T2>::Promote> Promote;
806 static Promote toPromote(T1
const & v) {
return Promote(v); }
807 static Promote toPromote(Rational<T2>
const & v) {
return v; }
810 #endif // NO_PARTIAL_TEMPLATE_SPECIALIZATION
837 template <
typename IntType>
844 template <
typename IntType>
851 template <
typename IntType>
858 template <
typename IntType>
865 template <
typename IntType>
872 template <
typename IntType>
879 template <
typename IntType>
880 inline Rational<IntType>
887 template <
typename IntType>
888 inline Rational<IntType>
895 template <
typename IntType>
896 inline Rational<IntType>
903 template <
typename IntType>
904 inline Rational<IntType>
911 template <
typename IntType>
912 inline Rational<IntType>
919 template <
typename IntType>
920 inline Rational<IntType>
927 template <
typename IntType>
928 inline Rational<IntType>
935 template <
typename IntType>
936 inline Rational<IntType>
953 template <
typename IntType1,
typename IntType2>
963 template <
typename IntType1,
typename IntType2>
971 template <
typename IntType1,
typename IntType2>
979 template <
typename IntType1,
typename IntType2>
989 template <
typename IntType1,
typename IntType2>
997 template <
typename IntType1,
typename IntType2>
1005 template <
typename IntType1,
typename IntType2>
1010 typedef typename PromoteTraits<IntType1, IntType2>::Promote IntType;
1015 if(l.denominator() == zero)
1017 if(r.denominator() == zero)
1019 return l.numerator() < r.numerator();
1023 return l.numerator() < zero;
1025 if(r.denominator() == zero)
1028 return r.numerator() > zero;
1030 if(l.numerator() >= zero && r.numerator() <= zero)
1033 if(l.numerator() <= zero && r.numerator() >= zero)
1038 IntType gcd1 = gcd<IntType>(l.numerator(), r.numerator());
1039 IntType gcd2 = gcd<IntType>(r.denominator(), l.denominator());
1040 return (l.numerator()/gcd1) * (r.denominator()/gcd2) <
1041 (l.denominator()/gcd2) * (r.numerator()/gcd1);
1045 template <
typename IntType1,
typename IntType2>
1047 operator< (const Rational<IntType1> & l, IntType2
const & i)
1050 typedef typename PromoteTraits<IntType1, IntType2>::Promote IntType;
1055 if(l.denominator() == zero)
1058 return l.numerator() < zero;
1060 if(l.numerator() >= zero && i <= zero)
1063 if(l.numerator() <= zero && i >= zero)
1070 if (l.numerator() > zero)
1071 return (l.numerator()/l.denominator()) < i;
1073 return -i < (-l.numerator()/l.denominator());
1077 template <
typename IntType1,
typename IntType2>
1079 operator<(IntType1 const & l, Rational<IntType2>
const & r)
1085 template <
typename IntType1,
typename IntType2>
1093 template <
typename IntType1,
typename IntType2>
1106 template <
typename IntType1,
typename IntType2>
1114 template <
typename IntType1,
typename IntType2>
1122 template <
typename IntType1,
typename IntType2>
1124 operator<=(Rational<IntType1>
const & l, IntType2
const & r)
1130 template <
typename IntType1,
typename IntType2>
1132 operator<=(IntType1 const & l, Rational<IntType2>
const & r)
1138 template <
typename IntType1,
typename IntType2>
1146 template <
typename IntType1,
typename IntType2>
1154 template <
typename IntType1,
typename IntType2>
1168 template <
typename IntType>
1169 inline Rational<IntType>
1179 template <
typename IntType>
1180 inline Rational<IntType>
1187 template <
typename IntType>
1188 inline typename NormTraits<Rational<IntType> >::SquaredNormType
1198 template <
typename IntType>
1207 throw bad_rational();
1226 nnew = IntType(1), dnew = IntType(1);
1227 for(; ae != 0; ae >>= 1, nold *= nold, dold *= dold)
1247 template <
typename IntType>
1251 IntType zero(0), one(1);
1260 template <
typename IntType>
1264 IntType zero(0), one(1);
1288 template <
typename T,
typename IntType>
1302 template <
typename IntType>
1303 std::ostream& operator<< (std::ostream& os, const vigra::Rational<IntType>& r)
1305 os << r.numerator() <<
'/' << r.denominator();
1311 #endif // VIGRA_RATIONAL_HPP
T rational_cast(const Rational< IntType > &src)
Definition: rational.hxx:1289
Rational operator--(int)
Definition: rational.hxx:335
Rational & operator/=(const Rational &r)
Definition: rational.hxx:520
If< typename TypeTraits< IntType >::isBuiltinType, IntType, IntType const & >::type param_type
Definition: rational.hxx:204
param_type denominator() const
Definition: rational.hxx:273
bool is_ninf() const
Definition: rational.hxx:351
Diff2D operator-(Diff2D const &a, Diff2D const &b)
Definition: diff2d.hxx:711
Rational< IntType > pow(const Rational< IntType > &r, int n)
Definition: rational.hxx:1200
Rational(double v, double epsilon=1e-4)
Definition: rational.hxx:248
bool is_pinf() const
Definition: rational.hxx:343
int sign() const
Definition: rational.hxx:369
Rational & operator*=(const Rational &r)
Definition: rational.hxx:486
FFTWComplex< R >::SquaredNormType squaredNorm(const FFTWComplex< R > &a)
squared norm (= squared magnitude)
Definition: fftw3.hxx:1044
Diff2D operator+(Diff2D const &a, Diff2D const &b)
Definition: diff2d.hxx:739
Rational(Rational< U > const &r)
Definition: rational.hxx:216
Rational & assign(param_type n, param_type d, bool doNormalize=true)
Definition: rational.hxx:391
bool is_inf() const
Definition: rational.hxx:359
FFTWComplex< R >::NormType norm(const FFTWComplex< R > &a)
norm (= magnitude)
Definition: fftw3.hxx:1037
Rational(param_type n, param_type d, bool doNormalize=true)
Definition: rational.hxx:236
NumericTraits< T >::Promote sq(T t)
The square function.
Definition: mathutil.hxx:382
IntType value_type
Definition: rational.hxx:198
bool operator!=(FFTWComplex< R > const &a, const FFTWComplex< R > &b)
not equal
Definition: fftw3.hxx:841
Rational & operator+=(const Rational &r)
Definition: rational.hxx:402
IntType lcm(IntType n, IntType m)
Definition: rational.hxx:122
bool operator==(FFTWComplex< R > const &a, const FFTWComplex< R > &b)
equal
Definition: fftw3.hxx:825
Rational()
Definition: rational.hxx:208
Rational(param_type n)
Definition: rational.hxx:223
Rational operator++(int)
Definition: rational.hxx:332
Rational & operator--()
Definition: rational.hxx:647
IntType gcd(IntType n, IntType m)
Definition: rational.hxx:81
param_type numerator() const
Definition: rational.hxx:269
bool operator>=(FixedPoint< IntBits1, FracBits1 > l, FixedPoint< IntBits2, FracBits2 > r)
greater or equal
Definition: fixedpoint.hxx:539
bool operator!() const
Definition: rational.hxx:339
FFTWComplex< R >::NormType abs(const FFTWComplex< R > &a)
absolute value (= magnitude)
Definition: fftw3.hxx:1002
Rational & operator++()
Definition: rational.hxx:639
int ceil(FixedPoint< IntBits, FracBits > v)
rounding up.
Definition: fixedpoint.hxx:675
bool operator>(FixedPoint< IntBits1, FracBits1 > l, FixedPoint< IntBits2, FracBits2 > r)
greater
Definition: fixedpoint.hxx:530
T sign(T t)
The sign function.
Definition: mathutil.hxx:591
Rational & operator-=(const Rational &r)
Definition: rational.hxx:452
int floor(FixedPoint< IntBits, FracBits > v)
rounding down.
Definition: fixedpoint.hxx:667
Definition: rational.hxx:147
Rational & operator=(param_type n)
Definition: rational.hxx:261