Generative Fast Fourier Transforms (GFFT)  0.3
sbigint.h
Go to the documentation of this file.
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 __sbigint_h
16 #define __sbigint_h
17 
22 #include "sint.h"
23 
24 #include "numtypelist.h"
25 #include "typelistext.h"
26 
27 #include "Typelist.h"
28 #include "TypeManip.h"
29 #include "TypeTraits.h"
30 
31 #include <iostream>
32 
33 //typedef unsigned int base_t;
34 typedef int_t base_t;
35 
36 //static const base_t DefaultBase = (1<<(sizeof(int_t)*4));
37 
38 #ifdef __x86_64
39 // for 64bit
40 //static const base_t DefaultBase = 2147483648;
41 static const base_t DefaultBase = 1000000000;
42 static const base_t DefaultDecimalBase = 1000000000;
43 #else
44 // for 32bit
45 //static const base_t DefaultBase = 65536;
46 static const base_t DefaultBase = 10000;
47 static const base_t DefaultDecimalBase = 10000;
48 #endif
49 
56 template<bool S, class NList,
57  base_t B = DefaultBase>
58 struct SBigInt {
59  static const bool isPositive = S;
60  static const base_t Base = B;
61  typedef NList Num;
62 };
63 
64 template<typename T1, typename T2>
65 struct Pair {
66  typedef T1 first;
67  typedef T2 second;
68 };
69 
70 template<class F1, class F2>
71 class Mult;
72 
73 template<class F1, class F2>
74 class Add;
75 
76 template<class F1, class F2>
77 class Sub;
78 
79 template<class F>
80 class Negate;
81 
82 template<class F1, class F2>
83 class Div;
84 
85 template<class F1, class F2>
86 class Mod;
87 
88 template<class F>
89 class Abs;
90 
91 template<class F>
92 class Sign;
93 
94 template<class N, base_t Base>
95 struct CreateBigInt;
96 
97 
98 template<class T, int Accuracy, base_t Base = DefaultBase>
99 struct Reduce;
100 
101 template<int_t N, int Accuracy, base_t Base>
102 struct Reduce<SInt<N>,Accuracy,Base> {
103  typedef SInt<N> Result;
104 };
105 
106 
108 // bool isInt = Loki::TypeTraits<RetType>::isIntegral,
109 // bool isFloat = Loki::TypeTraits<RetType>::isFloat
110 template<class BInt, class RetType, unsigned long AccumBase = 1>
111 struct Evaluate2IntLoop;
112 
113 template<bool S, class H, class T, base_t Base, class RetType, unsigned long AccumBase>
114 struct Evaluate2IntLoop<SBigInt<S,Loki::Typelist<H,T>,Base>,RetType,AccumBase>
115 {
116  static const RetType Next = Evaluate2IntLoop<SBigInt<S,T,Base>,RetType,AccumBase*Base>::value;
117  static const RetType value = H::value*AccumBase + Next;
118 };
119 
120 template<bool S, base_t Base, class RetType, unsigned long AccumBase>
121 struct Evaluate2IntLoop<SBigInt<S,Loki::NullType,Base>,RetType,AccumBase>
122 {
123  static const RetType value = 0;
124 };
125 
126 template<class BInt, class RetType>
127 struct Evaluate2Int;
128 
129 template<bool S, class NList, base_t Base, class RetType>
130 struct Evaluate2Int<SBigInt<S,NList,Base>,RetType>
131 {
132  static const RetType v = Evaluate2IntLoop<SBigInt<S,NList,Base>,RetType>::value;
133  static const RetType value = S ? v : -v;
134 };
135 
136 template<int_t N, class RetType>
137 struct Evaluate2Int<SInt<N>, RetType>
138 {
139  static const RetType value = N;
140 };
141 
142 
143 template<class BInt, class RetType>
144 struct EvaluateToFloatLoop;
145 
146 template<bool S, class H, class T, base_t Base, class RetType>
147 struct EvaluateToFloatLoop<SBigInt<S,Loki::Typelist<H,T>,Base>,RetType>
148 {
149  static RetType value()
150  {
151  return static_cast<RetType>(H::value) + Base * EvaluateToFloatLoop<SBigInt<S,T,Base>,RetType>::value();
152  }
153 };
154 
155 template<bool S, class H, base_t Base, class RetType>
156 struct EvaluateToFloatLoop<SBigInt<S,Loki::Typelist<H,Loki::NullType>,Base>,RetType>
157 {
158  static RetType value() { return static_cast<RetType>(H::value); }
159 };
160 
161 template<bool S, base_t Base, class RetType>
162 struct EvaluateToFloatLoop<SBigInt<S,Loki::NullType,Base>,RetType>
163 {
164  static RetType value() { return static_cast<RetType>(0); }
165 };
166 
167 
168 template<class BInt, class RetType>
169 struct EvaluateToFloat;
170 
171 template<bool S, class NList, base_t Base, class RetType>
172 struct EvaluateToFloat<SBigInt<S,NList,Base>,RetType>
173 {
174  static RetType value()
175  {
176  RetType v = EvaluateToFloatLoop<SBigInt<S,NList,Base>,RetType>::value();
177  return S ? v : -v;
178  }
179 };
180 
181 template<int_t N, class RetType>
182 struct EvaluateToFloat<SInt<N>,RetType>
183 {
184  static RetType value() { return static_cast<RetType>(N); }
185 };
186 
187 
188 namespace NL
189 {
190 
191 template<bool S1, class N1, bool S2, class N2, base_t B>
192 struct Compare<SBigInt<S1,N1,B>, SBigInt<S2,N2,B> >
193 {
194  static const int c = Compare<N1,N2>::value;
195  static const int value = (S1 && S2) ? c : (!S1 && !S2) ? -c
196  : (S1 && !S2) ? 1 : -1;
197 };
198 
199 template<int_t N1, int_t N2>
200 struct Compare<SInt<N1>, SInt<N2> >
201 {
202  static const int value = (N1 > N2) ? 1 : (N1 < N2) ? -1 : 0;
203 };
204 
205 template<bool S1, class N1, base_t Base, int_t N2>
206 struct Compare<SBigInt<S1,N1,Base>, SInt<N2> >
207 {
208  typedef typename CreateBigInt<SInt<N2>,Base>::Result BI;
209  static const int value = Compare<SBigInt<S1,N1,Base>,BI>::value;
210 };
211 
212 template<bool S1, class N1, base_t B1, int_t N2>
213 struct Compare<SInt<N2>, SBigInt<S1,N1,B1> >
214 {
215  static const int value = -Compare<SBigInt<S1,N1,B1>, SInt<N2> >::value;
216 };
217 
218 template<class N1, class N2>
219 struct CompareAbs : public Compare<typename Abs<N1>::Result, typename Abs<N2>::Result> {};
220 
221 
222 template<class Num>
223 struct Length;
224 
225 template<bool S, class NList, base_t B>
226 struct Length<SBigInt<S,NList,B> > {
227  static const int value = Loki::TL::Length<NList>::value;
228 };
229 
230 template<int_t N>
231 struct Length<SInt<N> > {
232  static const int value = 1;
233 };
234 
235 }
236 
237 
238 
249 template<class NList, base_t Base, int_t Rest=0>
250 struct Align;
251 
252 template<class H, class T, base_t Base, int_t Rest>
253 struct Align<Loki::Typelist<H,T>,Base,Rest> {
254  static const int_t A = H::value+Rest;
255  typedef Loki::Typelist<SInt<A%Base>,
256  typename Align<T,Base,A/Base>::Result> Result;
257 };
258 
259 template<base_t Base, int_t Rest>
260 struct Align<Loki::NullType,Base,Rest> {
261  typedef Loki::Typelist<SInt<Rest%Base>,
262  typename Align<Loki::NullType,Base,Rest/Base>::Result> Result;
263 };
264 
265 template<base_t Base>
266 struct Align<Loki::Typelist<SInt<0>,Loki::NullType>,Base,0> {
267  typedef Loki::NullType Result;
268 };
269 
270 template<base_t Base>
271 struct Align<Loki::NullType,Base,0> {
272  typedef Loki::NullType Result;
273 };
274 
276 
277 template<class N, base_t Base>
278 struct CreateBigInt;
279 
280 template<bool S, class N, base_t Base>
281 struct CreateBigInt<SBigInt<S,N,Base>,Base> {
282  typedef SBigInt<S,N,Base> Result;
283 };
284 
285 template<int_t N, base_t Base>
286 struct CreateBigInt<SInt<N>,Base> {
287  static const bool S = (N>=0);
288  typedef typename Abs<SInt<N> >::Result AN;
289  typedef typename Align<
290  Loki::Typelist<AN,Loki::NullType>,Base>::Result NList;
291  typedef SBigInt<S,NList,Base> Result;
292 };
293 
294 template<base_t Base>
295 struct CreateBigInt<SInt<0>,Base> {
296  typedef SBigInt<true,Loki::NullType,DefaultBase> Result;
297 };
298 
300 
301 template<int_t N, base_t Base = DefaultBase,
302 bool isSmallEnough=((N>=0 && N<Base) || (N<0 && -N<Base))>
303 struct __SwitchToBigInt;
304 
305 template<int_t N, base_t Base>
306 struct __SwitchToBigInt<N,Base,true> {
307  typedef SInt<N> Result;
308 };
309 
310 template<int_t N, base_t Base>
311 struct __SwitchToBigInt<N,Base,false> {
312  typedef typename CreateBigInt<SInt<N>,Base>::Result Result;
313 };
314 
316 
317 template<class N,
318 int_t L = NL::Length<N>::value>
319 struct __SwitchToInt {
320  typedef N Result;
321 };
322 
323 template<class N>
324 struct __SwitchToInt<N,1> {
325  typedef SInt<Evaluate2Int<N,int_t>::value> Result;
326 };
327 
328 template<class N>
329 struct __SwitchToInt<N,0> {
330  typedef SInt<0> Result;
331 };
332 
339 template<int_t N1, int_t N2>
340 struct Add<SInt<N1>, SInt<N2> > {
341  typedef typename __SwitchToBigInt<N1+N2>::Result Result;
342 };
343 
344 template<int_t N>
345 struct Add<SInt<N>, Loki::NullType> {
346  typedef SInt<N> Result;
347 };
348 
349 template<int_t N>
350 struct Add<Loki::NullType, SInt<N> > {
351  typedef SInt<N> Result;
352 };
353 
359 template<int_t N1, int_t N2>
360 struct Sub<SInt<N1>, SInt<N2> > : public Add<SInt<N1>, SInt<-N2> > {};
361 
366 template<int_t N>
367 struct Negate<SInt<N> > {
368  typedef SInt<-N> Result;
369 };
370 
377 template<int_t N1, int_t N2>
378 struct Mult<SInt<N1>, SInt<N2> > {
379  typedef typename __SwitchToBigInt<N1*N2>::Result Result;
380 };
381 
387 template<int_t N1, int_t N2>
388 struct Div<SInt<N1>, SInt<N2> > {
389  typedef SInt<N1/N2> DivResult;
390  typedef SInt<N1%N2> ModResult;
391 };
392 
398 template<int_t N1, int_t N2>
399 struct Mod<SInt<N1>, SInt<N2> > {
400  typedef SInt<N1%N2> Result;
401 };
402 
407 template<int_t N>
408 struct Abs<SInt<N> > {
409  static const int_t AN = (N>0) ? N : -N ;
410  typedef SInt<AN> Result;
411 };
412 
419 template<bool S, class NList, base_t Base>
420 struct Abs<SBigInt<S,NList,Base> > {
421  typedef SBigInt<true,NList,Base> Result;
422 };
423 
431 template<bool S, class NList, base_t Base>
432 struct Negate<SBigInt<S,NList,Base> > {
433  typedef SBigInt<!S,NList,Base> Result;
434 };
435 
437 template<int_t N>
438 struct Sign<SInt<N> > {
439  static const char value = (N>0) ? 1 : ((N<0) ? -1 : 0);
440 };
441 
442 template<bool S, class NList, base_t Base>
443 struct Sign<SBigInt<S,NList,Base> > {
444  static const char value = S ? 1 : -1;
445 };
446 
447 template<bool S, base_t Base>
448 struct Sign<SBigInt<S,Loki::NullType,Base> > {
449  static const char value = 0;
450 };
451 
453 
454 template<class C>
455 struct Simplify;
456 
457 template<bool S, typename NList, base_t Base>
458 struct Simplify<SBigInt<S,NList,Base> > {
459  typedef typename NL::CutTrailingZeros<NList>::Result NewList;
460  typedef typename __SwitchToInt<SBigInt<S,NewList,Base> >::Result Result;
461 };
462 
463 template<int_t N>
464 struct Simplify<SInt<N> > {
465  typedef SInt<N> Result;
466 };
467 
469 
470 template<class B1, class B2, int Comparison>
471 struct __Add;
472 
473 template<class NList1, class NList2, base_t Base>
474 struct __Add<SBigInt<true,NList1,Base>,SBigInt<true,NList2,Base>,1> {
475 private:
476  typedef typename NL::Add<NList1,NList2>::Result Sum;
477  typedef typename Align<Sum,Base>::Result ASum;
478 public:
479  typedef SBigInt<true,ASum,Base> Result;
480 };
481 
482 template<class NList1, class NList2, base_t Base>
483 struct __Add<SBigInt<true,NList1,Base>,SBigInt<false,NList2,Base>,1> {
484 private:
485  static const int_t L = Loki::TL::Length<NList1>::value;
486  typedef typename NL::AddAt<
487  typename NL::AddConst<NList1,SInt<Base-1> >::Result,0,SInt<1> >::Result NList12;
488  typedef typename NL::Sub<NList12,NList2>::Result Dif;
489  typedef typename Align<Dif,Base>::Result ADif;
490  typedef typename Loki::TL::EraseAt<ADif,L>::Result ADif1;
491 public:
492 // typedef typename Simplify<SBigInt<true,ADif1,Base> >::Result Result;
493  typedef SBigInt<true,ADif1,Base> Result;
494 };
495 
496 template<class NList1, class NList2, base_t Base>
497 struct __Add<SBigInt<false,NList1,Base>,SBigInt<true,NList2,Base>,1> {
498  typedef typename Negate<
499  typename __Add<SBigInt<true,NList1,Base>,
500  SBigInt<false,NList2,Base>,1>::Result>::Result Result;
501 };
502 
503 template<class NList1, class NList2, base_t Base>
504 struct __Add<SBigInt<false,NList1,Base>,SBigInt<false,NList2,Base>,1> {
505  typedef typename Negate<
506  typename __Add<SBigInt<true,NList1,Base>,
507  SBigInt<true,NList2,Base>,1>::Result>::Result Result;
508 };
509 
510 template<bool S1, bool S2, class NList1, class NList2, base_t Base>
511 struct __Add<SBigInt<S1,NList1,Base>,SBigInt<S2,NList2,Base>,-1> {
512  typedef typename __Add<SBigInt<S2,NList2,Base>,SBigInt<S1,NList1,Base>,1>::Result Result;
513 };
514 
515 template<class NList1, class NList2, base_t Base>
516 struct __Add<SBigInt<true,NList1,Base>,SBigInt<true,NList2,Base>,0>
517 : public __Add<SBigInt<true,NList1,Base>,SBigInt<true,NList2,Base>,1> {};
518 
519 template<class NList1, class NList2, base_t Base>
520 struct __Add<SBigInt<true,NList1,Base>,SBigInt<false,NList2,Base>,0> {
521  typedef SInt<0> Result;
522 };
523 
524 template<class NList1, class NList2, base_t Base>
525 struct __Add<SBigInt<false,NList1,Base>,SBigInt<true,NList2,Base>,0> {
526  typedef SInt<0> Result;
527 };
528 
529 template<class NList1, class NList2, base_t Base>
530 struct __Add<SBigInt<false,NList1,Base>,SBigInt<false,NList2,Base>,0>
531 : public __Add<SBigInt<false,NList1,Base>,SBigInt<false,NList2,Base>,1> {};
532 
534 
535 template<bool S1, class NList1, bool S2, class NList2, base_t Base>
536 class Add<SBigInt<S1,NList1,Base>,SBigInt<S2,NList2,Base> > {
537  typedef SBigInt<S1,NList1,Base> BI1;
538  typedef SBigInt<S2,NList2,Base> BI2;
539  static const char C = NL::Compare<NList1,NList2>::value;
540 public:
541  typedef typename __Add<BI1,BI2,C>::Result Result;
542 };
543 
544 template<bool S, class NList, base_t Base, int_t N>
545 class Add<SBigInt<S,NList,Base>,SInt<N> > {
546  static const int C = NL::Compare<SBigInt<true,NList,Base>,typename Abs<SInt<N> >::Result>::value;
547  typedef SBigInt<S,NList,Base> BI1;
548  typedef typename CreateBigInt<SInt<N>,Base>::Result BI2;
549 public:
550  typedef typename __Add<BI1,BI2,C>::Result Result;
551 };
552 
553 template<bool S, class NList, base_t Base, int_t N>
554 class Add<SInt<N>,SBigInt<S,NList,Base> > : public Add<SBigInt<S,NList,Base>,SInt<N> > {};
555 
556 template<bool S, class NList, base_t Base>
557 class Add<SBigInt<S,NList,Base>,SInt<0> > {
558 public:
559  typedef SBigInt<S,NList,Base> Result;
560 };
561 
562 template<bool S, base_t Base, int_t N>
563 class Add<SBigInt<S,Loki::NullType,Base>,SInt<N> > {
564 public:
565  typedef SInt<N> Result;
566 };
567 
568 
569 template<bool S1, class NList1, bool S2, class NList2, base_t Base>
570 class Sub<SBigInt<S1,NList1,Base>,SBigInt<S2,NList2,Base> > {
571  typedef SBigInt<S1,NList1,Base> BI1;
572  typedef SBigInt<!S2,NList2,Base> BI2;
573  static const char C = NL::Compare<NList1,NList2>::value;
574 public:
575  typedef typename __Add<BI1,BI2,C>::Result Result;
576 };
577 
578 template<bool S, class NList, base_t Base, int_t N>
579 class Sub<SBigInt<S,NList,Base>,SInt<N> > : public Add<SBigInt<S,NList,Base>,SInt<-N> > {};
580 
581 template<bool S, class NList, base_t Base, int_t N>
582 class Sub<SInt<N>,SBigInt<S,NList,Base> > {
583 public:
584  typedef typename Negate<
585  typename Sub<SBigInt<S,NList,Base>,SInt<N> >::Result>::Result Result;
586 };
587 
589 
590 template<class NList1, class NList2, base_t Base, int_t I=0>
591 struct __MultLoop;
592 
593 template<class Num, class Tail, class NList2, base_t Base, int_t I>
594 struct __MultLoop<Loki::Typelist<Num,Tail>,NList2,Base,I> {
595 private:
596  typedef typename NL::MultConst<NList2,Num>::Result Prod;
597  typedef typename Loki::TL::Repeat<SInt<0>,I>::Result Shift;
598  typedef typename Loki::TL::Append<Shift,Prod>::Result ShiftedProd;
599 public:
600  typedef typename Align<typename NL::Add<ShiftedProd,
601  typename __MultLoop<Tail,NList2,Base,I+1>::Result>::Result,Base>::Result Result;
602 };
603 
604 template<class NList2, base_t Base, int_t I>
605 struct __MultLoop<Loki::NullType,NList2,Base,I> {
606  typedef Loki::NullType Result;
607 };
608 
609 
610 
611 template<bool S1, class NList1, bool S2, class NList2, base_t Base>
612 class Mult<SBigInt<S1,NList1,Base>,SBigInt<S2,NList2,Base> > {
613  typedef typename __MultLoop<NList1,NList2,Base>::Result NListProd;
614  //typedef typename Align<NListProd,Base>::Result ANListProd;
615 public:
616  typedef SBigInt<(S1==S2),NListProd,Base> Result;
617 };
618 
619 template<bool S, class NList, base_t Base, int_t N>
620 class Mult<SBigInt<S,NList,Base>,SInt<N> > {
621  static const int_t A = (N<0) ? -N : N ;
622  static const bool S1 = (N>=0);
623  typedef typename NL::MultConst<NList,SInt<A> >::Result Prod;
624  typedef typename Align<Prod,Base>::Result AProd;
625 public:
626  typedef SBigInt<(S1==S),AProd,Base> Result;
627 };
628 
629 template<bool S, class NList, base_t Base>
630 class Mult<SBigInt<S,NList,Base>,SInt<Base> > {
631 public:
632  typedef SBigInt<S,Loki::Typelist<SInt<0>,NList>,Base> Result;
633 };
634 
635 template<bool S, class NList, base_t Base>
636 class Mult<SBigInt<S,NList,Base>,SInt<-Base> > {
637 public:
638  typedef SBigInt<!S,Loki::Typelist<SInt<0>,NList>,Base> Result;
639 };
640 
641 template<bool S, class NList, base_t Base>
642 class Mult<SBigInt<S,NList,Base>,SInt<1> > {
643 public:
644  typedef SBigInt<S,NList,Base> Result;
645 };
646 
647 template<bool S, class NList, base_t Base>
648 class Mult<SBigInt<S,NList,Base>,SInt<-1> > {
649 public:
650  typedef SBigInt<!S,NList,Base> Result;
651 };
652 
653 template<bool S, class NList, base_t Base>
654 class Mult<SBigInt<S,NList,Base>,SInt<0> > {
655 public:
656  typedef SInt<0> Result;
657 };
658 
659 template<bool S, class NList, base_t Base, int_t N>
660 class Mult<SInt<N>,SBigInt<S,NList,Base> > {
661 public:
662  typedef typename Mult<SBigInt<S,NList,Base>,SInt<N> >::Result Result;
663 };
664 
666 
667 template<class C>
668 struct SelectUList;
669 
670 template<>
671 struct SelectUList<SInt<0> > {
672  typedef Loki::NullType Result;
673 };
674 
675 template<bool S, class NList, base_t Base>
676 struct SelectUList<SBigInt<S,NList,Base> > {
677  typedef NList Result;
678 };
679 
680 
681 template<class NList1, class NList2, base_t Base, int_t I,
682 unsigned int NList1Len, int_t V1, int_t V2>
683 class __Div;
684 
685 template<class H, class T, class NList2, base_t Base, int_t I,
686 unsigned int NList1Len, int_t V1, int_t V2>
687 class __Div<Loki::Typelist<H,T>,NList2,Base,I,NList1Len,V1,V2> {
688  typedef __Div<T,NList2,Base,I-1,NList1Len-1,V1,V2> Next;
689  typedef Loki::Typelist<H,typename Next::UList> NList1;
690  typedef typename Loki::TL::Next<NList1,NList1Len-I-2>::Result UT;
691  static const int_t U0 = Loki::TL::TypeAtNonStrict<UT,2,SInt<0> >::Result::value;
692  static const int_t U1 = Loki::TL::TypeAtNonStrict<UT,1,SInt<0> >::Result::value;
693  static const int_t U2 = Loki::TL::TypeAtNonStrict<UT,0,SInt<0> >::Result::value;
694 // static const int_t U0 = Loki::TL::TypeAtNonStrict<NList1,NList1Len-I,SInt<0> >::Result::value;
695 // static const int_t U1 = Loki::TL::TypeAtNonStrict<NList1,NList1Len-I-1,SInt<0> >::Result::value;
696 // static const int_t U2 = Loki::TL::TypeAtNonStrict<NList1,NList1Len-I-2,SInt<0> >::Result::value;
697  static const int_t U = U0*Base+U1;
698  static const uint_t Q = U/V1; // trial quotient
699  static const uint_t R = U%V1; // trial reminder
700  // Test trial Q
701  static const uint_t Q1 = ((Q==Base) || (Q*V2>R*Base+U2)) ? Q-1 : Q;
702  static const uint_t R1 = (Q1<Q) ? R+V1 : R;
703  // Repeat, if (R1<Base)
704  static const int_t Q2 = ((R1<Base) && ((Q1==Base) || (Q1*V2>R1*Base+U2))) ? Q1-1 : Q1;
705  typedef SBigInt<true,NList1,Base> BI1;
706  typedef SBigInt<true,NList2,Base> BI2;
707  //typedef typename __SwitchToBigInt<Q2>::Result Q2T;
708  //typedef typename Sub<BI1,typename Mult<BI2,Q2T>::Result>::Result Dif;
709  typedef typename Sub<BI1,typename Mult<BI2,SInt<Q2> >::Result>::Result Dif;
710 public:
711 //typedef typename Loki::Print<T1>::Result DBG;
712 //typedef typename Loki::Print<SInt<Q> >::Result DBG;
713  typedef Loki::Typelist<SInt<Q2>,typename Next::DivList> DivList;
714  typedef typename SelectUList<Dif>::Result UList;
715 };
716 
717 template<class H, class T, class NList2, base_t Base,
718 unsigned int NList1Len, int_t V1, int_t V2>
719 class __Div<Loki::Typelist<H,T>,NList2,Base,0,NList1Len,V1,V2> {
720 public:
721  typedef Loki::NullType DivList;
722  typedef Loki::Typelist<H,T> UList;
723 };
724 
725 
726 
727 template<class B1, class B2>
728 class BigDiv;
729 
730 
731 template<class B1, class B2, int_t L1, int_t L2, char C>
732 struct DivSelect;
733 
734 template<class B1, class B2, int_t L1, int_t L2>
735 struct DivSelect<B1,B2,L1,L2,1> {
736  typedef typename Simplify<B1>::Result BS1;
737  typedef typename Simplify<B2>::Result BS2;
738  typedef BigDiv<BS1,BS2> T;
739 // typedef BigDiv<B1,B2> T;
740  typedef typename T::DivResult DivResult;
741  typedef typename T::ModResult ModResult;
742 };
743 
744 template<class B1, class B2, int_t L1, int_t L2>
745 struct DivSelect<B1,B2,L1,L2,-1> {
746  typedef SInt<0> DivResult;
747  typedef B1 ModResult; //<<< TODO: modify for negative B1
748 };
749 
750 template<class B1, class B2, int_t L1, int_t L2>
751 struct DivSelect<B1,B2,L1,L2,0> {
752  typedef SInt<1> DivResult;
753  typedef SInt<0> ModResult;
754 };
755 
756 template<class B1, class B2, int_t L>
757 struct DivSelect<B1,B2,2,L,1> {
758  typedef SInt<Evaluate2Int<B1,int_t>::value> I1;
759  typedef SInt<Evaluate2Int<B2,int_t>::value> I2;
760  typedef Div<I1,I2> T;
761  typedef typename T::DivResult DivResult;
762  typedef typename T::ModResult ModResult;
763 };
764 
765 template<class B1, class B2>
766 struct DivSelect<B1,B2,2,1,1> {
767  typedef SInt<Evaluate2Int<B1,int_t>::value> I1;
768  typedef SInt<Evaluate2Int<B2,int_t>::value> I2;
769  typedef Div<I1,I2> T;
770  typedef typename T::DivResult DivResult;
771  typedef typename T::ModResult ModResult;
772 };
773 
774 template<class B1, class B2, int_t L>
775 struct DivSelect<B1,B2,L,1,1> {
776  typedef SInt<Evaluate2Int<B2,int_t>::value> I2;
777  typedef Div<B1,I2> T;
778  typedef typename T::DivResult DivResult;
779  typedef typename T::ModResult ModResult;
780 };
781 
782 
783 template<bool S1, class NList1, bool S2, class NList2, base_t Base>
784 class BigDiv<SBigInt<S1,NList1,Base>,SBigInt<S2,NList2,Base> > {
785 public:
786  typedef SBigInt<S1,NList1,Base> BI1;
787  typedef SBigInt<S2,NList2,Base> BI2;
788  static const unsigned L1 = Loki::TL::Length<NList1>::value;
789  static const unsigned L2 = Loki::TL::Length<NList2>::value;
790 //typedef typename Loki::TL::Print<SInt<L2> >::Result A;
791 
792  // Normalization
793  static const int_t D = Base/(Loki::TL::TypeAt<NList2,L2-1>::Result::value+1);
794  typedef typename Mult<BI1,SInt<D> >::Result U;
795  static const unsigned int ULen = Loki::TL::Length<typename U::Num>::value;
796  typedef typename Loki::Select<(ULen==L1),
797  typename Loki::TL::Append<typename U::Num,SInt<0> >::Result,
798  typename U::Num>::Result UList;
799  typedef typename Mult<BI2,SInt<D> >::Result V;
800 
801  // Loop
802  static const unsigned int UListLen = (ULen==L1) ? ULen+1 : ULen;
803  typedef typename V::Num VList;
804  static const unsigned int VLen = Loki::TL::Length<VList>::value;
805  static const int_t V1 = Loki::TL::TypeAt<VList,VLen-1>::Result::value;
806  static const int_t V2 = Loki::TL::TypeAt<VList,VLen-2>::Result::value;
807  typedef __Div<UList,VList,Base,L1-L2+1,UListLen,V1,V2> Loop;
808  //typedef SInt<Evaluate2Int<BI2,int_t>::value> I2;
809 
810 /* typedef typename Div<SBigInt<true,
811  typename Loki::Range<NList1,0,L2-1>::Result,Base>,SInt<D> >::DivResult ModResult;*/
812  typedef SBigInt<true,typename Loop::UList,Base> ModT;
813  typedef typename Div<ModT,SInt<D> >::DivResult ModResult;
814 
815  typedef SBigInt<(S1==S2),typename Loop::DivList,Base> DivResult;
816 // typedef SBigInt<true,typename Loop::ModList,Base> ModResult;
817 };
818 
819 template<class List, class N, base_t Base>
820 struct __DivN;
821 
822 template<class H, class T, int_t N, base_t Base>
823 struct __DivN<Loki::Typelist<H,T>,SInt<N>,Base> {
824  typedef __DivN<T,SInt<N>,Base> Next;
825  static const int_t AN = (N>0) ? N : -N;
826  static const int_t B = Next::Q*Base + H::value;
827  static const int_t R = B/AN;
828  static const int_t Q = B%AN;
829  typedef Loki::Typelist<SInt<R>,typename Next::Result> Result;
830 };
831 
832 template<int_t N, base_t Base>
833 struct __DivN<Loki::NullType,SInt<N>,Base> {
834  static const int_t Q = 0;
835  typedef Loki::NullType Result;
836 };
837 
839 
840 template<bool S1, class NList1, bool S2, class NList2, base_t Base>
841 class Div<SBigInt<S1,NList1,Base>,SBigInt<S2,NList2,Base> >
842 {
843  static const int_t L1 = Loki::TL::Length<NList1>::value;
844  static const int_t L2 = Loki::TL::Length<NList2>::value;
845  static const char C = NL::Compare<NList1,NList2>::value;
846 
847  typedef DivSelect<SBigInt<S1,NList1,Base>,SBigInt<S2,NList2,Base>,L1,L2,C> T;
848 public:
849  typedef typename Simplify<typename T::DivResult>::Result DivResult;
850  typedef typename Simplify<typename T::ModResult>::Result ModResult;
851 // typedef typename T::DivResult DivResult;
852 // typedef typename T::ModResult ModResult;
853 };
854 
855 
856 template<bool S1, bool S2, class NList2, base_t Base>
857 class Div<SBigInt<S1,Loki::NullType,Base>,SBigInt<S2,NList2,Base> > {
858 public:
859  typedef SInt<0> ModResult;
860  typedef SInt<0> DivResult;
861 };
862 
863 template<bool S1, class NList1, bool S2, base_t Base>
864 class Div<SBigInt<S1,NList1,Base>,SBigInt<S2,Loki::NullType,Base> > {}; // error, division by zero
865 
867 
868 template<bool S, class H, class T, base_t Base, int_t N>
869 class Div<SBigInt<S,Loki::Typelist<H,T>,Base>,SInt<N> > {
870  typedef __DivN<Loki::Typelist<H,T>,typename Abs<SInt<N> >::Result,Base> DivLoop;
871  typedef SBigInt<(S==(N>0)),typename DivLoop::Result,Base> BI;
872 public:
873  typedef typename Simplify<BI>::Result DivResult;
874  typedef SInt<DivLoop::Q> ModResult;
875 };
876 
877 template<bool S, class H, class T, base_t Base>
878 class Div<SBigInt<S,Loki::Typelist<H,T>,Base>,SInt<1> > {
879 public:
880  typedef SBigInt<S,Loki::Typelist<H,T>,Base> DivResult;
881  typedef SInt<0> ModResult;
882 };
883 
884 template<bool S, class H, class T, base_t Base>
885 class Div<SBigInt<S,Loki::Typelist<H,T>,Base>,SInt<0> > {}; // error, division by zero
886 
887 template<bool S, class H, class T, base_t Base>
888 class Div<SInt<0>, SBigInt<S,Loki::Typelist<H,T>,Base> > {
889 public:
890  typedef SInt<0> DivResult;
891  typedef SInt<0> ModResult;
892 };
893 
894 template<bool S, base_t Base, int_t N>
895 class Div<SBigInt<S,Loki::NullType,Base>,SInt<N> > {
896 public:
897  typedef SInt<0> DivResult;
898  typedef SInt<0> ModResult;
899 };
900 
901 template<bool S, base_t Base, int_t N>
902 class Div<SInt<N>, SBigInt<S,Loki::NullType,Base> > {}; // error
903 
904 
905 template<bool S, class NList, base_t Base, int_t N>
906 class Div<SInt<N>,SBigInt<S,NList,Base> > {
907 public:
908  typedef typename Div<SBigInt<S,NList,Base>,SInt<N> >::Result Result;
909 };
910 
912 /*
913 template<bool S1, class NList1, bool S2, class NList2, base_t Base>
914 class Mod<SBigInt<S1,NList1,Base>,SBigInt<S2,NList2,Base> > {
915 
916 };
917 
918 template<bool S, class NList, base_t Base, int_t N>
919 class Mod<SBigInt<S,NList,Base>,SInt<N> > {
920 
921 };
922 
923 template<bool S, class NList, base_t Base, int_t N>
924 class Mod<SInt<N>,SBigInt<S,NList,Base> > {
925 public:
926  typedef typename Mod<SBigInt<S,NList,Base>,SInt<N> >::Result Result;
927 };
928 */
929 
930 // Returns number of digits in N in the Base-system (Base=2 for binary)
931 template<unsigned N, unsigned Base>
932 struct NDigits {
933  static const unsigned value = NDigits<N/Base, Base>::value + 1;
934 };
935 
936 template<unsigned Base>
937 struct NDigits<0, Base> {
938  static const unsigned value = 0;
939 };
940 
942 
943 template<class B, base_t NewBase>
944 class Translate;
945 
946 template<bool S, class H, class T, base_t Base, base_t NewBase>
947 class Translate<SBigInt<S,Loki::Typelist<H,T>,Base>,NewBase> {
948  typedef SBigInt<S,T,Base> BI;
949  typedef typename Translate<BI,NewBase>::Result Next;
950 public:
951  typedef typename Add<typename Mult<Next,SInt<Base> >::Result,H>::Result Result;
952 };
953 
954 template<bool S, base_t Base, base_t NewBase>
955 class Translate<SBigInt<S,Loki::NullType,Base>,NewBase> {
956 public:
957  typedef SBigInt<S,Loki::NullType,NewBase> Result;
958 };
959 
961 
962 template<class NList, base_t Base>
963 struct DoubleBaseLoop;
964 
965 template<class H1, class H2, class T, base_t Base>
966 struct DoubleBaseLoop<Loki::Typelist<H1,Loki::Typelist<H2,T> >,Base> {
967  static const int_t H = H2::value*Base + H1::value;
968  typedef Loki::Typelist<SInt<H>,typename DoubleBaseLoop<T,Base>::Result> Result;
969 };
970 
971 template<class H1, base_t Base>
972 struct DoubleBaseLoop<Loki::Typelist<H1,Loki::NullType>,Base> {
973  typedef Loki::Typelist<H1,Loki::NullType> Result;
974 };
975 
976 template<base_t Base>
977 struct DoubleBaseLoop<Loki::NullType,Base> {
978  typedef Loki::NullType Result;
979 };
980 
981 
982 template<class BI>
983 struct DoubleBase;
984 
985 template<bool S, class N, base_t Base>
986 struct DoubleBase<SBigInt<S,N,Base> > {
987  typedef typename DoubleBaseLoop<N,Base>::Result List;
988  typedef SBigInt<S,List,Base*Base> Result;
989 };
990 
991 template<int_t N>
992 struct DoubleBase<SInt<N> > {
993  typedef SInt<N> Result;
994 };
995 
997 
998 template<class H, base_t Base,
999 bool C = (Abs<H>::Result::value < Base)>
1000 struct CheckStep;
1001 
1002 template<class H, base_t Base>
1003 struct CheckStep<H,Base,true> {
1004  typedef H Result;
1005 };
1006 
1007 template<class H, base_t Base>
1008 struct CheckStep<H,Base,false> { }; // error
1009 
1010 
1011 template<class T>
1012 struct Check;
1013 
1014 template<bool S, class H, class T, base_t Base>
1015 struct Check<SBigInt<S,Loki::Typelist<H,T>,Base> >
1016 {
1017  typedef Loki::Typelist<typename CheckStep<H,Base>::Result,
1018  typename Check<SBigInt<S,T,Base> >::Result> Result;
1019 };
1020 
1021 template<bool S, base_t Base>
1022 struct Check<SBigInt<S,Loki::NullType,Base> >
1023 {
1024  typedef Loki::NullType Result;
1025 };
1026 
1027 template<int_t N>
1028 struct Check<SInt<N> > : public CheckStep<SInt<N>,DefaultBase> {};
1029 
1030 #endif
Generated on Mon Feb 10 2014 for Generative Fast Fourier Transforms (GFFT) by DoxyGen 1.8.3.1