include/cln/integer.h

0001 // Public integer operations.
0002
0003 #ifndef _CL_INTEGER_H
0004 #define _CL_INTEGER_H
0005
0006 #include "cln/number.h"
0007 #include "cln/integer_class.h"
0008 #include "cln/exception.h"
0009 #include "cln/random.h"
0010
0011 namespace cln {
0012
0013 CL_DEFINE_AS_CONVERSION(cl_I)
0014
0015
0016 // Konversion Integer >=0, <2^32 nach uintL.
0017 // Wandelt Integer >=0 in Unsigned Longword um.
0018 // cl_I_to_UL(obj)
0019 // > obj: Integer, sollte >=0, <2^32 sein
0020 // < ergebnis: der Wert des Integer als 32-Bit-Zahl.
0021   extern uint32 cl_I_to_UL (const cl_I& obj);
0022
0023 // Konversion Integer >=-2^31, <2^31 nach sintL.
0024 // Wandelt Integer in Signed Longword um.
0025 // cl_I_to_L(obj)
0026 // > obj: Integer, sollte >=-2^31, <2^31 sein
0027 // < ergebnis: der Wert des Integer als 32-Bit-Zahl.
0028   extern sint32 cl_I_to_L (const cl_I& obj);
0029
0030 // Convert an integer to a C `int' or `unsigned int'.
0031 #if (int_bitsize==32)
0032   inline int          cl_I_to_int  (const cl_I& x) { return cl_I_to_L(x);  }
0033   inline unsigned int cl_I_to_uint (const cl_I& x) { return cl_I_to_UL(x); }
0034 #endif
0035
0036 // Convert an integer to a 64-bit 'quad' type.
0037 #ifdef intQsize
0038  extern uint64 cl_I_to_UQ (const cl_I& obj);
0039  extern sint64 cl_I_to_Q (const cl_I& obj);
0040 #endif
0041
0042 // Convert an integer to a C `long' or `unsigned long'.
0043 #if (long_bitsize==32)
0044   inline long          cl_I_to_long  (const cl_I& x) { return cl_I_to_L(x);  }
0045   inline unsigned long cl_I_to_ulong (const cl_I& x) { return cl_I_to_UL(x); }
0046 #elif (long_bitsize==64)
0047   inline long          cl_I_to_long  (const cl_I& x) { return cl_I_to_Q(x);  }
0048   inline unsigned long cl_I_to_ulong (const cl_I& x) { return cl_I_to_UQ(x); }
0049 #endif
0050
0051 // Convert an integer to a counter type.
0052 #if (intCsize==long_bitsize)
0053   inline uintC cl_I_to_UC (const cl_I& x) { return cl_I_to_ulong(x); }
0054   inline sintC cl_I_to_C  (const cl_I& x) { return cl_I_to_long(x);  }
0055 #elif (intCsize==int_bitsize)
0056   inline uintC cl_I_to_UC (const cl_I& x) { return cl_I_to_uint(x); }
0057   inline sintC cl_I_to_C  (const cl_I& x) { return cl_I_to_int(x);  }
0058 #endif
0059
0060 // Convert an integer to an exponent type.
0061 #if (intEsize==intLsize)
0062   inline uintE cl_I_to_UE (const cl_I& x) { return cl_I_to_UL(x); }
0063   inline sintE cl_I_to_E  (const cl_I& x) { return cl_I_to_L(x);  }
0064 #elif (intEsize==intQsize)
0065   inline uintE cl_I_to_UE (const cl_I& x) { return cl_I_to_UQ(x); }
0066   inline sintE cl_I_to_E  (const cl_I& x) { return cl_I_to_Q(x);  }
0067 #endif
0068
0069
0070 // Logische Operationen auf Integers:
0071
0072 // (LOGIOR x y), wenn x, y Integers sind.
0073 // Ergebnis Integer.
0074 extern const cl_I logior (const cl_I& x, const cl_I& y);
0075
0076 // (LOGXOR x y), wenn x, y Integers sind.
0077 // Ergebnis Integer.
0078 extern const cl_I logxor (const cl_I& x, const cl_I& y);
0079
0080 // (LOGAND x y), wenn x, y Integers sind.
0081 // Ergebnis Integer.
0082 extern const cl_I logand (const cl_I& x, const cl_I& y);
0083
0084 // (LOGEQV x y), wenn x, y Integers sind.
0085 // Ergebnis Integer.
0086 extern const cl_I logeqv (const cl_I& x, const cl_I& y);
0087
0088 // (LOGNAND x y), wenn x, y Integers sind.
0089 // Ergebnis Integer.
0090 extern const cl_I lognand (const cl_I& x, const cl_I& y);
0091
0092 // (LOGNOR x y), wenn x, y Integers sind.
0093 // Ergebnis Integer.
0094 extern const cl_I lognor (const cl_I& x, const cl_I& y);
0095
0096 // (LOGANDC2 x y), wenn x, y Integers sind.
0097 // Ergebnis Integer.
0098 extern const cl_I logandc2 (const cl_I& x, const cl_I& y);
0099
0100 // (LOGANDC1 x y), wenn x, y Integers sind.
0101 // Ergebnis Integer.
0102 inline const cl_I logandc1 (const cl_I& x, const cl_I& y)
0103 {
0104     return logandc2(y,x);
0105 }
0106
0107 // (LOGORC2 x y), wenn x, y Integers sind.
0108 // Ergebnis Integer.
0109 extern const cl_I logorc2 (const cl_I& x, const cl_I& y);
0110
0111 // (LOGORC1 x y), wenn x, y Integers sind.
0112 // Ergebnis Integer.
0113 inline const cl_I logorc1 (const cl_I& x, const cl_I& y)
0114 {
0115     return logorc2(y,x);
0116 }
0117
0118 // (LOGNOT x), wenn x ein Integer sind.
0119 // Ergebnis Integer.
0120 extern const cl_I lognot (const cl_I& x);
0121
0122 // Konstanten für BOOLE:
0123 typedef enum {
0124     boole_clr,
0125     boole_set,
0126     boole_1,
0127     boole_2,
0128     boole_c1,
0129     boole_c2,
0130     boole_and,
0131     boole_ior,
0132     boole_xor,
0133     boole_eqv,
0134     boole_nand,
0135     boole_nor,
0136     boole_andc1,
0137     boole_andc2,
0138     boole_orc1,
0139     boole_orc2
0140 } cl_boole;
0141
0142 // (BOOLE op x y), wenn x und y Integers und op ein Objekt sind.
0143 // Ergebnis Integer.
0144 extern const cl_I boole (cl_boole op, const cl_I& x, const cl_I& y);
0145
0146 // Prüft, ob (LOGTEST x y), wo x und y Integers sind.
0147 // (LOGTEST x y) = (NOT (ZEROP (LOGAND x y))).
0148 // < ergebnis: /=0, falls ja; =0, falls nein.
0149 extern bool logtest (const cl_I& x, const cl_I& y);
0150
0151 // Prüft, ob (LOGBITP x y), wo x und y Integers sind.
0152 // Ergebnis: /=0, wenn ja; =0, wenn nein.
0153 extern bool logbitp (uintC x, const cl_I& y);
0154 extern bool logbitp (const cl_I& x, const cl_I& y);
0155
0156 // Prüft, ob (ODDP x), wo x ein Integer ist.
0157 // Ergebnis: /=0, falls ja; =0, falls nein.
0158 extern bool oddp (const cl_I& x);
0159
0160 // Prüft, ob (EVENP x), wo x ein Integer ist.
0161 // Ergebnis: /=0, falls ja; =0, falls nein.
0162 inline bool evenp (const cl_I& x)
0163     { return !oddp(x); }
0164
0165 // (ASH x y), wo x und y Integers sind. Ergebnis Integer.
0166 extern const cl_I ash (const cl_I& x, sintC y);
0167 extern const cl_I ash (const cl_I& x, const cl_I& y);
0168
0169 // Thrown when shift amount is too large.
0170 class ash_exception : public runtime_exception {
0171 public:
0172     explicit ash_exception (const cl_I& badamount);
0173 };
0174
0175 // (LOGCOUNT x), wo x ein Integer ist. Ergebnis uintC.
0176 extern uintC logcount (const cl_I& x);
0177
0178 // (INTEGER-LENGTH x), wo x ein Integer ist. Ergebnis uintC.
0179 extern uintC integer_length (const cl_I& x);
0180
0181 // (ORD2 x) = max{n>=0: 2^n | x }, wo x ein Integer /=0 ist. Ergebnis uintC.
0182 extern uintC ord2 (const cl_I& x);
0183
0184 // power2p(x) stellt fest, ob ein Integer x>0 eine Zweierpotenz ist.
0185 // Ergebnis: n>0, wenn x=2^(n-1), 0 sonst.
0186 extern uintC power2p (const cl_I& x);
0187
0188 inline const cl_I operator| (const cl_I& x, const cl_I& y)
0189     { return logior(x,y); }
0190 inline const cl_I operator^ (const cl_I& x, const cl_I& y)
0191     { return logxor(x,y); }
0192 inline const cl_I operator& (const cl_I& x, const cl_I& y)
0193     { return logand(x,y); }
0194 inline const cl_I operator~ (const cl_I& x)
0195     { return lognot(x); }
0196 // This could be optimized to use in-place operations.
0197 inline cl_I& operator|= (cl_I& x, const cl_I& y) { return x = x | y; }
0198 inline cl_I& operator^= (cl_I& x, const cl_I& y) { return x = x ^ y; }
0199 inline cl_I& operator&= (cl_I& x, const cl_I& y) { return x = x & y; }
0200
0201
0202 // Addition/Subtraktion von Integers
0203
0204 // (1+ x), wo x ein Integer ist. Ergebnis Integer.
0205 extern const cl_I plus1 (const cl_I& x);
0206
0207 // (1- x), wo x ein Integer ist. Ergebnis Integer.
0208 extern const cl_I minus1 (const cl_I& x);
0209
0210 // (+ x y), wo x und y Integers sind. Ergebnis Integer.
0211 extern const cl_I operator+ (const cl_I& x, const cl_I& y);
0212 // Dem C++-Compiler muß man auch das Folgende sagen:
0213 inline const cl_I operator+ (const int x, const cl_I& y)
0214     { return cl_I(x) + y; }
0215 inline const cl_I operator+ (const unsigned int x, const cl_I& y)
0216     { return cl_I(x) + y; }
0217 inline const cl_I operator+ (const long x, const cl_I& y)
0218     { return cl_I(x) + y; }
0219 inline const cl_I operator+ (const unsigned long x, const cl_I& y)
0220     { return cl_I(x) + y; }
0221 inline const cl_I operator+ (const long long x, const cl_I& y)
0222     { return cl_I(x) + y; }
0223 inline const cl_I operator+ (const unsigned long long x, const cl_I& y)
0224     { return cl_I(x) + y; }
0225 inline const cl_I operator+ (const cl_I& x, const int y)
0226     { return x + cl_I(y); }
0227 inline const cl_I operator+ (const cl_I& x, const unsigned int y)
0228     { return x + cl_I(y); }
0229 inline const cl_I operator+ (const cl_I& x, const long y)
0230     { return x + cl_I(y); }
0231 inline const cl_I operator+ (const cl_I& x, const unsigned long y)
0232     { return x + cl_I(y); }
0233 inline const cl_I operator+ (const cl_I& x, const long long y)
0234     { return x + cl_I(y); }
0235 inline const cl_I operator+ (const cl_I& x, const unsigned long long y)
0236     { return x + cl_I(y); }
0237
0238 // (- x), wenn x ein Integer ist. Ergebnis Integer.
0239 extern const cl_I operator- (const cl_I& x);
0240
0241 // (- x y), wo x und y Integers sind. Ergebnis Integer.
0242 extern const cl_I operator- (const cl_I& x, const cl_I& y);
0243 // Dem C++-Compiler muß man auch das Folgende sagen:
0244 inline const cl_I operator- (const int x, const cl_I& y)
0245     { return cl_I(x) - y; }
0246 inline const cl_I operator- (const unsigned int x, const cl_I& y)
0247     { return cl_I(x) - y; }
0248 inline const cl_I operator- (const long x, const cl_I& y)
0249     { return cl_I(x) - y; }
0250 inline const cl_I operator- (const unsigned long x, const cl_I& y)
0251     { return cl_I(x) - y; }
0252 inline const cl_I operator- (const long long x, const cl_I& y)
0253     { return cl_I(x) - y; }
0254 inline const cl_I operator- (const unsigned long long x, const cl_I& y)
0255     { return cl_I(x) - y; }
0256 inline const cl_I operator- (const cl_I& x, const int y)
0257     { return x - cl_I(y); }
0258 inline const cl_I operator- (const cl_I& x, const unsigned int y)
0259     { return x - cl_I(y); }
0260 inline const cl_I operator- (const cl_I& x, const long y)
0261     { return x - cl_I(y); }
0262 inline const cl_I operator- (const cl_I& x, const unsigned long y)
0263     { return x - cl_I(y); }
0264 inline const cl_I operator- (const cl_I& x, const long long y)
0265     { return x - cl_I(y); }
0266 inline const cl_I operator- (const cl_I& x, const unsigned long long y)
0267     { return x - cl_I(y); }
0268
0269 // (abs x), wenn x ein Integer ist. Ergebnis Integer.
0270 extern const cl_I abs (const cl_I& x);
0271
0272 // Shifts.
0273 inline const cl_I operator<< (const cl_I& x, sintC y) // assume 0 <= y < 2^(intCsize-1)
0274     { return ash(x,y); }
0275 inline const cl_I operator<< (const cl_I& x, const cl_I& y) // assume y >= 0
0276     { return ash(x,y); }
0277 inline const cl_I operator>> (const cl_I& x, sintC y) // assume 0 <= y < 2^(intCsize-1)
0278     { return ash(x,-y); }
0279 inline const cl_I operator>> (const cl_I& x, const cl_I& y) // assume y >= 0
0280     { return ash(x,-y); }
0281
0282
0283 // Vergleich von Integers
0284
0285 // equal(x,y) vergleicht zwei Integers x und y auf Gleichheit.
0286 extern bool equal (const cl_I& x, const cl_I& y);
0287 // equal_hashcode(x) liefert einen equal-invarianten Hashcode für x.
0288 extern uint32 equal_hashcode (const cl_I& x);
0289
0290 // compare(x,y) vergleicht zwei Integers x und y.
0291 // Ergebnis: 0 falls x=y, +1 falls x>y, -1 falls x<y.
0292 extern cl_signean compare (const cl_I& x, const cl_I& y);
0293
0294 inline bool operator== (const cl_I& x, const cl_I& y)
0295     { return equal(x,y); }
0296 inline bool operator!= (const cl_I& x, const cl_I& y)
0297     { return !equal(x,y); }
0298 inline bool operator<= (const cl_I& x, const cl_I& y)
0299     { return compare(x,y)<=0; }
0300 inline bool operator< (const cl_I& x, const cl_I& y)
0301     { return compare(x,y)<0; }
0302 inline bool operator>= (const cl_I& x, const cl_I& y)
0303     { return compare(x,y)>=0; }
0304 inline bool operator> (const cl_I& x, const cl_I& y)
0305     { return compare(x,y)>0; }
0306
0307 // minusp(x) == (< x 0)
0308 extern bool minusp (const cl_I& x);
0309
0310 // plusp(x) == (> x 0)
0311 extern bool plusp (const cl_I& x);
0312
0313 // zerop(x) stellt fest, ob ein Integer = 0 ist.
0314 extern bool zerop (const cl_I& x);
0315
0316
0317 // BYTE-Operationen auf Integers
0318
0319 struct cl_byte {
0320     uintC size;
0321     uintC position;
0322 // Konstruktor:
0323     cl_byte (uintC s, uintC p) : size (s), position (p) {}
0324 };
0325
0326 // (LDB byte n), wo n ein Integer ist.
0327 extern const cl_I ldb (const cl_I& n, const cl_byte& b);
0328
0329 // ldb_test(n,byte) führt (LDB-TEST byte n) aus, wobei n ein Integer ist.
0330 // Ergebnis: false wenn nein (also alle fraglichen Bits =0), true wenn ja.
0331 extern bool ldb_test (const cl_I& n, const cl_byte& b);
0332
0333 // (MASK-FIELD byte n), wo n ein Integer ist.
0334 extern const cl_I mask_field (const cl_I& n, const cl_byte& b);
0335
0336 // (DEPOSIT-FIELD newbyte byte n), wo n und newbyte Integers sind.
0337 extern const cl_I deposit_field (const cl_I& newbyte, const cl_I& n, const cl_byte& b);
0338
0339 // (DPB newbyte byte n), wo n und newbyte Integers sind.
0340 extern const cl_I dpb (const cl_I& newbyte, const cl_I& n, const cl_byte& b);
0341
0342
0343 // Multiplikation ganzer Zahlen
0344
0345 // (* x y), wo x und y Integers sind. Ergebnis Integer.
0346 extern const cl_I operator* (const cl_I& x, const cl_I& y);
0347 // Dem C++-Compiler muß man auch das Folgende sagen:
0348 inline const cl_I operator* (const int x, const cl_I& y)
0349     { return cl_I(x) * y; }
0350 inline const cl_I operator* (const unsigned int x, const cl_I& y)
0351     { return cl_I(x) * y; }
0352 inline const cl_I operator* (const long x, const cl_I& y)
0353     { return cl_I(x) * y; }
0354 inline const cl_I operator* (const unsigned long x, const cl_I& y)
0355     { return cl_I(x) * y; }
0356 inline const cl_I operator* (const long long x, const cl_I& y)
0357     { return cl_I(x) * y; }
0358 inline const cl_I operator* (const unsigned long long x, const cl_I& y)
0359     { return cl_I(x) * y; }
0360 inline const cl_I operator* (const cl_I& x, const int y)
0361     { return x * cl_I(y); }
0362 inline const cl_I operator* (const cl_I& x, const unsigned int y)
0363     { return x * cl_I(y); }
0364 inline const cl_I operator* (const cl_I& x, const long y)
0365     { return x * cl_I(y); }
0366 inline const cl_I operator* (const cl_I& x, const unsigned long y)
0367     { return x * cl_I(y); }
0368 inline const cl_I operator* (const cl_I& x, const long long y)
0369     { return x * cl_I(y); }
0370 inline const cl_I operator* (const cl_I& x, const unsigned long long y)
0371     { return x * cl_I(y); }
0372
0373 // (EXPT x 2), wo x Integer ist.
0374 extern const cl_I square (const cl_I& x);
0375
0376 // (EXPT x y), wo x Integer, y Integer >0 ist.
0377 extern const cl_I expt_pos (const cl_I& x, uintL y);
0378 extern const cl_I expt_pos (const cl_I& x, const cl_I& y);
0379
0380 // Fakultät (! n), wo n Fixnum >=0 ist. Ergebnis Integer.
0381 extern const cl_I factorial (uintL n);
0382
0383 // Double factorial (!! n), with n Fixnum >=0.  Returns integer.
0384 extern const cl_I doublefactorial (uintL n);
0385
0386 // Binomialkoeffizient (n \choose k) = n! / k! (n-k)!, wo n,k >= 0 sind.
0387 extern const cl_I binomial (uintL n, uintL k);
0388
0389
0390 // Division ganzer Zahlen
0391
0392 // Return type for division operators.
0393 // x / y  --> (q,r) with x = y*q+r.
0394 struct cl_I_div_t {
0395     cl_I quotient;
0396     cl_I remainder;
0397 // Constructor.
0398     cl_I_div_t () {}
0399     cl_I_div_t (const cl_I& q, const cl_I& r) : quotient(q), remainder(r) {}
0400 };
0401
0402 // Dividiert zwei Integers x,y >=0 und liefert den Quotienten x/y >=0.
0403 // Bei y=0 Error. Die Division muß aufgehen, sonst Error.
0404 // exquopos(x,y)
0405 // > x,y: Integers >=0
0406 // < ergebnis: Quotient x/y, ein Integer >=0
0407   extern const cl_I exquopos (const cl_I& x, const cl_I& y);
0408
0409 // Dividiert zwei Integers x,y und liefert den Quotienten x/y.
0410 // Bei y=0 Error. Die Division muß aufgehen, sonst Error.
0411 // exquo(x,y)
0412 // > x,y: Integers
0413 // < ergebnis: Quotient x/y, ein Integer
0414   extern const cl_I exquo (const cl_I& x, const cl_I& y);
0415
0416 // Thrown when quotient is no integer.
0417 class exquo_exception : public runtime_exception {
0418 public:
0419     exquo_exception (const cl_I& x, const cl_I& y);
0420 };
0421
0422 // mod(x,y) = (mod x y), wo x,y Integers sind.
0423   extern const cl_I mod (const cl_I& x, const cl_I& y);
0424
0425 // rem(x,y) = (rem x y), wo x,y Integers sind.
0426   extern const cl_I rem (const cl_I& x, const cl_I& y);
0427
0428 // Dividiert zwei Integers x,y und liefert Quotient und Rest
0429 // (q,r) := (floor x y)
0430 // floor2(x,y)
0431 // > x,y: Integers
0432 // < q,r: Quotient q, Rest r
0433   extern const cl_I_div_t floor2 (const cl_I& x, const cl_I& y);
0434   extern const cl_I floor1 (const cl_I& x, const cl_I& y);
0435
0436 // Dividiert zwei Integers x,y und liefert Quotient und Rest
0437 // (q,r) := (ceiling x y)
0438 // ceiling2(x,y)
0439 // > x,y: Integers
0440 // < q,r: Quotient q, Rest r
0441   extern const cl_I_div_t ceiling2 (const cl_I& x, const cl_I& y);
0442   extern const cl_I ceiling1 (const cl_I& x, const cl_I& y);
0443
0444 // Dividiert zwei Integers x,y und liefert Quotient und Rest
0445 // (q,r) := (truncate x y)
0446 // truncate2(x,y)
0447 // > x,y: Integers
0448 // < q,r: Quotient q, Rest r
0449   extern const cl_I_div_t truncate2 (const cl_I& x, const cl_I& y);
0450   extern const cl_I truncate1 (const cl_I& x, const cl_I& y);
0451
0452 // Dividiert zwei Integers x,y und liefert Quotient und Rest
0453 // (q,r) := (round x y)
0454 // round2(x,y)
0455 // > x,y: Integers
0456 // < q,r: Quotient q, Rest r
0457   extern const cl_I_div_t round2 (const cl_I& x, const cl_I& y);
0458   extern const cl_I round1 (const cl_I& x, const cl_I& y);
0459
0460
0461 // ggT und kgV von Integers
0462
0463 // Liefert den ggT zweier Integers.
0464 // gcd(a,b)
0465 // > a,b: zwei Integers
0466 // < ergebnis: (gcd a b), ein Integer >=0
0467   extern const cl_I gcd (const cl_I& a, const cl_I& b);
0468   extern uintV gcd (uintV a, uintV b);
0469
0470 // Liefert den ggT zweier Integers samt Beifaktoren.
0471 // g = xgcd(a,b,&u,&v)
0472 // > a,b: zwei Integers
0473 // < u, v, g: Integers mit u*a+v*b = g >= 0
0474   extern const cl_I xgcd (const cl_I& a, const cl_I& b, cl_I* u, cl_I* v);
0475 // Im Fall A/=0, B/=0 genügt das Ergebnis (g,u,v) den Ungleichungen:
0476 //   Falls |A| = |B| : g = |A|, u = (signum A), v = 0.
0477 //   Falls |B| | |A|, |B| < |A| : g = |B|, u = 0, v = (signum B).
0478 //   Falls |A| | |B|, |A| < |B| : g = |A|, u = (signum A), v = 0.
0479 //   Sonst: |u| <= |B| / (2*g), |v| <= |A| / (2*g).
0480 //   In jedem Fall |u| <= |B|/g, |v| < |A|/g.
0481 // (Beweis: Im Prinzip macht man ja mehrere Euklid-Schritte auf einmal. Im
0482 // letzten Fall - oBdA |A| > |B| - braucht man mindestens zwei Euklid-Schritte,
0483 // also gilt im Euklid-Tableau
0484 //                 i         |A|            |B|         Erg.
0485 //                --------------------------------------------
0486 //                 0          1              0          |A|
0487 //                 1          0              1          |B|
0488 //                ...        ...            ...         ...
0489 //                n-1  -(-1)^n*x[n-1]  (-1)^n*y[n-1]   z[n-1]
0490 //                 n    (-1)^n*x[n]    -(-1)^n*y[n]     z[n]
0491 //                n+1  -(-1)^n*x[n+1]  (-1)^n*y[n+1]   z[n+1] = 0
0492 //                --------------------------------------------
0493 //                       g = z[n], |u|=x[n], |v|=y[n]
0494 // n>=2, z[0] > ... > z[n-1] > z[n] = g, g | z[n-1], also z[n-1] >= 2*g.
0495 // Da aber mit  (-1)^i*x[i]*|A| - (-1)^i*y[i]*|B| = z[i]  für i=0..n+1
0496 // und            x[i]*y[i+1] - x[i+1]*y[i] = (-1)^i  für i=0..n,
0497 //                x[i]*z[i+1] - x[i+1]*z[i] = (-1)^i*|B|  für i=0..n,
0498 //                y[i]*z[i+1] - y[i+1]*z[i] = -(-1)^i*|A|  für i=0..n
0499 // auch |A| = y[i+1]*z[i] + y[i]*z[i+1], |B| = x[i+1]*z[i] + x[i]*z[i+1]
0500 // für i=0..n (Cramersche Regel), folgt
0501 // |A| = y[n]*z[n-1] + y[n-1]*z[n] >= y[n]*2*g + 0 = |v|*2*g,
0502 // |B| = x[n]*z[n-1] + x[n-1]*z[n] >= x[n]*2*g + 0 = |u|*2*g.)
0503
0504 // Liefert den kgV zweier Integers.
0505 // lcm(a,b)
0506 // > a,b: zwei Integers
0507 // < ergebnis: (lcm a b), ein Integer >=0
0508   extern const cl_I lcm (const cl_I& a, const cl_I& b);
0509
0510
0511 // Wurzel aus ganzen Zahlen
0512
0513 // Zieht die Wurzel (ISQRT x) aus einem Integer.
0514 // isqrt(x,&w)
0515 // > x: Integer (sollte >=0 sein)
0516 // < w: (isqrt x)
0517 // < ergebnis: true falls x Quadratzahl, false sonst
0518   extern bool isqrt (const cl_I& x, cl_I* w);
0519 // Wenn das boolesche Ergebnis uninteressant ist:
0520   inline const cl_I isqrt (const cl_I& x) { cl_I w; isqrt(x,&w); return w; }
0521
0522 // Stellt fest, ob ein Integer >=0 eine Quadratzahl ist.
0523 // sqrtp(x,&w)
0524 // > x: ein Integer >=0
0525 // < w: Integer (sqrt x) falls x Quadratzahl
0526 // < ergebnis: true      ..................., false sonst
0527   extern bool sqrtp (const cl_I& x, cl_I* w);
0528
0529 // Stellt fest, ob ein Integer >=0 eine n-te Potenz ist.
0530 // rootp(x,n,&w)
0531 // > x: ein Integer >=0
0532 // > n: ein Integer >0
0533 // < w: Integer (expt x (/ n)) falls x eine n-te Potenz
0534 // < ergebnis: true            ........................, false sonst
0535   extern bool rootp (const cl_I& x, uintL n, cl_I* w);
0536   extern bool rootp (const cl_I& x, const cl_I& n, cl_I* w);
0537
0538
0539 // max(x,y) liefert (max x y), wo x und y ganze Zahlen sind.
0540 extern const cl_I max (const cl_I& x, const cl_I& y);
0541
0542 // min(x,y) liefert (min x y), wo x und y ganze Zahlen sind.
0543 extern const cl_I min (const cl_I& x, const cl_I& y);
0544
0545 // signum(x) liefert (signum x), wo x eine ganze Zahl ist.
0546 extern const cl_I signum (const cl_I& x);
0547
0548
0549 // Multipliziert ein Integer mit 10 und addiert eine weitere Ziffer.
0550 // mul_10_plus_x(y,x)
0551 // > y: Integer Y (>=0)
0552 // > x: Ziffernwert X (>=0,<10)
0553 // < ergebnis: Integer Y*10+X (>=0)
0554 extern const cl_I mul_10_plus_x (const cl_I& y, unsigned char x);
0555
0556
0557 // 2-adische Inverse.
0558 // cl_recip2adic(n,x)
0559 // > n: >0
0560 // > x: Integer, ungerade
0561 // < ergebnis: n-Bit-Zahl y == (x mod 2^n)^-1, d.h. y*x == 1 mod 2^n
0562 extern const cl_I cl_recip2adic (uintL n, const cl_I& x);
0563
0564 // 2-adische Division.
0565 // cl_div2adic(n,x,y)
0566 // > n: >0
0567 // > x: Integer
0568 // > y: Integer, ungerade
0569 // < ergebnis: n-Bit-Zahl z == (x mod 2^n)/(y mod 2^n), d.h. z*y == x mod 2^n
0570 extern const cl_I cl_div2adic (uintL n, const cl_I& x, const cl_I& y);
0571
0572
0573 // numerator(r) liefert den Zähler des Integer r.
0574 inline const cl_I numerator (const cl_I& r)
0575     { return r; }
0576 // denominator(r) liefert den Nenner (> 0) des Integer r.
0577 inline const cl_I denominator (const cl_I& r)
0578     { (void)r; return 1; }
0579
0580
0581 // Konversion zu einem C "float".
0582 extern float float_approx (const cl_I& x);
0583
0584 // Konversion zu einem C "double".
0585 extern double double_approx (const cl_I& x);
0586
0587
0588 // random_I(randomstate,n) liefert zu einem Integer n>0 ein zufälliges
0589 // Integer x mit 0 <= x < n.
0590 // > randomstate: ein Random-State, wird verändert
0591 extern const cl_I random_I (random_state& randomstate, const cl_I& n);
0592
0593 inline const cl_I random_I (const cl_I& n)
0594     { return random_I(default_random_state,n); }
0595
0596 // testrandom_I(randomstate) liefert ein zufälliges Integer zum Testen.
0597 // > randomstate: ein Random-State, wird verändert
0598 extern const cl_I testrandom_I (random_state& randomstate);
0599
0600 inline const cl_I testrandom_I ()
0601     { return testrandom_I(default_random_state); }
0602
0603
0604 // This could be optimized to use in-place operations.
0605 inline cl_I& operator+= (cl_I& x, const cl_I& y) { return x = x + y; }
0606 inline cl_I& operator+= (cl_I& x, const int y) { return x = x + y; }
0607 inline cl_I& operator+= (cl_I& x, const unsigned int y) { return x = x + y; }
0608 inline cl_I& operator+= (cl_I& x, const long y) { return x = x + y; }
0609 inline cl_I& operator+= (cl_I& x, const unsigned long y) { return x = x + y; }
0610 inline cl_I& operator++ /* prefix */ (cl_I& x) { return x = plus1(x); }
0611 inline void operator++ /* postfix */ (cl_I& x, int dummy) { (void)dummy; x = plus1(x); }
0612 inline cl_I& operator-= (cl_I& x, const cl_I& y) { return x = x - y; }
0613 inline cl_I& operator-= (cl_I& x, const int y) { return x = x - y; }
0614 inline cl_I& operator-= (cl_I& x, const unsigned int y) { return x = x - y; }
0615 inline cl_I& operator-= (cl_I& x, const long y) { return x = x - y; }
0616 inline cl_I& operator-= (cl_I& x, const unsigned long y) { return x = x - y; }
0617 inline cl_I& operator-- /* prefix */ (cl_I& x) { return x = minus1(x); }
0618 inline void operator-- /* postfix */ (cl_I& x, int dummy) { (void)dummy; x = minus1(x); }
0619 inline cl_I& operator*= (cl_I& x, const cl_I& y) { return x = x * y; }
0620 inline cl_I& operator<<= (cl_I& x, sintC y) // assume 0 <= y < 2^(intCsize-1)
0621     { return x = x << y; }
0622 inline cl_I& operator<<= (cl_I& x, const cl_I& y) // assume y >= 0
0623     { return x = x << y; }
0624 inline cl_I& operator>>= (cl_I& x, sintC y) // assume 0 <= y < 2^(intCsize-1)
0625     { return x = x >> y; }
0626 inline cl_I& operator>>= (cl_I& x, const cl_I& y) // assume y >= 0
0627     { return x = x >> y; }
0628 #if 0 // Defining operator/ collides with the operator/ (cl_RA, cl_RA).
0629 // operator/ should perform exquo(x,y), but people believe in the C semantics.
0630 // And it would be wiser to use floor1 and mod instead of truncate1 and rem,
0631 // but again, many C compilers implement / and % like this and people believe
0632 // in it.
0633 inline const cl_I operator/ (const cl_I& x, const cl_I& y) { return truncate1(x,y); }
0634 inline const cl_I operator% (const cl_I& x, const cl_I& y) { return rem(x,y); }
0635 inline cl_I& operator/= (cl_I& x, const cl_I& y) { return x = x / y; }
0636 inline cl_I& operator%= (cl_I& x, const cl_I& y) { return x = x % y; }
0637 #endif
0638
0639
0640 // Runtime typing support.
0641 extern cl_class cl_class_fixnum;
0642 extern cl_class cl_class_bignum;
0643 CL_FORCE_LINK(cl_I_classes_dummy, cl_class_fixnum)
0644
0645
0646 // Debugging support.
0647 #ifdef CL_DEBUG
0648 extern int cl_I_debug_module;
0649 CL_FORCE_LINK(cl_I_debug_dummy, cl_I_debug_module)
0650 #endif
0651
0652 }  // namespace cln
0653
0654 #endif /* _CL_INTEGER_H */