Generative Fast Fourier Transforms (GFFT)  0.3
srational.h
1 /***************************************************************************
2  * Copyright (C) 2008-2014 by Vladimir Mirnyy *
3  * *
4  * This program is free software; you can redistribute it and/or modify *
5  * it under the terms of the GNU General Public License as published by *
6  * the Free Software Foundation; either version 2 of the License, or *
7  * (at your option) any later version. *
8  * *
9  * This program is distributed in the hope that it will be useful, *
10  * but WITHOUT ANY WARRANTY; without even the implied warranty of *
11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the *
12  * GNU General Public License for more details. *
13  ***************************************************************************/
14 
15 #ifndef __srational_h
16 #define __srational_h
17 
18 #include "sbigint.h"
19 
20 template<class Num, class Den>
21 struct SRational {
22  typedef Num Numer;
23  typedef Den Denom;
24 };
25 
26 typedef SRational<SInt<1>,SInt<1> > UnitRational;
27 
28 
30 
31 template<class A, class B, int C>
32 struct __GCD;
33 
34 template<class A, class B>
35 struct __GCD<A,B,0> {
36  typedef A Result;
37 };
38 
39 template<bool S1, class N1, bool S2, class N2, base_t B>
40 struct __GCD<SBigInt<S1,N1,B>, SBigInt<S2,N2,B>, 1> {
41  typedef SBigInt<S1,N1,B> TN1;
42  typedef SBigInt<S2,N2,B> TN2;
43  typedef typename Div<TN1,TN2>::ModResult Mod;
44  static const int C = NL::Compare<TN2,Mod>::value;
45  typedef typename __GCD<TN2,Mod,C>::Result Result;
46 };
47 
48 template<bool S1, class N1, base_t B1, bool S2, class N2, base_t B2>
49 struct __GCD<SBigInt<S1,N1,B1>, SBigInt<S2,N2,B2>, -1>
50 : public __GCD<SBigInt<S2,N2,B2>, SBigInt<S1,N1,B1>, 1> {};
51 
52 template<bool S, class N1, base_t Base, int_t N2>
53 struct __GCD<SBigInt<S,N1,Base>, SInt<N2>, 1> {
54  typedef typename Div<SBigInt<S,N1,Base>,SInt<N2> >::ModResult Mod;
55  static const int C = NL::Compare<SInt<N2>,Mod>::value;
56  typedef typename __GCD<SInt<N2>,Mod,C>::Result Result;
57 };
58 
59 template<bool S, class N1, base_t Base, int_t N2>
60 struct __GCD<SBigInt<S,N1,Base>, SInt<N2>, -1>
61 : public __GCD<SInt<N2>, SBigInt<S,N1,Base>, 1> {};
62 
63 template<bool S, class N1, base_t Base, int_t N2>
64 struct __GCD<SInt<N2>, SBigInt<S,N1,Base>, 1>
65 {
66  static const int_t N = Evaluate2Int<SBigInt<S,N1,Base>, int_t>::Value;
67  static const int C = (N2<N) ? -1 : (N2>N) ? 1 : 0;
68  typedef typename __GCD<SInt<N2>,SInt<N>,C>::Result Result;
69 };
70 
71 template<bool S, class N1, base_t Base, int_t N2>
72 struct __GCD<SInt<N2>, SBigInt<S,N1,Base>, -1>
73 : public __GCD<SBigInt<S,N1,Base>, SInt<N2>, 1> {};
74 
75 template<int_t N1, int_t N2>
76 struct __GCD<SInt<N1>, SInt<N2>, 1> {
77  static const int_t N = N1%N2;
78  static const int C = (N2<N) ? -1 : (N2>N) ? 1 : 0;
79  typedef typename __GCD<SInt<N2>,SInt<N>,C>::Result Result;
80 };
81 
82 template<int_t N1, int_t N2>
83 struct __GCD<SInt<N1>, SInt<N2>, -1>
84 : public __GCD<SInt<N2>, SInt<N1>, 1> {};
85 
86 template<bool S1, bool S2, class N, base_t Base>
87 struct __GCD<SBigInt<S1,N,Base>, SBigInt<S2,Loki::NullType,Base>, 1> {
88  typedef SBigInt<S1,N,Base> Result;
89 };
90 
91 template<bool S, class N, base_t Base>
92 struct __GCD<SBigInt<S,N,Base>, SInt<1>, 1> {
93  typedef SInt<1> Result;
94 };
95 
96 template<int_t N>
97 struct __GCD<SInt<N>, SInt<1>, 1> {
98  typedef SInt<1> Result;
99 };
100 
101 template<bool S, class N, base_t Base>
102 struct __GCD<SBigInt<S,N,Base>, SInt<0>, 1> {
103  typedef SBigInt<S,N,Base> Result;
104 };
105 
106 template<int_t N>
107 struct __GCD<SInt<N>, SInt<0>, 1> {
108  typedef typename __SwitchToBigInt<N>::Result Result;
109 };
110 
111 
112 template<class N1, class N2>
113 class GCD {
114  typedef typename Abs<N1>::Result AN1;
115  typedef typename Abs<N2>::Result AN2;
116  static const int C = NL::Compare<AN1,AN2>::value;
117 public:
118  typedef typename __GCD<AN1,AN2,C>::Result Result;
119 };
120 
121 template<bool S1, class T1, bool S2, class T2, base_t B>
122 class GCD<SBigInt<S1,Loki::Typelist<SInt<0>,T1>,B>,
123  SBigInt<S2,Loki::Typelist<SInt<0>,T2>,B> > {
124  typedef typename GCD<SBigInt<S1,T1,B>,SBigInt<S2,T2,B> >::Result Next;
125  typedef typename CreateBigInt<Next,B>::Result NextBig;
126  typedef Loki::Typelist<SInt<0>,typename NextBig::Num> NList;
127 public:
128  typedef SBigInt<true,NList,B> Result;
129 };
130 
131 
132 
133 template<class N, class D>
134 class Simplify<SRational<N,D> > {
135  typedef typename Abs<N>::Result AN;
136  typedef typename GCD<AN,D>::Result T;
137  typedef typename Div<N,T>::DivResult Num;
138  typedef typename Div<D,T>::DivResult Den;
139 public:
140  typedef SRational<Num,Den> Result;
141 };
142 
144 template<class N1, class D1, class N2, class D2>
145 class Mult<SRational<N1,D1>, SRational<N2,D2> > {
146  typedef typename GCD<N1,D2>::Result G1;
147  typedef typename GCD<N2,D1>::Result G2;
148  typedef typename Div<N1,G1>::DivResult NN1;
149  typedef typename Div<N2,G2>::DivResult NN2;
150  typedef typename Div<D2,G1>::DivResult DD2;
151  typedef typename Div<D1,G2>::DivResult DD1;
152  typedef typename Mult<NN1,NN2>::Result Num;
153  typedef typename Mult<DD1,DD2>::Result Den;
154 public:
155  typedef SRational<Num,Den> Result;
156 };
157 
158 template<class N, class D>
159 class Mult<SRational<N,D>, SRational<N,D> > {
160  typedef typename Mult<N,N>::Result Num;
161  typedef typename Mult<D,D>::Result Den;
162 public:
163  typedef SRational<Num,Den> Result;
164 };
165 
166 template<int_t N1, int_t D1, int_t N2, int_t D2>
167 class Mult<SRational<SInt<N1>,SInt<D1> >, SRational<SInt<N2>,SInt<D2> > > {
168  static const int_t Num = N1*N2;
169  static const int_t Den = D1*D2;
170  typedef typename GCD<SInt<Num>, SInt<Den> >::Result T; // T must remain SInt
171  typedef typename __SwitchToBigInt<Num/T::value>::Result NumT;
172  typedef typename __SwitchToBigInt<Den/T::value>::Result DenT;
173 public:
174  typedef SRational<NumT,DenT> Result;
175 };
176 
177 template<int_t N, int_t D>
178 class Mult<SRational<SInt<N>,SInt<D> >, SRational<SInt<N>,SInt<D> > > {
179  static const int_t Num = N*N;
180  static const int_t Den = D*D;
181  typedef typename __SwitchToBigInt<Num>::Result NumT;
182  typedef typename __SwitchToBigInt<Den>::Result DenT;
183 public:
184  typedef SRational<NumT,DenT> Result;
185 };
186 
187 template<class N, class D, int_t Num>
188 class Mult<SRational<N,D>,SInt<Num> > {
189  typedef typename GCD<SInt<Num>,D>::Result G;
190  typedef typename Div<SInt<Num>,G>::DivResult Num1;
191  typedef typename Div<D,G>::DivResult D1;
192  typedef typename Mult<N,Num1>::Result Numer;
193 public:
194  typedef SRational<Numer,D1> Result;
195 };
196 
197 template<class N, class D, int_t Num>
198 class Mult<SInt<Num>, SRational<N,D> > : public Mult<SRational<N,D>,SInt<Num> > {};
199 
200 template<class N, class D, bool S, class NList, unsigned int Base>
201 class Mult<SRational<N,D>,SBigInt<S,NList,Base> > {
202  typedef SBigInt<S,NList,Base> Num;
203  typedef typename GCD<Num,D>::Result G;
204  typedef typename Div<Num,G>::DivResult Num1;
205  typedef typename Div<D,G>::DivResult D1;
206  typedef typename Mult<N,Num1>::Result Numer;
207 public:
208  typedef SRational<Numer,D1> Result;
209 };
210 
211 template<class N, class D, bool S, class NList, unsigned int Base>
212 class Mult<SBigInt<S,NList,Base>,SRational<N,D> > : public Mult<SRational<N,D>,SBigInt<S,NList,Base> > {};
213 
215 
216 template<class Numer, class Denom>
217 struct Negate<SRational<Numer,Denom> > {
218  typedef typename Negate<Numer>::Result NewNumer;
219  typedef SRational<NewNumer,Denom> Result;
220 };
221 
223 
224 template<class N1, class D1, class N2, class D2>
225 class Add<SRational<N1,D1>, SRational<N2,D2> > {
226  typedef typename GCD<D1,D2>::Result G;
227  typedef typename Div<D1,G>::DivResult DD1;
228  typedef typename Div<D2,G>::DivResult DD2;
229  typedef typename Mult<N1,DD2>::Result T1;
230  typedef typename Mult<N2,DD1>::Result T2;
231  typedef typename Add<T1,T2>::Result Num;
232  typedef typename Mult<DD1,D2>::Result Den;
233 public:
234  typedef SRational<Num,Den> Result;
235 };
236 
237 template<class N, class D, int_t Num>
238 class Add<SRational<N,D>,SInt<Num> > {
239  typedef SInt<Num> T;
240  typedef typename Add<
241  typename Mult<D,T>::Result,N>::Result Numer;
242 public:
243  typedef SRational<Numer,D> Result;
244 };
245 
246 template<class N, class D, int_t Num>
247 class Add<SInt<Num>, SRational<N,D> > : public Add<SRational<N,D>,SInt<Num> > {};
248 
249 
250 template<class N, class D, bool S, class NList, base_t Base>
251 class Add<SRational<N,D>,SBigInt<S,NList,Base> > {
252  typedef SBigInt<S,NList,Base> T;
253  typedef typename Add<
254  typename Mult<D,T>::Result,N>::Result Numer;
255 public:
256  typedef SRational<Numer,D> Result;
257 };
258 
259 template<class N, class D, bool S, class NList, base_t Base>
260 class Add<SBigInt<S,NList,Base>,SRational<N,D> > : public Add<SRational<N,D>,SBigInt<S,NList,Base> > {};
261 
263 
264 template<class N1, class D1, class N2, class D2>
265 class Sub<SRational<N1,D1>, SRational<N2,D2> >
266 : public Add<SRational<N1,D1>, typename Negate<SRational<N2,D2> >::Result> { };
267 
268 template<class N, class D, int_t Num>
269 class Sub<SRational<N,D>,SInt<Num> > : public Add<SRational<N,D>,SInt<-Num> > { };
270 
271 template<class N, class D, int_t Num>
272 class Sub<SInt<Num>, SRational<N,D> > : public Add<SInt<Num>, typename Negate<SRational<N,D> >::Result> { };
273 
275 
276 template<class N, class D>
277 struct Check<SRational<N,D> >
278 {
279  typedef typename Check<N>::Result CheckN;
280  typedef typename Check<D>::Result CheckD;
281  typedef SRational<CheckN,CheckD> Result;
282 };
283 
284 #endif
Generated on Mon Feb 10 2014 for Generative Fast Fourier Transforms (GFFT) by DoxyGen 1.8.3.1