plll  1.0
arithmetic-nint.hpp
Go to the documentation of this file.
1 /*
2  Copyright (c) 2011-2014 University of Zurich
3 
4  Permission is hereby granted, free of charge, to any person obtaining a copy
5  of this software and associated documentation files (the "Software"), to deal
6  in the Software without restriction, including without limitation the rights
7  to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
8  copies of the Software, and to permit persons to whom the Software is
9  furnished to do so, subject to the following conditions:
10 
11  The above copyright notice and this permission notice shall be included in
12  all copies or substantial portions of the Software.
13 
14  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
15  IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
16  FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
17  AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
18  LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
19  OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
20  THE SOFTWARE.
21 */
22 
23 #ifndef PLLL_INCLUDE_GUARD__NINT_WRAPPER
24 #define PLLL_INCLUDE_GUARD__NINT_WRAPPER
25 
37 #include <sstream>
38 #include <limits>
39 #include <cmath>
40 #include <plll/arithmetic.hpp>
41 
42 namespace plll
43 {
44  namespace arithmetic
45  {
46  template<typename Type>
47  // Type should be long, long long, int, ....
48  class NInt;
49  // NInt stands for "Native Integers" (i.e. something native to the CPU/FPU)
50  }
51 }
52 
53 namespace plll
54 {
55  namespace arithmetic
56  {
64  template<class IType>
65  class NIntContext
66  // Emulates IntegerContext
67  {
68  public:
72  typedef arithmetic::NInt<IType> Integer;
76  typedef arithmetic::NInt<IType> Type;
77 
81  enum { is_cputype = true, is_realtype = false, is_inttype = true, is_exact = true,
82  is_modulo = true, has_infinity = false, has_uniform_rng = true };
83 
89  class UniformRNG
90  {
91  private:
92  RandomNumberGenerator & d_rng;
93 
94  public:
99  UniformRNG(RandomNumberGenerator & rng) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE
100  : d_rng(rng)
101  {
102  }
103 
110  inline void random(NInt<IType> & res, const NInt<IType> & bound);
111 
119  inline NInt<IType> random(const NInt<IType> & bound, const NIntContext<IType> & ic)
120  {
121  NInt<IType> res;
122  random(res, bound);
123  return res;
124  }
125 
132  inline void randomBits(NInt<IType> & res, unsigned long bits);
133 
141  inline NInt<IType> randomBits(unsigned long bits, const NIntContext<IType> & ic)
142  {
143  NInt<IType> res;
144  randomBits(res, bits);
145  return res;
146  }
147 
154  inline void randomLen(NInt<IType> & res, unsigned long bits);
155 
163  inline NInt<IType> randomLen(unsigned long bits, const NIntContext<IType> & ic)
164  {
165  NInt<IType> res;
166  randomLen(res, bits);
167  return res;
168  }
169  };
170  };
171 
172  namespace traits
173  {
174  template<typename Type>
175  struct type_traits<NInt<Type> >
176  {
177  enum
178  {
179  is_number = true,
180  is_cputype = true,
181  is_realtype = false,
182  is_inttype = true,
183  is_string = false,
184  is_cpp_string = false,
185  is_c_string = false,
186  is_exact = true,
187  has_uniform_rng = true,
188  has_context = true,
189  is_native = false,
190  is_modulo = true,
191  has_infinity = false,
192  is_variable_precision = false,
193  has_squareroot = false,
194  has_full_power = false,
195  has_special_fns = false,
196  has_huge_exponent = false,
197  has_constants = false,
198  has_trigonometric = false
199  };
200 
201  typedef NIntContext<Type> Context;
202  typedef NInt<typename type_traits<Type>::PromoteType> PromoteType;
203  typedef NInt<Type> ConstReferenceType;
204  };
205  }
206 
216  template<typename Type>
217  inline bool operator == (const NInt<Type> & a, const NInt<Type> & b) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE;
224  template<typename Type>
225  inline bool operator != (const NInt<Type> & a, const NInt<Type> & b) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE;
232  template<typename Type>
233  inline bool operator <= (const NInt<Type> & a, const NInt<Type> & b) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE;
240  template<typename Type>
241  inline bool operator >= (const NInt<Type> & a, const NInt<Type> & b) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE;
248  template<typename Type>
249  inline bool operator < (const NInt<Type> & a, const NInt<Type> & b) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE;
256  template<typename Type>
257  inline bool operator > (const NInt<Type> & a, const NInt<Type> & b) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE;
259 
268  template<typename Type>
269  inline NInt<Type> operator - (const NInt<Type> & a) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE;
277  template<typename Type>
278  inline NInt<Type> operator + (const NInt<Type> & a, const NInt<Type> & b) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE;
286  template<typename Type>
287  inline NInt<Type> operator - (const NInt<Type> & a, const NInt<Type> & b) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE;
295  template<typename Type>
296  inline NInt<Type> operator * (const NInt<Type> & a, const NInt<Type> & b) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE;
304  template<typename Type>
305  inline NInt<Type> operator / (const NInt<Type> & a, const NInt<Type> & b) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE;
313  template<typename Type>
314  inline NInt<Type> operator % (const NInt<Type> & a, const NInt<Type> & b) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE;
325  template<typename Type>
326  inline NInt<Type> operator << (const NInt<Type> & a, long b) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE;
338  template<typename Type>
339  inline NInt<Type> operator >> (const NInt<Type> & a, long b) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE;
350  template<typename Type>
351  inline NInt<Type> operator << (const NInt<Type> & a, const NInt<Type> & b) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE;
363  template<typename Type>
364  inline NInt<Type> operator >> (const NInt<Type> & a, const NInt<Type> & b) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE;
371  template<typename Type>
372  inline NInt<Type> operator ++ (NInt<Type> & cur, int) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE;
379  template<typename Type>
380  inline NInt<Type> operator -- (NInt<Type> & cur, int) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE;
387  template<typename Type>
388  inline NInt<Type> & operator ++ (NInt<Type> & cur) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE;
395  template<typename Type>
396  inline NInt<Type> & operator -- (NInt<Type> & cur) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE;
398 
409  template<typename Type>
410  inline NInt<Type> & operator -= (NInt<Type> & cur, const NInt<Type> & i) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE;
418  template<typename Type>
419  inline NInt<Type> & operator += (NInt<Type> & cur, const NInt<Type> & i) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE;
427  template<typename Type>
428  inline NInt<Type> & operator *= (NInt<Type> & cur, const NInt<Type> & i) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE;
436  template<typename Type>
437  inline NInt<Type> & operator /= (NInt<Type> & cur, const NInt<Type> & i) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE;
446  template<typename Type>
447  inline NInt<Type> & operator %= (NInt<Type> & cur, const NInt<Type> & i) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE;
458  template<typename Type>
459  inline NInt<Type> & operator <<= (NInt<Type> & cur, long i) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE;
470  template<typename Type>
471  inline NInt<Type> & operator >>= (NInt<Type> & cur, long i) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE;
482  template<typename Type>
483  inline NInt<Type> & operator <<= (NInt<Type> & cur, const NInt<Type> & i) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE;
494  template<typename Type>
495  inline NInt<Type> & operator >>= (NInt<Type> & cur, const NInt<Type> & i) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE;
497 
507  template<typename Type>
508  inline bool isZero(const NInt<Type> &) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE;
509 
516  template<typename Type>
517  inline bool isOne(const NInt<Type> &) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE;
518 
525  template<typename Type>
526  inline bool isPMOne(const NInt<Type> &) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE;
527 
534  template<typename Type>
535  inline bool isPMTwo(const NInt<Type> &) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE;
536 
543  template<typename Type>
544  inline bool isPositive(const NInt<Type> &) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE;
545 
552  template<typename Type>
553  inline bool isNonNegative(const NInt<Type> &) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE;
554 
561  template<typename Type>
562  inline bool isNegative(const NInt<Type> &) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE;
563 
570  template<typename Type>
571  inline bool isNonPositive(const NInt<Type> &) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE;
573 
584  template<typename Type>
585  inline void add(NInt<Type> & r, const NInt<Type> & a, const NInt<Type> & b) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE;
593  template<typename Type>
594  inline void sub(NInt<Type> & r, const NInt<Type> & a, const NInt<Type> & b) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE;
602  template<typename Type>
603  inline void addmul(NInt<Type> & r, const NInt<Type> & a, const NInt<Type> & b) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE;
611  template<typename Type>
612  inline void submul(NInt<Type> & r, const NInt<Type> & a, const NInt<Type> & b) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE;
620  template<typename Type>
621  inline void mul(NInt<Type> & r, const NInt<Type> & a, const NInt<Type> & b) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE;
629  template<typename Type>
630  inline void div(NInt<Type> & r, const NInt<Type> & a, const NInt<Type> & b) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE;
640  template<typename Type>
641  inline void divmod(NInt<Type> & q, NInt<Type> & r, const NInt<Type> & a, const NInt<Type> & b) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE;
649  template<typename Type>
650  inline void mod(NInt<Type> & r, const NInt<Type> & a, const NInt<Type> & b) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE;
658  template<typename Type>
659  inline void shl(NInt<Type> & r, const NInt<Type> & a, long b) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE;
667  template<typename Type>
668  inline void shr(NInt<Type> & r, const NInt<Type> & a, long b) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE;
676  template<typename Type>
677  inline void shl(NInt<Type> & r, const NInt<Type> & a, const NInt<Type> & b) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE;
685  template<typename Type>
686  inline void shr(NInt<Type> & r, const NInt<Type> & a, const NInt<Type> & b) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE;
694  template<typename Type>
695  inline void increment(NInt<Type> & r, const NInt<Type> & a) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE;
702  template<typename Type>
703  inline void decrement(NInt<Type> & r, const NInt<Type> & a) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE;
710  template<typename Type>
711  inline void neg(NInt<Type> & r, const NInt<Type> & a) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE;
718  template<typename Type>
719  inline void abs(NInt<Type> & r, const NInt<Type> & a) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE;
726  template<typename Type>
727  inline void square(NInt<Type> & r, const NInt<Type> & a) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE;
729 
738  template<typename Type>
739  inline NInt<Type> abs(const NInt<Type> & i) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE;
745  template<typename Type>
746  inline NInt<Type> square(const NInt<Type> & i) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE;
748 
755  template<typename Type>
756  std::ostream & operator << (std::ostream &, const NInt<Type> &);
757 
761  template<typename Type>
762  std::istream & operator >> (std::istream &, NInt<Type> &);
764 
771  template<typename Type>
772  inline void setZero(NInt<Type> &) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE;
776  template<typename Type>
777  inline void setOne(NInt<Type> &) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE;
779 
791  template<typename Type>
792  inline int compare(const NInt<Type> &, const NInt<Type> &) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE;
801  template<typename Type>
802  inline int compareAbsValues(const NInt<Type> &, const NInt<Type> &) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE;
804 
814  template<typename Type>
815  inline int sign(const NInt<Type> &) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE;
821  template<typename Type>
822  inline void makeAbs(NInt<Type> & a) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE;
824 
832  template<typename Type>
833  inline int bit(const NInt<Type> & x, long n) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE;
841  template<typename Type>
842  inline void setbit(NInt<Type> & x, long n, bool value = true) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE;
844 
854  template<typename Type>
855  inline NInt<Type> power(const NInt<Type> & a, long b) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE;
863  template<typename Type>
864  inline void power(NInt<Type> & r, const NInt<Type> & a, long b) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE;
871  template<typename Type>
872  inline NInt<Type> power(const NInt<Type> & a, const NInt<Type> & b) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE;
880  template<typename Type>
881  inline void power(NInt<Type> & r, const NInt<Type> & a, const NInt<Type> & b) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE;
883 
893  template<typename Type>
894  inline void sqrtCeil(NInt<Type> & r, const NInt<Type> & a) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE;
901  template<typename Type>
902  inline NInt<Type> sqrtCeil(const NInt<Type> & a) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE;
909  template<typename Type>
910  inline void sqrtFloor(NInt<Type> & r, const NInt<Type> & a) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE;
917  template<typename Type>
918  inline NInt<Type> sqrtFloor(const NInt<Type> & a) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE;
926  template<typename Type>
927  long ceilOfLog2(const NInt<Type> & x) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE; // Returns ceil(log_2(|x|)).
935  template<typename Type>
936  long floorOfLog2(const NInt<Type> & x) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE; // Returns floor(log_2(|x|)).
943  template<typename Type>
944  long approxLog2(const NInt<Type> & x) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE; // Returns ~log_2(|x|).
952  template<typename Type>
953  inline long bitLength(const NInt<Type> & x) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE; // Returns n such that 2^{n-1} <= |x| < 2^n
962  template<typename Type>
963  void floorDiv(NInt<Type> & r, const NInt<Type> & a, const NInt<Type> & b) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE; // Computes r = floor(a/b), where b \neq 0.
972  template<typename Type>
973  NInt<Type> floorDiv(const NInt<Type> & a, const NInt<Type> & b) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE; // Computes r = floor(a/b), where b \neq 0.
982  template<typename Type>
983  void ceilDiv(NInt<Type> & r, const NInt<Type> & a, const NInt<Type> & b) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE; // Computes r = ceil(a/b), where b \neq 0.
992  template<typename Type>
993  NInt<Type> ceilDiv(const NInt<Type> & a, const NInt<Type> & b) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE; // Computes r = ceil(a/b), where b \neq 0.
1003  template<typename Type>
1004  void roundDiv(NInt<Type> & r, const NInt<Type> & a, const NInt<Type> & b) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE; // Computes r = round(a/b), where b \neq 0.
1014  template<typename Type>
1015  NInt<Type> roundDiv(const NInt<Type> & a, const NInt<Type> & b) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE; // Computes r = round(a/b), where b \neq 0.
1017 
1032  template<typename Type>
1033  inline void euclideanDivision(NInt<Type> & q, NInt<Type> & r, const NInt<Type> & a, const NInt<Type> & b) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE;
1034 
1045  template<typename Type>
1046  inline void euclideanDivisionPos(NInt<Type> & q, NInt<Type> & r, const NInt<Type> & a, const NInt<Type> & b) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE;
1047 
1056  template<typename Type>
1057  inline void GCD(NInt<Type> & r, const NInt<Type> & x, const NInt<Type> & y) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE;
1066  template<typename Type>
1067  inline NInt<Type> GCD(const NInt<Type> & x, const NInt<Type> & y) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE;
1068 
1082  template<typename Type>
1083  inline void XGCD(NInt<Type> & r, NInt<Type> & a, NInt<Type> & b, const NInt<Type> & x, const NInt<Type> & y) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE;
1084 
1093  template<typename Type>
1094  inline void LCM(NInt<Type> & r, const NInt<Type> & x, const NInt<Type> & y) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE;
1103  template<typename Type>
1104  inline NInt<Type> LCM(const NInt<Type> & x, const NInt<Type> & y) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE;
1106 
1113  template<typename Type>
1114  inline void swap(NInt<Type> &, NInt<Type> &) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE;
1116 
1122  template<typename Type>
1123  class NInt
1124  {
1125 #ifdef PLLL_INTERNAL_NO_TEMPLATE_FRIENDS
1126  public:
1127 #else
1128  private:
1129  friend class NIntContext<Type>;
1130 
1131  template<class X, class Y>
1132  friend class implementation::conversion_impl;
1133 
1134  friend class implementation::nativeconversion_impl<NInt<Type> >;
1135 #endif
1136 
1137  Type d_value;
1138 
1139  inline NInt(bool, Type v) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE
1140  : d_value(v)
1141  {
1142  }
1143 
1144  inline void assignType(Type v) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE
1145  {
1146  d_value = v;
1147  }
1148 
1149  public:
1153  typedef NIntContext<Type> Context;
1154 
1158  inline NInt() PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE
1159  : d_value(0)
1160  {
1161  }
1162 
1168  inline NInt(const NIntContext<Type> & c) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE
1169  : d_value(0)
1170  {
1171  }
1172 
1178  inline NInt(const NInt & i) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE
1179  : d_value(i.d_value)
1180  {
1181  }
1182 
1188  template<typename T>
1189  inline NInt(const NInt<T> & i) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE
1190  : d_value(i.d_value)
1191  {
1192  }
1193 
1200  inline NInt(const NInt & i, const NIntContext<Type> & ic) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE
1201  : d_value(i.d_value)
1202  {
1203  }
1204 
1211  template<typename T>
1212  inline NInt(const NInt<T> & i, const NIntContext<Type> & ic) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE
1213  : d_value(i.d_value)
1214  {
1215  }
1216 
1222  static inline void setContext(const NIntContext<Type> & c) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE
1223  {
1224  }
1225 
1231  inline explicit NInt(double d) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE
1232  : d_value(d)
1233  {
1234  }
1235 
1241  inline explicit NInt(long double d) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE
1242  : d_value(d)
1243  {
1244  }
1245 
1251  inline explicit NInt(long i) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE
1252  : d_value(i)
1253  {
1254  }
1255 
1261  inline explicit NInt(unsigned long i) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE
1262  : d_value(i)
1263  {
1264  }
1265 
1271  inline explicit NInt(const Integer & i)
1272  : d_value(convert<Type>(i))
1273  {
1274  }
1275 
1281  inline NInt & operator = (const NInt & r) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE
1282  {
1283  d_value = r.d_value;
1284  return *this;
1285  }
1286 
1287 #ifndef PLLL_INTERNAL_NO_TEMPLATE_FRIENDS
1288  friend NInt<Type> operator - <>(const NInt<Type> &) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE;
1289  friend NInt<Type> operator + <>(const NInt<Type> &, const NInt<Type> & b) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE;
1290  friend NInt<Type> operator - <>(const NInt<Type> &, const NInt<Type> & b) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE;
1291  friend NInt<Type> operator * <>(const NInt<Type> &, const NInt<Type> & b) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE;
1292  friend NInt<Type> operator / <>(const NInt<Type> &, const NInt<Type> & b) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE;
1293  friend NInt<Type> operator % <>(const NInt<Type> &, const NInt<Type> & b) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE;
1294  friend NInt<Type> operator << <>(const NInt<Type> & a, long b) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE;
1295  friend NInt<Type> operator >> <>(const NInt<Type> & a, long b) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE;
1296  friend NInt<Type> operator << <>(const NInt<Type> & a, const NInt<Type> & b) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE;
1297  friend NInt<Type> operator >> <>(const NInt<Type> & a, const NInt<Type> & b) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE;
1298  friend NInt<Type> & operator -= <>(NInt<Type> &, const NInt<Type> & i) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE;
1299  friend NInt<Type> & operator += <>(NInt<Type> &, const NInt<Type> & i) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE;
1300  friend NInt<Type> & operator *= <>(NInt<Type> &, const NInt<Type> & i) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE;
1301  friend NInt<Type> & operator /= <>(NInt<Type> &, const NInt<Type> & i) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE;
1302  friend NInt<Type> & operator %= <>(NInt<Type> &, const NInt<Type> & i) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE;
1303  friend NInt<Type> operator ++ <>(NInt<Type> &, int) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE;
1304  friend NInt<Type> operator -- <>(NInt<Type> &, int) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE;
1305  friend NInt<Type> & operator ++ <>(NInt<Type> &) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE;
1306  friend NInt<Type> & operator -- <>(NInt<Type> &) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE;
1307  friend bool operator == <>(const NInt<Type> & a, const NInt<Type> & b) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE;
1308  friend bool operator != <>(const NInt<Type> & a, const NInt<Type> & b) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE;
1309  friend bool operator <= <>(const NInt<Type> & a, const NInt<Type> & b) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE;
1310  friend bool operator >= <>(const NInt<Type> & a, const NInt<Type> & b) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE;
1311  friend bool operator < <>(const NInt<Type> & a, const NInt<Type> & b) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE;
1312  friend bool operator > <>(const NInt<Type> & a, const NInt<Type> & b) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE;
1313  friend bool isZero<>(const NInt<Type> & r) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE;
1314  friend bool isOne<>(const NInt<Type> & r) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE;
1315  friend bool isPMOne<>(const NInt<Type> & r) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE;
1316  friend bool isPMTwo<>(const NInt<Type> & r) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE;
1317  friend bool isPositive<>(const NInt<Type> & r) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE;
1318  friend bool isNonNegative<>(const NInt<Type> & r) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE;
1319  friend bool isNegative<>(const NInt<Type> & r) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE;
1320  friend bool isNonPositive<>(const NInt<Type> & r) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE;
1321  friend void add<>(NInt<Type> & r, const NInt<Type> & a, const NInt<Type> & b) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE;
1322  friend void sub<>(NInt<Type> & r, const NInt<Type> & a, const NInt<Type> & b) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE;
1323  friend void mul<>(NInt<Type> & r, const NInt<Type> & a, const NInt<Type> & b) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE;
1324  friend void div<>(NInt<Type> & r, const NInt<Type> & a, const NInt<Type> & b) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE;
1325  friend void mod<>(NInt<Type> & r, const NInt<Type> & a, const NInt<Type> & b) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE;
1326  friend void shl<>(NInt<Type> & r, const NInt<Type> & a, long b) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE;
1327  friend void shr<>(NInt<Type> & r, const NInt<Type> & a, long b) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE;
1328  friend void shl<>(NInt<Type> & r, const NInt<Type> & a, const NInt<Type> & b) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE;
1329  friend void shr<>(NInt<Type> & r, const NInt<Type> & a, const NInt<Type> & b) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE;
1330  friend void increment<>(NInt<Type> & r, const NInt<Type> & a) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE;
1331  friend void decrement<>(NInt<Type> & r, const NInt<Type> & a) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE;
1332  friend void neg<>(NInt<Type> & r, const NInt<Type> & a) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE;
1333  friend void abs<>(NInt<Type> & r, const NInt<Type> & a) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE;
1334  friend NInt<Type> abs<>(const NInt<Type> & i) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE;
1335  friend void makeAbs<>(NInt<Type> & a) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE;
1336  friend std::ostream & operator << <>(std::ostream & s, const NInt<Type> & r);
1337  // Output to stream
1338  friend std::istream & operator >> <>(std::istream & s, NInt<Type> & r);
1339  // Input from stream
1340  friend void setZero<>(NInt<Type> & r) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE;
1341  // Set to zero
1342  friend void setOne<>(NInt<Type> & r) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE;
1343  // Set to one
1344  friend int compare<>(const NInt<Type> & a, const NInt<Type> & b) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE;
1345  // Tests whether the first real is < (-1), = (0) or > (1) than the second.
1346  friend int compareAbsValues<>(const NInt<Type> & a, const NInt<Type> & b) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE;
1347  // Tests whether the absolute value of the first NInt<Type> is < (-1), = (0) or > (1) than the
1348  // absolute value of the second NInt.
1349  friend int sign<>(const NInt<Type> & r) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE;
1350  // Returns the sign (i.e. -1, 0, 1).
1351  friend int bit<>(const NInt<Type> &, long n) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE;
1352  friend NInt<Type> square<>(const NInt<Type> & i) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE;
1353  friend void square<>(NInt<Type> & r, const NInt<Type> & a) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE;
1354  friend NInt<Type> power<>(const NInt<Type> &, long) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE;
1355  friend void power<>(NInt<Type> &, const NInt<Type> &, long) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE;
1356  friend NInt<Type> power<>(const NInt<Type> &, const NInt<Type> &) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE;
1357  friend void power<>(NInt<Type> &, const NInt<Type> &, const NInt<Type> &) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE;
1358  friend void sqrtCeil<>(NInt<Type> &, const NInt<Type> &) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE;
1359  friend void sqrtFloor<>(NInt<Type> &, const NInt<Type> &) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE;
1360  friend long ceilOfLog2<>(const NInt<Type> & x) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE;
1361  friend long floorOfLog2<>(const NInt<Type> & x) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE;
1362  friend long approxLog2<>(const NInt<Type> & x) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE;
1363  friend long bitLength<>(const NInt<Type> & x) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE;
1364  friend void floorDiv<>(NInt<Type> & r, const NInt<Type> & a, const NInt<Type> & b) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE;
1365  friend NInt<Type> floorDiv<>(const NInt<Type> & a, const NInt<Type> & b) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE;
1366  friend void ceilDiv<>(NInt<Type> & r, const NInt<Type> & a, const NInt<Type> & b) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE;
1367  friend NInt<Type> ceilDiv<>(const NInt<Type> & a, const NInt<Type> & b) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE;
1368  friend void roundDiv<>(NInt<Type> & r, const NInt<Type> & a, const NInt<Type> & b) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE;
1369  friend NInt<Type> roundDiv<>(const NInt<Type> & a, const NInt<Type> & b) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE;
1370  friend void euclideanDivision<>(NInt<Type> & q, NInt<Type> & r, const NInt<Type> & a, const NInt<Type> & b) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE;
1371  friend void euclideanDivisionPos<>(NInt<Type> & q, NInt<Type> & r, const NInt<Type> & a, const NInt<Type> & b) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE;
1372  friend void GCD<>(NInt<Type> & r, const NInt<Type> & x, const NInt<Type> & y) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE;
1373  friend NInt<Type> GCD<>(const NInt<Type> & x, const NInt<Type> & y) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE;
1374  friend void XGCD<>(NInt<Type> & r, NInt<Type> & a, NInt<Type> & b, const NInt<Type> & x, const NInt<Type> & y) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE;
1375  friend void LCM<>(NInt<Type> & r, const NInt<Type> & x, const NInt<Type> & y) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE;
1376  friend NInt<Type> LCM<>(const NInt<Type> & x, const NInt<Type> & y) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE;
1377  friend void swap<>(NInt<Type> & a, NInt<Type> & b) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE;
1378 #endif
1379  };
1380 
1381  template<typename Type>
1382  inline NInt<Type> operator - (const NInt<Type> & a) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE
1383  {
1384  return NInt<Type>(true, -a.d_value);
1385  }
1386 
1387  template<typename Type>
1388  inline NInt<Type> operator + (const NInt<Type> & a, const NInt<Type> & b) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE
1389  {
1390  return NInt<Type>(true, a.d_value + b.d_value);
1391  }
1392 
1393  template<typename Type>
1394  inline NInt<Type> operator - (const NInt<Type> & a, const NInt<Type> & b) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE
1395  {
1396  return NInt<Type>(true, a.d_value - b.d_value);
1397  }
1398 
1399  template<typename Type>
1400  inline NInt<Type> operator * (const NInt<Type> & a, const NInt<Type> & b) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE
1401  {
1402  return NInt<Type>(true, a.d_value * b.d_value);
1403  }
1404 
1405  template<typename Type>
1406  inline NInt<Type> operator / (const NInt<Type> & a, const NInt<Type> & b) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE
1407  {
1408  return NInt<Type>(true, a.d_value / b.d_value);
1409  }
1410 
1411  template<typename Type>
1412  inline NInt<Type> operator % (const NInt<Type> & a, const NInt<Type> & b) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE
1413  {
1414  return NInt<Type>(true, a.d_value % b.d_value);
1415  }
1416 
1417  template<typename Type>
1418  inline NInt<Type> & operator -= (NInt<Type> & a, const NInt<Type> & i) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE
1419  {
1420  a.d_value -= i.d_value;
1421  return a;
1422  }
1423 
1424  template<typename Type>
1425  inline NInt<Type> & operator += (NInt<Type> & a, const NInt<Type> & i) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE
1426  {
1427  a.d_value += i.d_value;
1428  return a;
1429  }
1430 
1431  template<typename Type>
1432  inline NInt<Type> & operator *= (NInt<Type> & a, const NInt<Type> & i) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE
1433  {
1434  a.d_value *= i.d_value;
1435  return a;
1436  }
1437 
1438  template<typename Type>
1439  inline NInt<Type> & operator /= (NInt<Type> & a, const NInt<Type> & i) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE
1440  {
1441  a.d_value /= i.d_value;
1442  return a;
1443  }
1444 
1445  template<typename Type>
1446  inline NInt<Type> & operator %= (NInt<Type> & a, const NInt<Type> & i) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE
1447  {
1448  a.d_value %= i.d_value;
1449  return a;
1450  }
1451 
1452  template<typename Type>
1453  inline NInt<Type> & operator <<= (NInt<Type> & a, long r) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE
1454  {
1455  shl(a, a, r);
1456  return a;
1457  }
1458 
1459  template<typename Type>
1460  inline NInt<Type> & operator >>= (NInt<Type> & a, long r) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE
1461  {
1462  shr(a, a, r);
1463  return a;
1464  }
1465 
1466  template<typename Type>
1467  inline NInt<Type> & operator <<= (NInt<Type> & a, const NInt<Type> & r) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE
1468  {
1469  shl(a, a, r);
1470  return a;
1471  }
1472 
1473  template<typename Type>
1474  inline NInt<Type> & operator >>= (NInt<Type> & a, const NInt<Type> & r) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE
1475  {
1476  shr(a, a, r);
1477  return a;
1478  }
1479 
1480  template<typename Type>
1481  inline NInt<Type> operator ++ (NInt<Type> & a, int) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE
1482  {
1483  return NInt<Type>(true, a.d_value++);
1484  }
1485 
1486  template<typename Type>
1487  inline NInt<Type> operator -- (NInt<Type> & a, int) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE
1488  {
1489  return NInt<Type>(true, a.d_value--);
1490  }
1491 
1492  template<typename Type>
1493  inline NInt<Type> & operator ++ (NInt<Type> & a) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE
1494  {
1495  ++a.d_value;
1496  return a;
1497  }
1498 
1499  template<typename Type>
1500  inline NInt<Type> & operator -- (NInt<Type> & a) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE
1501  {
1502  --a.d_value;
1503  return a;
1504  }
1505 
1506  template<typename Type>
1507  inline NInt<Type> operator << (const NInt<Type> & a, long b) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE
1508  {
1509  NInt<Type> r;
1510  shl(r, a, b);
1511  return r;
1512  }
1513 
1514  template<typename Type>
1515  inline NInt<Type> operator >> (const NInt<Type> & a, long b) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE
1516  {
1517  NInt<Type> r;
1518  shr(r, a, b);
1519  return r;
1520  }
1521 
1522  template<typename Type>
1523  inline NInt<Type> operator << (const NInt<Type> & a, const NInt<Type> & b) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE
1524  {
1525  NInt<Type> r;
1526  shl(r, a, b);
1527  return r;
1528  }
1529 
1530  template<typename Type>
1531  inline NInt<Type> operator >> (const NInt<Type> & a, const NInt<Type> & b) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE
1532  {
1533  NInt<Type> r;
1534  shr(r, a, b);
1535  return r;
1536  }
1537 
1538  template<typename Type>
1539  inline bool operator == (const NInt<Type> & a, const NInt<Type> & b) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE
1540  {
1541  return a.d_value == b.d_value;
1542  }
1543 
1544  template<typename Type>
1545  inline bool operator != (const NInt<Type> & a, const NInt<Type> & b) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE
1546  {
1547  return a.d_value != b.d_value;
1548  }
1549 
1550  template<typename Type>
1551  inline bool operator <= (const NInt<Type> & a, const NInt<Type> & b) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE
1552  {
1553  return a.d_value <= b.d_value;
1554  }
1555 
1556  template<typename Type>
1557  inline bool operator >= (const NInt<Type> & a, const NInt<Type> & b) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE
1558  {
1559  return a.d_value >= b.d_value;
1560  }
1561 
1562  template<typename Type>
1563  inline bool operator < (const NInt<Type> & a, const NInt<Type> & b) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE
1564  {
1565  return a.d_value < b.d_value;
1566  }
1567 
1568  template<typename Type>
1569  inline bool operator > (const NInt<Type> & a, const NInt<Type> & b) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE
1570  {
1571  return a.d_value > b.d_value;
1572  }
1573 
1574  template<typename Type>
1575  inline bool isZero(const NInt<Type> & r) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE
1576  // Tests whether the given value is = 0.
1577  {
1578  return r.d_value == (Type)0;
1579  }
1580 
1581  template<typename Type>
1582  inline bool isOne(const NInt<Type> & r) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE
1583  // Tests whether the given value is = 1.
1584  {
1585  return r.d_value == (Type)1;
1586  }
1587 
1588  template<typename Type>
1589  inline bool isPMOne(const NInt<Type> & r) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE
1590  // Tests whether the given value is = +-1.
1591  {
1592  return (r.d_value == (Type)1) || (r.d_value == (Type)(-1));
1593  }
1594 
1595  template<typename Type>
1596  inline bool isPMTwo(const NInt<Type> & r) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE
1597  // Tests whether the given value is = +-2.
1598  {
1599  return (r.d_value == (Type)2) || (r.d_value == (Type)(-2));
1600  }
1601 
1602  template<typename Type>
1603  inline bool isPositive(const NInt<Type> & r) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE
1604  // Tests whether the given value is > 0.
1605  {
1606  return r.d_value > (Type)0;
1607  }
1608 
1609  template<typename Type>
1610  inline bool isNonNegative(const NInt<Type> & r) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE
1611  // Tests whether the given value is >= 0.
1612  {
1613  return r.d_value >= (Type)0;
1614  }
1615 
1616  template<typename Type>
1617  inline bool isNegative(const NInt<Type> & r) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE
1618  // Tests whether the given value is < 0.
1619  {
1620  return r.d_value < (Type)0;
1621  }
1622 
1623  template<typename Type>
1624  inline bool isNonPositive(const NInt<Type> & r) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE
1625  // Tests whether the given value is <= 0.
1626  {
1627  return r.d_value <= (Type)0;
1628  }
1629 
1630  template<typename Type>
1631  inline void add(NInt<Type> & r, const NInt<Type> & a, const NInt<Type> & b) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE
1632  {
1633  r.d_value = a.d_value + b.d_value;
1634  }
1635 
1636  template<typename Type>
1637  inline void sub(NInt<Type> & r, const NInt<Type> & a, const NInt<Type> & b) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE
1638  {
1639  r.d_value = a.d_value - b.d_value;
1640  }
1641 
1642  template<typename Type>
1643  inline void addmul(NInt<Type> & r, const NInt<Type> & a, const NInt<Type> & b) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE
1644  {
1645  r.d_value += a.d_value * b.d_value;
1646  }
1647 
1648  template<typename Type>
1649  inline void submul(NInt<Type> & r, const NInt<Type> & a, const NInt<Type> & b) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE
1650  {
1651  r.d_value -= a.d_value * b.d_value;
1652  }
1653 
1654  template<typename Type>
1655  inline void mul(NInt<Type> & r, const NInt<Type> & a, const NInt<Type> & b) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE
1656  {
1657  r.d_value = a.d_value * b.d_value;
1658  }
1659 
1660  template<typename Type>
1661  inline void div(NInt<Type> & r, const NInt<Type> & a, const NInt<Type> & b) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE
1662  {
1663  r.d_value = a.d_value / b.d_value;
1664  }
1665 
1666  template<typename Type>
1667  inline void mod(NInt<Type> & r, const NInt<Type> & a, const NInt<Type> & b) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE
1668  {
1669  r.d_value = a.d_value % b.d_value;
1670  }
1671 
1672  template<typename Type>
1673  inline void divmod(NInt<Type> & q, NInt<Type> & r, const NInt<Type> & a, const NInt<Type> & b) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE
1674  {
1675  Type qq = a.d_value / b.d_value, rr = a.d_value % b.d_value;
1676  q.d_value = qq;
1677  r.d_value = rr;
1678  }
1679 
1680  template<typename Type>
1681  inline void shl(NInt<Type> & r, const NInt<Type> & a, long b) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE
1682  {
1683  if (b < 0)
1684  {
1685  if (static_cast<unsigned long>(-b) >= static_cast<unsigned long>(std::numeric_limits<Type>::digits))
1686  r.d_value = 0;
1687  else
1688  r.d_value = a.d_value >> static_cast<unsigned long>(-b);
1689  }
1690  else
1691  {
1692  if (b >= std::numeric_limits<Type>::digits)
1693  r.d_value = 0;
1694  else
1695  r.d_value = a.d_value << b;
1696  }
1697  }
1698 
1699  template<typename Type>
1700  inline void shr(NInt<Type> & r, const NInt<Type> & a, long b) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE
1701  {
1702  if (b < 0)
1703  {
1704  if (static_cast<unsigned long>(-b) >= static_cast<unsigned long>(std::numeric_limits<Type>::digits))
1705  r.d_value = 0;
1706  else
1707  r.d_value = a.d_value << static_cast<unsigned long>(-b);
1708  }
1709  else
1710  {
1711  if (b >= std::numeric_limits<Type>::digits)
1712  r.d_value = 0;
1713  else
1714  r.d_value = a.d_value >> b;
1715  }
1716  }
1717 
1718  template<typename Type>
1719  inline void shl(NInt<Type> & r, const NInt<Type> & a, const NInt<Type> & b) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE
1720  {
1721  r.d_value = a.d_value << b.d_value;
1722  }
1723 
1724  template<typename Type>
1725  inline void shr(NInt<Type> & r, const NInt<Type> & a, const NInt<Type> & b) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE
1726  {
1727  if (b.d_value >= std::numeric_limits<Type>::digits)
1728  r.d_value = 0;
1729  else
1730  r.d_value = a.d_value >> b.d_value;
1731  }
1732 
1733  template<typename Type>
1734  inline void increment(NInt<Type> & r, const NInt<Type> & a) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE
1735  {
1736  r.d_value = a.d_value + (Type)1;
1737  }
1738 
1739  template<typename Type>
1740  inline void decrement(NInt<Type> & r, const NInt<Type> & a) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE
1741  {
1742  r.d_value = a.d_value - (Type)1;
1743  }
1744 
1745  template<typename Type>
1746  inline void neg(NInt<Type> & r, const NInt<Type> & a) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE
1747  {
1748  r.d_value = -a.d_value;
1749  }
1750 
1751  template<typename Type>
1752  inline void abs(NInt<Type> & r, const NInt<Type> & a) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE
1753  {
1754  r.d_value = a.d_value < 0 ? -a.d_value : a.d_value;
1755  }
1756 
1757  template<typename Type>
1758  inline NInt<Type> abs(const NInt<Type> & i) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE
1759  {
1760  return NInt<Type>(true, i.d_value < 0 ? -i.d_value : i.d_value);
1761  }
1762 
1763  template<typename Type>
1764  inline void makeAbs(NInt<Type> & a) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE
1765  {
1766  if (a.d_value < 0)
1767  a.d_value = -a.d_value;
1768  }
1769 
1770  template<typename Type>
1771  std::ostream & operator << (std::ostream & s, const NInt<Type> & r)
1772  // Output to stream
1773  {
1774  return s << r.d_value;
1775  }
1776 
1777  template<typename Type>
1778  std::istream & operator >> (std::istream & s, NInt<Type> & r)
1779  // Input from stream
1780  {
1781  return s >> r.d_value;
1782  }
1783 
1784  template<typename Type>
1785  inline void setZero(NInt<Type> & r) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE
1786  // Set to zero
1787  {
1788  r.d_value = (Type)0;
1789  }
1790 
1791  template<typename Type>
1792  inline void setOne(NInt<Type> & r) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE
1793  // Set to one
1794  {
1795  r.d_value = (Type)1;
1796  }
1797 
1798  template<typename Type>
1799  inline int compare(const NInt<Type> & a, const NInt<Type> & b) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE
1800  // Tests whether the first real is < (-1), = (0) or > (1) than the second.
1801  {
1802  return a.d_value < b.d_value ? -1 : (a.d_value > b.d_value ? 1 : 0);
1803  }
1804 
1805  template<typename Type>
1806  inline int compareAbsValues(const NInt<Type> & a, const NInt<Type> & b) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE
1807  // Tests whether the absolute value of the first NInt is < (-1), = (0) or > (1) than the
1808  // absolute value of the second NInt.
1809  {
1810  Type aabs = a.d_value < 0 ? -a.d_value : a.d_value, babs = b.d_value < 0 ? -b.d_value : b.d_value;
1811  return aabs < babs ? -1 : (aabs > babs ? 1 : 0);
1812  }
1813 
1814  template<typename Type>
1815  inline int sign(const NInt<Type> & r) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE
1816  // Returns the sign (i.e. -1, 0, 1).
1817  {
1818  return r.d_value < 0 ? -1 : (r.d_value > 0 ? 1 : 0);
1819  }
1820 
1821  namespace implementation
1822  {
1823  template<typename Type>
1824  struct get_unsigned;
1825 
1826  template<>
1827  struct get_unsigned<int>
1828  {
1829  typedef unsigned int result;
1830  };
1831 
1832  template<>
1833  struct get_unsigned<long>
1834  {
1835  typedef unsigned long result;
1836  };
1837 
1838  template<>
1839  struct get_unsigned<long long>
1840  {
1841  typedef unsigned long long result;
1842  };
1843  }
1844 
1845  template<typename Type>
1846  inline int bit(const NInt<Type> & v, long n) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE
1847  // Returns the n-th bit of the given integer.
1848  {
1849  return v.d_value < 0
1850  ? ((static_cast<typename implementation::get_unsigned<Type>::result>(-v.d_value) >> (Type)n) & 1)
1851  : ((v.d_value >> (Type)n) & 1);
1852  }
1853 
1854  template<typename Type>
1855  inline void setbit(NInt<Type> & v, long n, bool value) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE
1856  // Sets the n-th bit of the given integer.
1857  {
1858  if (value)
1859  v.d_value |= (static_cast<Type>(1) << n);
1860  else
1861  v.d_value &= ~(static_cast<Type>(1) << n);
1862  }
1863 
1864  template<typename Type>
1865  inline NInt<Type> square(const NInt<Type> & i) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE
1866  {
1867  return NInt<Type>(true, i.d_value * i.d_value);
1868  }
1869 
1870  template<typename Type>
1871  inline void square(NInt<Type> & r, const NInt<Type> & a) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE
1872  {
1873  r.d_value = a.d_value * a.d_value;
1874  }
1875 
1876  template<typename Type>
1877  inline Type powerimpl(Type base, Type exp) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE
1878  {
1879  assert(exp >= 0);
1880  Type result = (exp & 1) ? base : (Type)1;
1881  exp >>= 1;
1882  while (exp)
1883  {
1884  base = base * base;
1885  if (exp & 1)
1886  result *= base;
1887  exp >>= 1;
1888  }
1889  return result;
1890  }
1891 
1892  template<typename Type>
1893  inline void power(NInt<Type> & r, const NInt<Type> & a, long e) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE
1894  {
1895  r.d_value = powerimpl(a.d_value, (Type)e);
1896  }
1897 
1898  template<typename Type>
1899  inline NInt<Type> power(const NInt<Type> & a, long e) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE
1900  {
1901  return NInt<Type>(true, powerimpl(a.d_value, (Type)e));
1902  }
1903 
1904  template<typename Type>
1905  inline void power(NInt<Type> & r, const NInt<Type> & a, const NInt<Type> & e) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE
1906  {
1907  r.d_value = powerimpl(a.d_value, e.d_value);
1908  }
1909 
1910  template<typename Type>
1911  inline NInt<Type> power(const NInt<Type> & a, const NInt<Type> & e) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE
1912  {
1913  return NInt<Type>(true, powerimpl(a.d_value, e.d_value));
1914  }
1915 
1916  template<typename Type>
1917  inline void sqrtCeil(NInt<Type> & v, const NInt<Type> & a) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE
1918  {
1919  Type result = 0, rsq = 0, bm = 1;
1920  int bits = 0;
1921  while (bm + (bm - 1) < a.d_value)
1922  {
1923  bm <<= 2;
1924  ++bits;
1925  }
1926  while (bm)
1927  {
1928  Type nsq = rsq + bm + (result << (bits + 1));
1929  if (nsq <= a.d_value)
1930  {
1931  result += (((Type)1) << bits);
1932  rsq = nsq;
1933  }
1934  bm >>= 2;
1935  --bits;
1936  }
1937  v.d_value = (rsq < a.d_value) ? result + 1 : result;
1938  }
1939 
1940  template<typename Type>
1941  inline void sqrtFloor(NInt<Type> & v, const NInt<Type> & a) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE
1942  {
1943  Type result = 0, rsq = 0, bm = 1;
1944  int bits = 0;
1945  while (bm + (bm - 1) < a.d_value)
1946  {
1947  bm <<= 2;
1948  ++bits;
1949  }
1950  while (bm)
1951  {
1952  Type nsq = rsq + bm + (result << (bits + 1));
1953  if (nsq <= a.d_value)
1954  {
1955  result += (((Type)1) << bits);
1956  rsq = nsq;
1957  }
1958  bm >>= 2;
1959  --bits;
1960  }
1961  v.d_value = result;
1962  }
1963 
1964  template<typename Type>
1965  long ceilOfLog2(const NInt<Type> & x) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE
1966  // Returns ceil(log_2(|x|)).
1967  {
1968  Type v = x.d_value < 0 ? -x.d_value : x.d_value;
1969  bool pot = (v & (-v)) == v;
1970  unsigned res = 0;
1971  while (v)
1972  {
1973  --res;
1974  v >>= 1;
1975  }
1976  if (!pot)
1977  ++res;
1978  return res;
1979  }
1980 
1981  template<typename Type>
1982  long floorOfLog2(const NInt<Type> & x) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE
1983  // Returns floor(log_2(|x|)).
1984  {
1985  Type v = x.d_value < 0 ? -x.d_value : x.d_value;
1986  unsigned res = 0;
1987  while (v)
1988  {
1989  --res;
1990  v >>= 1;
1991  }
1992  return res;
1993  }
1994 
1995  namespace implementation
1996  {
1997  template<class X> class GetUnsignedType;
1998 
1999  template<> class GetUnsignedType<signed short int>
2000  {
2001  public:
2002  typedef signed short int signed_type;
2003  typedef unsigned short int unsigned_type;
2004  enum { is_signed = true };
2005  };
2006 
2007  template<> class GetUnsignedType<signed int>
2008  {
2009  public:
2010  typedef signed int signed_type;
2011  typedef unsigned int unsigned_type;
2012  enum { is_signed = true };
2013  };
2014 
2015  template<> class GetUnsignedType<signed long>
2016  {
2017  public:
2018  typedef signed long signed_type;
2019  typedef unsigned long unsigned_type;
2020  enum { is_signed = true };
2021  };
2022 
2023  template<> class GetUnsignedType<signed long long>
2024  {
2025  public:
2026  typedef signed long long signed_type;
2027  typedef unsigned long long unsigned_type;
2028  enum { is_signed = true };
2029  };
2030 
2031  template<> class GetUnsignedType<unsigned short int>
2032  {
2033  public:
2034  typedef signed short int signed_type;
2035  typedef unsigned short int unsigned_type;
2036  enum { is_signed = false };
2037  };
2038 
2039  template<> class GetUnsignedType<unsigned int>
2040  {
2041  public:
2042  typedef signed int signed_type;
2043  typedef unsigned int unsigned_type;
2044  enum { is_signed = false };
2045  };
2046 
2047  template<> class GetUnsignedType<unsigned long>
2048  {
2049  public:
2050  typedef signed long signed_type;
2051  typedef unsigned long unsigned_type;
2052  enum { is_signed = false };
2053  };
2054 
2055  template<> class GetUnsignedType<unsigned long long>
2056  {
2057  public:
2058  typedef signed long long signed_type;
2059  typedef unsigned long long unsigned_type;
2060  enum { is_signed = false };
2061  };
2062 
2063  template<class UType>
2064  inline long approxLog2Impl(UType xx) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE // for unsigned types
2065  // Returns ~log_2(xx).
2066  {
2067  // Uses the technique described by Sean E. Anderson in
2068  // http://graphics.stanford.edu/~seander/bithacks.html#IntegerLog. The original version is
2069  // from Eric Cole and was modified by Andrew Shapira.
2070  unsigned int res, shift;
2071  PLLL_INTERNAL_STATIC_CHECK((std::numeric_limits<UType>::digits == 7) ||
2072  (std::numeric_limits<UType>::digits == 8) ||
2073  (std::numeric_limits<UType>::digits == 15) ||
2074  (std::numeric_limits<UType>::digits == 16) ||
2075  (std::numeric_limits<UType>::digits == 31) ||
2076  (std::numeric_limits<UType>::digits == 32) ||
2077  (std::numeric_limits<UType>::digits == 63) ||
2078  (std::numeric_limits<UType>::digits == 64) ||
2079  (std::numeric_limits<UType>::digits == 127) ||
2080  (std::numeric_limits<UType>::digits == 128), RequiresTypeOf_8_16_32_64_128_Bits)
2081  switch (std::numeric_limits<UType>::digits) // Note that CLANG seems to return bitsize-1
2082  // instead of bitsize.
2083  {
2084  case 7:
2085  case 8:
2086  {
2087  res = (xx > (UType)0xF) << 2; xx >>= res;
2088  shift = (xx > (UType)0x3) << 1; xx >>= shift; res |= shift;
2089  res |= (xx >> (UType)1);
2090  }
2091  return res;
2092  case 15:
2093  case 16:
2094  {
2095  res = (xx > (UType)0xFF) << 3; xx >>= res;
2096  shift = (xx > (UType)0xF ) << 2; xx >>= shift; res |= shift;
2097  shift = (xx > (UType)0x3 ) << 1; xx >>= shift; res |= shift;
2098  res |= (xx >> (UType)1);
2099  }
2100  return res;
2101  case 31:
2102  case 32:
2103  {
2104  res = (xx > (UType)0xFFFF) << 4; xx >>= res;
2105  shift = (xx > (UType)0xFF ) << 3; xx >>= shift; res |= shift;
2106  shift = (xx > (UType)0xF ) << 2; xx >>= shift; res |= shift;
2107  shift = (xx > (UType)0x3 ) << 1; xx >>= shift; res |= shift;
2108  res |= (xx >> (UType)1);
2109  }
2110  return res;
2111  case 63:
2112  case 64:
2113  {
2114  res = (xx > (UType)0xFFFFFFFFul) << 5; xx >>= res;
2115  shift = (xx > (UType)0xFFFF ) << 4; xx >>= shift; res |= shift;
2116  shift = (xx > (UType)0xFF ) << 3; xx >>= shift; res |= shift;
2117  shift = (xx > (UType)0xF ) << 2; xx >>= shift; res |= shift;
2118  shift = (xx > (UType)0x3 ) << 1; xx >>= shift; res |= shift;
2119  res |= (xx >> (UType)1);
2120  }
2121  return res;
2122  case 127:
2123  case 128:
2124  {
2125  res = (xx > (UType)0xFFFFFFFFFFFFFFFFul) << 6; xx >>= res;
2126  shift = (xx > (UType)0xFFFFFFFFul ) << 5; xx >>= shift; res |= shift;
2127  shift = (xx > (UType)0xFFFF ) << 4; xx >>= shift; res |= shift;
2128  shift = (xx > (UType)0xFF ) << 3; xx >>= shift; res |= shift;
2129  shift = (xx > (UType)0xF ) << 2; xx >>= shift; res |= shift;
2130  shift = (xx > (UType)0x3 ) << 1; xx >>= shift; res |= shift;
2131  res |= (xx >> (UType)1);
2132  }
2133  return res;
2134  }
2135  }
2136 
2137  template<typename Type>
2138  inline long approxLog2_impl(Type x, helper::BoolToType<true>) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE // for signed types
2139  // Returns ~log_2(|x|).
2140  {
2141  typedef typename GetUnsignedType<Type>::unsigned_type UType;
2142  return approxLog2Impl(x < 0 ? -(UType)x : (UType)x);
2143  }
2144 
2145  template<typename Type>
2146  inline long approxLog2_impl(Type x, helper::BoolToType<false>) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE // for unsigned types
2147  // Returns ~log_2(|x|).
2148  {
2149  return approxLog2Impl(x);
2150  }
2151  }
2152 
2153  template<typename Type>
2154  inline long approxLog2(Type x) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE // for signed & unsigned types
2155  // Returns ~log_2(|x|).
2156  {
2157  return implementation::approxLog2_impl(x, helper::BoolToType<implementation::GetUnsignedType<Type>::is_signed>());
2158  }
2159 
2160  template<typename Type>
2161  inline long approxLog2(const NInt<Type> & x) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE
2162  // Returns ~log_2(|x|).
2163  {
2164  return approxLog2(x.d_value);
2165  }
2166 
2167  template<typename Type>
2168  inline long bitLength(const NInt<Type> & x) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE
2169  // Returns n such that 2^{n-1} <= |x| < 2^n
2170  {
2171  return isZero(x) ? 0 : floorOfLog2(x) + 1;
2172  }
2173 
2174  template<typename Type>
2175  void floorDiv(NInt<Type> & r, const NInt<Type> & a, const NInt<Type> & b) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE
2176  // Computes r = floor(a/b), where b \neq 0.
2177  {
2178  Type aa = a.d_value < 0 ? -a.d_value : a.d_value;
2179  Type ba = b.d_value < 0 ? -b.d_value : b.d_value;
2180  bool neg = (b.d_value < 0) ^ (a.d_value < 0);
2181  if (neg)
2182  r.d_value = -(aa + (ba - 1)) / ba;
2183  else
2184  r.d_value = aa / ba;
2185  }
2186 
2187  template<typename Type>
2188  NInt<Type> floorDiv(const NInt<Type> & a, const NInt<Type> & b) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE
2189  {
2190  NInt<Type> result;
2191  floorDiv(result, a, b);
2192  return result;
2193  }
2194 
2195  template<typename Type>
2196  void ceilDiv(NInt<Type> & r, const NInt<Type> & a, const NInt<Type> & b) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE
2197  // Computes r = ceil(a/b), where b \neq 0.
2198  {
2199  Type aa = a.d_value < 0 ? -a.d_value : a.d_value;
2200  Type ba = b.d_value < 0 ? -b.d_value : b.d_value;
2201  bool neg = (b.d_value < 0) ^ (a.d_value < 0);
2202  if (neg)
2203  r.d_value = -aa / ba;
2204  else
2205  r.d_value = (aa + (ba - 1)) / ba;
2206  }
2207 
2208  template<typename Type>
2209  NInt<Type> ceilDiv(const NInt<Type> & a, const NInt<Type> & b) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE
2210  {
2211  NInt<Type> result;
2212  ceilDiv(result, a, b);
2213  return result;
2214  }
2215 
2216  template<typename Type>
2217  void roundDiv(NInt<Type> & r, const NInt<Type> & a, const NInt<Type> & b) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE
2218  // Computes r = round(a/b), where b \neq 0.
2219  {
2220  Type aa = a.d_value < 0 ? -a.d_value : a.d_value;
2221  Type ba = b.d_value < 0 ? -b.d_value : b.d_value;
2222  bool neg = (b.d_value < 0) ^ (a.d_value < 0);
2223  if (neg)
2224  r.d_value = -(aa + ba/2) / ba;
2225  else
2226  r.d_value = (aa + ba/2) / ba;
2227  }
2228 
2229  template<typename Type>
2230  NInt<Type> roundDiv(const NInt<Type> & a, const NInt<Type> & b) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE
2231  {
2232  NInt<Type> result;
2233  roundDiv(result, a, b);
2234  return result;
2235  }
2236 
2237  template<typename Type>
2238  inline void euclideanDivision(NInt<Type> & q, NInt<Type> & r, const NInt<Type> & a, const NInt<Type> & b) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE
2239  // Given b \neq 0, computes q, r such that a = q b + r, 0 <= |r| < |b| and b*r >= 0.
2240  {
2241  q.d_value = a.d_value / b.d_value;
2242  r.d_value = a.d_value % b.d_value;
2243  }
2244 
2245  template<typename Type>
2246  inline void euclideanDivisionPos(NInt<Type> & q, NInt<Type> & r, const NInt<Type> & a, const NInt<Type> & b) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE
2247  // Given b \neq 0, computes q, r such that a = q b + r, 0 <= r < |b|
2248  {
2249  Type aa = a.d_value < 0 ? -a.d_value : a.d_value;
2250  Type ba = b.d_value < 0 ? -b.d_value : b.d_value;
2251  bool neg = (b.d_value < 0) ^ (a.d_value < 0);
2252  if (neg)
2253  q.d_value = -(aa + (ba - 1)) / ba;
2254  else
2255  q.d_value = aa / ba;
2256  r.d_value = a.d_value - q.d_value * b.d_value;
2257  }
2258 
2259  template<typename Type>
2260  inline void GCD(NInt<Type> & r, const NInt<Type> & x, const NInt<Type> & y) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE
2261  // Computes the gcd of x and y.
2262  {
2263  Type a = x.d_value, b = y.d_value;
2264  if (a < 0)
2265  a = -a;
2266  if (b < 0)
2267  b = -b;
2268  while (a)
2269  {
2270  Type c = b % a;
2271  b = a;
2272  a = c;
2273  }
2274  r.d_value = b;
2275  }
2276 
2277  template<typename Type>
2278  NInt<Type> GCD(const NInt<Type> & x, const NInt<Type> & y) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE
2279  {
2280  NInt<Type> result;
2281  GCD(result, x, y);
2282  return result;
2283  }
2284 
2285  template<typename Type>
2286  inline void XGCD(NInt<Type> & r, NInt<Type> & a, NInt<Type> & b, const NInt<Type> & x, const NInt<Type> & y) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE
2287  // Computes the gcd of x and y, as well as a, b such that gcd = a*x + b*y.
2288  {
2289  Type aa = x.d_value, bb = y.d_value;
2290  Type x1, x2 = 0, y1 = 0, y2; // beginning: |a| = x1 * a + y1 * b, |b| = x2 * a + y2 * b
2291  if (aa < 0)
2292  {
2293  aa = -aa;
2294  x1 = -1;
2295  }
2296  else
2297  x1 = 1;
2298  if (bb < 0)
2299  {
2300  bb = -bb;
2301  y2 = -1;
2302  }
2303  else
2304  y2 = 1;
2305  while (aa)
2306  {
2307  Type r = bb % aa, q = bb / aa; // b = q * a + r
2308  // Have: a = x1 * a_orig + y1 * b_orig, b = x2 * a_orig + y2 * b_orig
2309  // Want: r = x1' * a_orig + y1' * b_orig, a = x2' * a_orig + y2' * b_orig
2310  // Use: r = b - q * a
2311  // Thus: x1' = q * x2 - x1
2312  // y1' = q * y2 - y1
2313  // x2' = x1
2314  // y2' = y1
2315  bb = aa;
2316  aa = r;
2317  Type x = x2 - q * x1;
2318  x2 = x1;
2319  x1 = x;
2320  Type y = y2 - q * y1;
2321  y2 = y1;
2322  y1 = y;
2323  }
2324  a.d_value = x2;
2325  b.d_value = y2;
2326  r.d_value = bb;
2327  }
2328 
2329  template<typename Type>
2330  inline void LCM(NInt<Type> & r, const NInt<Type> & x, const NInt<Type> & y) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE // Computes the lcm of x and y.
2331  {
2332  GCD(r, x, y);
2333  r.d_value = x.d_value * (y.d_value / r.d_value);
2334  }
2335 
2336  template<typename Type>
2337  NInt<Type> LCM(const NInt<Type> & x, const NInt<Type> & y) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE
2338  {
2339  NInt<Type> result;
2340  LCM(result, x, y);
2341  return result;
2342  }
2343 
2344  namespace implementation
2345  {
2346  void randomInt(int & l, long b, RandomNumberGenerator & rng);
2347  void randomInt(long & l, long b, RandomNumberGenerator & rng);
2348  void randomInt(long long & ll, long long b, RandomNumberGenerator & rng);
2349  void randomBits(int & l, unsigned long b, RandomNumberGenerator & rng);
2350  void randomBits(long & l, unsigned long b, RandomNumberGenerator & rng);
2351  void randomBits(long long & ll, unsigned long b, RandomNumberGenerator & rng);
2352  }
2353 
2354  template<class IType>
2355  inline void NIntContext<IType>::UniformRNG::random(NInt<IType> & res, const NInt<IType> & bound)
2356  {
2357  implementation::randomInt(res.d_value, bound.d_value, d_rng);
2358  }
2359 
2360  template<class IType>
2361  inline void NIntContext<IType>::UniformRNG::randomBits(NInt<IType> & res, unsigned long bits)
2362  {
2363  implementation::randomBits(res.d_value, bits, d_rng);
2364  }
2365 
2366  template<class IType>
2367  inline void NIntContext<IType>::UniformRNG::randomLen(NInt<IType> & res, unsigned long bits)
2368  {
2369  if (bits)
2370  {
2371  randomBits(res, bits - 1);
2372  IType b = 1;
2373  b <<= bits;
2374  res.d_value |= b;
2375  }
2376  else
2377  setZero(res);
2378  }
2379 
2380  template<typename Type>
2381  inline void swap(NInt<Type> & a, NInt<Type> & b) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE
2382  {
2383  std::swap(a.d_value, b.d_value);
2384  }
2385  }
2386 }
2387 
2388 #include "arithmetic-nint-conv.hpp"
2389 
2390 #endif
plll::arithmetic::NIntContext::UniformRNG::randomLen
void randomLen(NInt< IType > &res, unsigned long bits)
Creates a random integer of a fixed bit length.
Definition: arithmetic-nint.hpp:2367
plll::arithmetic::floorDiv
expressions::Expression< IntegerContext, std::pair< expressions::Wrapper< IntegerContext >, expressions::Wrapper< IntegerContext > >, expressions::FloorDivOp > floorDiv(const Integer &a, const Integer &b)
Computes and returns .
Definition: arithmetic-gmp-iops.hpp:1583
plll::arithmetic::submul
void submul(Integer &r, const Integer &a, const Integer &b)
Multiplies a and b and subtracts the result from r.
Definition: arithmetic-gmp.hpp:1483
plll::arithmetic::euclideanDivisionPos
void euclideanDivisionPos(Integer &q, Integer &r, const Integer &a, const Integer &b)
Computes an Euclidean Division of a by b.
Definition: arithmetic-gmp.hpp:1652
plll::arithmetic::exp
expressions::Expression< RealContext, expressions::Wrapper< RealContext >, expressions::ExpOp > exp(const Real &i)
Returns the exponential function evaluated at the given floating point number.
Definition: arithmetic-gmp-rops.hpp:1548
plll::arithmetic::operator+=
Integer & operator+=(Integer &cur, const expressions::Expression< IntegerContext, D, expressions::MulOp > &E)
Adds the given multiplication expression to cur.
Definition: arithmetic-gmp-iops.hpp:844
plll::arithmetic::isZero
bool isZero(const Integer &) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE
Tests the given plll::arithmetic::Integer object for being zero.
Definition: arithmetic-gmp.hpp:1601
plll::arithmetic::NInt::NInt
NInt(const Integer &i)
Creates a native CPU integer from the given arbitrary precision integer.
Definition: arithmetic-nint.hpp:1271
plll::arithmetic::NIntContext::UniformRNG
A uniform random number generator frontend.
Definition: arithmetic-nint.hpp:89
plll::arithmetic::NInt::NInt
NInt(long i) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE
Creates a native CPU integer from the given native integer.
Definition: arithmetic-nint.hpp:1251
plll::arithmetic::NInt::NInt
NInt(const NInt< T > &i) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE
Creates a copy of the given integer (of another native type).
Definition: arithmetic-nint.hpp:1189
plll::arithmetic::operator%=
Integer & operator%=(Integer &cur, const Integer &i)
Divides cur by the given integer i and stores the remainder in cur.
Definition: arithmetic-gmp-iops.hpp:897
plll::arithmetic::isPMTwo
bool isPMTwo(const Integer &) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE
Tests the given plll::arithmetic::Integer object for being two or minus two.
Definition: arithmetic-gmp.hpp:1616
plll::arithmetic::NIntContext::UniformRNG::randomLen
NInt< IType > randomLen(unsigned long bits, const NIntContext< IType > &ic)
Creates a random integer of a fixed bit length.
Definition: arithmetic-nint.hpp:163
plll::arithmetic::bit
int bit(const Integer &x, long n) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE
Returns the n bit of in the usual binary representation.
Definition: arithmetic-gmp.hpp:1773
plll::arithmetic::XGCD
void XGCD(Integer &r, Integer &a, Integer &b, const Integer &x, const Integer &y)
Computes the non-negative extended Greatest Common Divisior r of x and y.
Definition: arithmetic-gmp.hpp:1676
plll::arithmetic::compare
int compare(const Integer &a, const Integer &b)
Compares the two integers.
Definition: arithmetic-gmp.hpp:1718
plll::arithmetic::isNegative
bool isNegative(const Integer &) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE
Tests the given plll::arithmetic::Integer object for being strictly negative.
Definition: arithmetic-gmp.hpp:1631
plll::arithmetic::operator-
expressions::Expression< IntegerContext, expressions::Wrapper< IntegerContext >, expressions::NegOp > operator-(const Integer &a)
Negates the integer.
Definition: arithmetic-gmp-iops.hpp:249
plll::arithmetic::setOne
void setOne(Integer &)
Sets the given integer to one.
Definition: arithmetic-gmp.hpp:1712
plll::arithmetic::shr
void shr(Integer &r, const Integer &a, long b)
Shifts a by b bits to the left and stores the result in r.
Definition: arithmetic-gmp.hpp:1588
plll::arithmetic::sqrtFloor
expressions::Expression< IntegerContext, expressions::Wrapper< IntegerContext >, expressions::SqrtFloorOp > sqrtFloor(const Integer &i)
Computes and returns the floor of the square root of i.
Definition: arithmetic-gmp-iops.hpp:1521
plll::arithmetic::isOne
bool isOne(const Integer &) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE
Tests the given plll::arithmetic::Integer object for being one.
Definition: arithmetic-gmp.hpp:1606
PLLL_INTERNAL_STATIC_CHECK
#define PLLL_INTERNAL_STATIC_CHECK(condition, IdentifierWhichIsAMessage)
Definition: helper.hpp:83
plll::arithmetic::NIntContext::Integer
arithmetic::NInt< IType > Integer
The integer type.
Definition: arithmetic-nint.hpp:72
plll::arithmetic::operator*=
Integer & operator*=(Integer &cur, const Integer &i)
Multiplies the given integer i with cur.
Definition: arithmetic-gmp-iops.hpp:870
plll::arithmetic::operator--
Integer operator--(Integer &cur, int)
Decrements the integer by one and returns the previous value.
Definition: arithmetic-gmp-iops.hpp:766
plll::arithmetic::abs
expressions::Expression< IntegerContext, expressions::Wrapper< IntegerContext >, expressions::AbsOp > abs(const Integer &i)
Computes and returns the absolute value of i.
Definition: arithmetic-gmp-iops.hpp:1490
plll::arithmetic::LCM
expressions::Expression< IntegerContext, std::pair< expressions::Wrapper< IntegerContext >, expressions::Wrapper< IntegerContext > >, expressions::LCMOp > LCM(const Integer &a, const Integer &b)
Computes and returns the non-negative Least Common Multiple of a and b.
Definition: arithmetic-gmp-iops.hpp:1549
arithmetic-nint-conv.hpp
Conversion definitions for native integers.
plll::arithmetic::ceilDiv
expressions::Expression< IntegerContext, std::pair< expressions::Wrapper< IntegerContext >, expressions::Wrapper< IntegerContext > >, expressions::CeilDivOp > ceilDiv(const Integer &a, const Integer &b)
Computes and returns .
Definition: arithmetic-gmp-iops.hpp:1596
plll::arithmetic::approxLog2
long approxLog2(const Integer &x) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE
Quickly approximates and returns the approximation.
Definition: arithmetic-gmp.hpp:1793
plll::arithmetic::NIntContext::UniformRNG::random
void random(NInt< IType > &res, const NInt< IType > &bound)
Creates a random native CPU integer in the range .
Definition: arithmetic-nint.hpp:2355
plll::arithmetic::operator-=
Integer & operator-=(Integer &cur, const expressions::Expression< IntegerContext, D, expressions::MulOp > &E)
Subtracts the multiplication expression E from cur.
Definition: arithmetic-gmp-iops.hpp:814
plll::arithmetic::NInt::NInt
NInt(const NIntContext< Type > &c) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE
Creates a new integer. Default value is zero.
Definition: arithmetic-nint.hpp:1168
plll::arithmetic::setZero
void setZero(Integer &)
Sets the given integer to zero.
Definition: arithmetic-gmp.hpp:1706
plll::arithmetic::mul
void mul(Integer &r, const Integer &a, const Integer &b)
Multiplies a with b and stores the result in r.
Definition: arithmetic-gmp.hpp:1377
plll::arithmetic::implementation::conversion_impl
Provides conversion implementation from type SourceType to DestContext::Type.
Definition: arithmetic.hpp:713
plll::arithmetic::div
void div(Integer &r, const Integer &a, const Integer &b)
Divides a by b and stores the result in r.
Definition: arithmetic-gmp.hpp:1399
plll::arithmetic::NInt::NInt
NInt(const NInt &i, const NIntContext< Type > &ic) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE
Creates a copy of the given integer.
Definition: arithmetic-nint.hpp:1200
plll::arithmetic::convert
void convert(typename DestContext::Type &dst, const SourceType &src, const DestContext &context)
Converts the value in src to the type described by context and stores the result in dst...
Definition: arithmetic.hpp:734
plll::arithmetic::implementation::get_unsigned
Definition: arithmetic-nint.hpp:1824
plll::arithmetic::NIntContext::UniformRNG::randomBits
NInt< IType > randomBits(unsigned long bits, const NIntContext< IType > &ic)
Creates random bits.
Definition: arithmetic-nint.hpp:141
plll::arithmetic::mod
void mod(Integer &r, const Integer &a, const Integer &b)
Takes the remainder of the division of a by b and stores it in r.
Definition: arithmetic-gmp.hpp:1422
plll::arithmetic::increment
void increment(Integer &r, const Integer &a)
Increments a by one and stores the result in r.
Definition: arithmetic-gmp.hpp:1309
plll::arithmetic::operator==
bool operator==(const Integer &a, const Integer &b)
Compares the current integer with the given one for equality.
Definition: arithmetic-gmp-iops.hpp:1144
plll::arithmetic::NInt::NInt
NInt() PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE
Creates a new integer. Default value is zero.
Definition: arithmetic-nint.hpp:1158
plll::arithmetic::operator/=
Integer & operator/=(Integer &cur, const Integer &i)
Divides cur by the given integer i.
Definition: arithmetic-gmp-iops.hpp:883
plll::arithmetic::NInt::NInt
NInt(double d) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE
Creates a native CPU integer from the given native floating point number.
Definition: arithmetic-nint.hpp:1231
plll::arithmetic::operator*
expressions::Expression< IntegerContext, std::pair< expressions::Wrapper< IntegerContext >, expressions::Wrapper< IntegerContext > >, expressions::MulOp > operator*(const Integer &a, const Integer &b)
Multiplies the two integers and returns the result.
Definition: arithmetic-gmp-iops.hpp:299
plll::arithmetic::implementation::nativeconversion_impl
Implementation backend for conversions from context types to native types.
Definition: arithmetic.hpp:994
plll::arithmetic::RandomNumberGenerator
Represents a random number generator.
Definition: arithmetic-gmp.hpp:3281
plll::arithmetic::NIntContext::UniformRNG::random
NInt< IType > random(const NInt< IType > &bound, const NIntContext< IType > &ic)
Creates and returns a random native CPU integer in the range .
Definition: arithmetic-nint.hpp:119
plll::arithmetic::swap
void swap(NInt< Type > &, NInt< Type > &) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE
Swaps two plll::arithmetic::NInt<> objects.
Definition: arithmetic-nint.hpp:2381
plll::arithmetic::swap
void swap(plll::arithmetic::Integer &, plll::arithmetic::Integer &) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE
Swaps two plll::arithmetic::Integer objects.
Definition: arithmetic-gmp.hpp:3225
plll::arithmetic::power
expressions::Expression< IntegerContext, std::pair< expressions::Wrapper< IntegerContext >, expressions::Wrapper< IntegerContext > >, expressions::PowerOp > power(const Integer &a, const Integer &b)
Computes and returns a raised to the power of b.
Definition: arithmetic-gmp-iops.hpp:1566
plll::arithmetic::sqrtCeil
expressions::Expression< IntegerContext, expressions::Wrapper< IntegerContext >, expressions::SqrtCeilOp > sqrtCeil(const Integer &i)
Computes and returns the ceil of the square root of i.
Definition: arithmetic-gmp-iops.hpp:1512
plll::arithmetic::NIntContext::UniformRNG::UniformRNG
UniformRNG(RandomNumberGenerator &rng) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE
Creates a new uniform random number generator based on the given random number generator.
Definition: arithmetic-nint.hpp:99
plll::arithmetic::NInt::NInt
NInt(const NInt< T > &i, const NIntContext< Type > &ic) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE
Creates a copy of the given integer (of another native type).
Definition: arithmetic-nint.hpp:1212
plll::arithmetic::setbit
void setbit(Integer &x, long n, bool value=true)
Sets the n-th bit of to value.
Definition: arithmetic-gmp.hpp:1779
plll::arithmetic::NInt
Represents a native integer.
Definition: arithmetic-nint.hpp:48
plll::arithmetic::NInt::Context
NIntContext< Type > Context
The context type.
Definition: arithmetic-nint.hpp:1153
plll::arithmetic::NIntContext::UniformRNG::randomBits
void randomBits(NInt< IType > &res, unsigned long bits)
Creates random bits.
Definition: arithmetic-nint.hpp:2361
plll::arithmetic::compareAbsValues
int compareAbsValues(const Integer &a, const Integer &b)
Compares the two integers in absolute value.
Definition: arithmetic-gmp.hpp:1742
plll::arithmetic::isNonNegative
bool isNonNegative(const Integer &) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE
Tests the given plll::arithmetic::Integer object for being positive or zero.
Definition: arithmetic-gmp.hpp:1626
plll::arithmetic::roundDiv
expressions::Expression< IntegerContext, std::pair< expressions::Wrapper< IntegerContext >, expressions::Wrapper< IntegerContext > >, expressions::RoundDivOp > roundDiv(const Integer &a, const Integer &b)
Computes and returns .
Definition: arithmetic-gmp-iops.hpp:1609
plll::arithmetic::sign
int sign(const Integer &) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE
Returns the sign of the given integer.
Definition: arithmetic-gmp.hpp:1767
plll::arithmetic::NInt::NInt
NInt(unsigned long i) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE
Creates a native CPU integer from the given native integer.
Definition: arithmetic-nint.hpp:1261
plll::arithmetic::operator++
Integer operator++(Integer &cur, int)
Increments the integer by one and returns the previous value.
Definition: arithmetic-gmp-iops.hpp:753
plll::arithmetic::operator>
bool operator>(const Integer &a, const Integer &b)
Compares the current integer with the given one.
Definition: arithmetic-gmp-iops.hpp:1199
plll::arithmetic::shl
void shl(Integer &r, const Integer &a, long b)
Shifts a by b bits to the left and stores the result in r.
Definition: arithmetic-gmp.hpp:1575
plll::arithmetic::NInt::setContext
static void setContext(const NIntContext< Type > &c) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE
Sets the integer context c.
Definition: arithmetic-nint.hpp:1222
plll::arithmetic::operator>>
expressions::Expression< IntegerContext, std::pair< expressions::Wrapper< IntegerContext >, expressions::Wrapper< IntegerContext > >, expressions::ShROp > operator>>(const Integer &a, const Integer &b)
Computes the bitwise right shift of the first integer by the number of bits given by the second integ...
Definition: arithmetic-gmp-iops.hpp:404
plll::arithmetic::neg
void neg(Integer &r, const Integer &a)
Negates a and stores the result in r.
Definition: arithmetic-gmp.hpp:1394
plll::arithmetic::addmul
void addmul(Integer &r, const Integer &a, const Integer &b)
Multiplies a and b and adds the result to r.
Definition: arithmetic-gmp.hpp:1463
plll::arithmetic::operator%
expressions::Expression< IntegerContext, std::pair< expressions::Wrapper< IntegerContext >, expressions::Wrapper< IntegerContext > >, expressions::ModOp > operator%(const Integer &a, const Integer &b)
Divides the first by the second integer and returns the remainder.
Definition: arithmetic-gmp-iops.hpp:327
plll::arithmetic::operator>>=
Integer & operator>>=(Integer &cur, const Integer &i)
Computes the bitwise right shift of cur by i bits, and stores the result in cur.
Definition: arithmetic-gmp-iops.hpp:969
plll::arithmetic::isPositive
bool isPositive(const Integer &) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE
Tests the given plll::arithmetic::Integer object for being strictly positive.
Definition: arithmetic-gmp.hpp:1621
plll::arithmetic::divmod
void divmod(Integer &q, Integer &r, const Integer &a, const Integer &b)
Stores quotient and remainder of the division of a by b in q respectively r.
Definition: arithmetic-gmp.hpp:1439
plll::arithmetic::add
void add(Integer &r, const Integer &a, const Integer &b)
Adds a and b and stores the result in r.
Definition: arithmetic-gmp.hpp:1319
plll::arithmetic::makeAbs
void makeAbs(Integer &a) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE
Makes the operand non-negative.
Definition: arithmetic-gmp.hpp:1641
plll::arithmetic::square
expressions::Expression< IntegerContext, expressions::Wrapper< IntegerContext >, expressions::SquareOp > square(const Integer &i)
Computes and returns the square of i.
Definition: arithmetic-gmp-iops.hpp:1499
plll::arithmetic::decrement
void decrement(Integer &r, const Integer &a)
Decrements a by one and stores the result in r.
Definition: arithmetic-gmp.hpp:1314
plll::arithmetic::bitLength
long bitLength(const Integer &x) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE
Computes and returns n such that .
Definition: arithmetic-gmp.hpp:1810
plll::arithmetic::floorOfLog2
long floorOfLog2(const Integer &x) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE
Computes and returns .
Definition: arithmetic-gmp.hpp:1805
plll::arithmetic::NInt::NInt
NInt(const NInt &i) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE
Creates a copy of the given integer.
Definition: arithmetic-nint.hpp:1178
plll::arithmetic::isNonPositive
bool isNonPositive(const Integer &) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE
Tests the given plll::arithmetic::Integer object for being negative or zero.
Definition: arithmetic-gmp.hpp:1636
plll::arithmetic::ceilOfLog2
long ceilOfLog2(const Integer &x) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE
Computes and returns .
Definition: arithmetic-gmp.hpp:1798
plll::arithmetic::operator+
expressions::Expression< IntegerContext, std::pair< expressions::Wrapper< IntegerContext >, expressions::Wrapper< IntegerContext > >, expressions::AddOp > operator+(const Integer &a, const Integer &b)
Adds the two integers and returns the result.
Definition: arithmetic-gmp-iops.hpp:271
plll::arithmetic::traits::type_traits
Provides information on arithmetic (and string) types.
Definition: arithmetic.hpp:184
plll::arithmetic::operator/
expressions::Expression< IntegerContext, std::pair< expressions::Wrapper< IntegerContext >, expressions::Wrapper< IntegerContext > >, expressions::DivOp > operator/(const Integer &a, const Integer &b)
Divides the first by the second integer and returns the result.
Definition: arithmetic-gmp-iops.hpp:313
plll::arithmetic::Integer
Represents an arbitrary precision integer.
Definition: arithmetic-gmp.hpp:1071
plll::arithmetic::isPMOne
bool isPMOne(const Integer &) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE
Tests the given plll::arithmetic::Integer object for being one or minus one.
Definition: arithmetic-gmp.hpp:1611
plll::arithmetic::euclideanDivision
void euclideanDivision(Integer &q, Integer &r, const Integer &a, const Integer &b)
Computes an Euclidean Division of a by b.
Definition: arithmetic-gmp.hpp:1646
plll::arithmetic::operator!=
bool operator!=(const Integer &a, const Integer &b)
Compares the current integer with the given one for inequality.
Definition: arithmetic-gmp-iops.hpp:1155
plll::arithmetic::NIntContext
Represents an arithmetic context for native integers.
Definition: arithmetic-nint.hpp:65
plll::arithmetic::GCD
expressions::Expression< IntegerContext, std::pair< expressions::Wrapper< IntegerContext >, expressions::Wrapper< IntegerContext > >, expressions::GCDOp > GCD(const Integer &a, const Integer &b)
Computes and returns the non-negative Greatest Common Divisor of a and b.
Definition: arithmetic-gmp-iops.hpp:1536
plll::arithmetic::NInt::NInt
NInt(long double d) PLLL_INTERNAL_NOTHROW_POSTFIX_INLINE
Creates a native CPU integer from the given native floating point number.
Definition: arithmetic-nint.hpp:1241
plll::arithmetic::operator>=
bool operator>=(const Integer &a, const Integer &b)
Compares the current integer with the given one.
Definition: arithmetic-gmp-iops.hpp:1177
plll::arithmetic::NIntContext::Type
arithmetic::NInt< IType > Type
The integer type.
Definition: arithmetic-nint.hpp:76
arithmetic.hpp
Main arithmetic header.
plll::arithmetic::sub
void sub(Integer &r, const Integer &a, const Integer &b)
Subtracts b from a and stores the result in r.
Definition: arithmetic-gmp.hpp:1339