include/cl_integer.h

   1 // Public integer operations.
   2
   3 #ifndef _CL_INTEGER_H
   4 #define _CL_INTEGER_H
   5
   6 #include "cl_number.h"
   7 #include "cl_integer_class.h"
   8 #include "cl_random.h"
   9
  10
  11 CL_DEFINE_AS_CONVERSION(cl_I)
  12
  13
  14 // Konversion Integer >=0, <2^32 nach uintL.
  15 // Wandelt Integer >=0 in Unsigned Longword um.
  16 // cl_I_to_UL(obj)
  17 // > obj: Integer, sollte >=0, <2^32 sein
  18 // < ergebnis: der Wert des Integer als 32-Bit-Zahl.
  19   extern uint32 cl_I_to_UL (const cl_I& obj);
  20
  21 // Konversion Integer >=-2^31, <2^31 nach sintL.
  22 // Wandelt Integer in Signed Longword um.
  23 // cl_I_to_L(obj)
  24 // > obj: Integer, sollte >=-2^31, <2^31 sein
  25 // < ergebnis: der Wert des Integer als 32-Bit-Zahl.
  26   extern sint32 cl_I_to_L (const cl_I& obj);
  27
  28 // Convert an integer to a C `int' or `unsigned int'.
  29 #if (int_bitsize==32)
  30   inline int          cl_I_to_int  (const cl_I& x) { return cl_I_to_L(x);  }
  31   inline unsigned int cl_I_to_uint (const cl_I& x) { return cl_I_to_UL(x); }
  32 #endif
  33
  34 // Convert an integer to a C `long' or `unsigned long'.
  35 #if (long_bitsize==32)
  36   inline long          cl_I_to_long  (const cl_I& x) { return cl_I_to_L(x);  }
  37   inline unsigned long cl_I_to_ulong (const cl_I& x) { return cl_I_to_UL(x); }
  38 #elif (long_bitsize==64)
  39   extern uint64 cl_I_to_UQ (const cl_I& obj);
  40   extern sint64 cl_I_to_Q (const cl_I& obj);
  41   inline long          cl_I_to_long  (const cl_I& x) { return cl_I_to_Q(x);  }
  42   inline unsigned long cl_I_to_ulong (const cl_I& x) { return cl_I_to_UQ(x); }
  43 #endif
  44
  45
  46 // Logische Operationen auf Integers:
  47
  48 // (LOGIOR x y), wenn x, y Integers sind.
  49 // Ergebnis Integer.
  50 extern const cl_I logior (const cl_I& x, const cl_I& y);
  51
  52 // (LOGXOR x y), wenn x, y Integers sind.
  53 // Ergebnis Integer.
  54 extern const cl_I logxor (const cl_I& x, const cl_I& y);
  55
  56 // (LOGAND x y), wenn x, y Integers sind.
  57 // Ergebnis Integer.
  58 extern const cl_I logand (const cl_I& x, const cl_I& y);
  59
  60 // (LOGEQV x y), wenn x, y Integers sind.
  61 // Ergebnis Integer.
  62 extern const cl_I logeqv (const cl_I& x, const cl_I& y);
  63
  64 // (LOGNAND x y), wenn x, y Integers sind.
  65 // Ergebnis Integer.
  66 extern const cl_I lognand (const cl_I& x, const cl_I& y);
  67
  68 // (LOGNOR x y), wenn x, y Integers sind.
  69 // Ergebnis Integer.
  70 extern const cl_I lognor (const cl_I& x, const cl_I& y);
  71
  72 // (LOGANDC2 x y), wenn x, y Integers sind.
  73 // Ergebnis Integer.
  74 extern const cl_I logandc2 (const cl_I& x, const cl_I& y);
  75
  76 // (LOGANDC1 x y), wenn x, y Integers sind.
  77 // Ergebnis Integer.
  78 inline const cl_I logandc1 (const cl_I& x, const cl_I& y)
  79 {
  80         return logandc2(y,x);
  81 }
  82
  83 // (LOGORC2 x y), wenn x, y Integers sind.
  84 // Ergebnis Integer.
  85 extern const cl_I logorc2 (const cl_I& x, const cl_I& y);
  86
  87 // (LOGORC1 x y), wenn x, y Integers sind.
  88 // Ergebnis Integer.
  89 inline const cl_I logorc1 (const cl_I& x, const cl_I& y)
  90 {
  91         return logorc2(y,x);
  92 }
  93
  94 // (LOGNOT x), wenn x ein Integer sind.
  95 // Ergebnis Integer.
  96 extern const cl_I lognot (const cl_I& x);
  97
  98 // Konstanten für BOOLE:
  99 typedef enum {
 100         boole_clr,
 101         boole_set,
 102         boole_1,
 103         boole_2,
 104         boole_c1,
 105         boole_c2,
 106         boole_and,
 107         boole_ior,
 108         boole_xor,
 109         boole_eqv,
 110         boole_nand,
 111         boole_nor,
 112         boole_andc1,
 113         boole_andc2,
 114         boole_orc1,
 115         boole_orc2
 116 } cl_boole;
 117
 118 // (BOOLE op x y), wenn x und y Integers und op ein Objekt sind.
 119 // Ergebnis Integer.
 120 extern const cl_I boole (cl_boole op, const cl_I& x, const cl_I& y);
 121
 122 // Prüft, ob (LOGTEST x y), wo x und y Integers sind.
 123 // (LOGTEST x y) = (NOT (ZEROP (LOGAND x y))).
 124 // < ergebnis: /=0, falls ja; =0, falls nein.
 125 extern cl_boolean logtest (const cl_I& x, const cl_I& y);
 126
 127 // Prüft, ob (LOGBITP x y), wo x und y Integers sind.
 128 // Ergebnis: /=0, wenn ja; =0, wenn nein.
 129 extern cl_boolean logbitp (uintL x, const cl_I& y);
 130 extern cl_boolean logbitp (const cl_I& x, const cl_I& y);
 131
 132 // Prüft, ob (ODDP x), wo x ein Integer ist.
 133 // Ergebnis: /=0, falls ja; =0, falls nein.
 134 extern cl_boolean oddp (const cl_I& x);
 135
 136 // Prüft, ob (EVENP x), wo x ein Integer ist.
 137 // Ergebnis: /=0, falls ja; =0, falls nein.
 138 inline cl_boolean evenp (const cl_I& x)
 139         { return (cl_boolean) (!oddp(x)); }
 140
 141 // (ASH x y), wo x und y Integers sind. Ergebnis Integer.
 142 extern const cl_I ash (const cl_I& x, sintL y);
 143 extern const cl_I ash (const cl_I& x, const cl_I& y);
 144
 145 // (LOGCOUNT x), wo x ein Integer ist. Ergebnis uintL.
 146 extern uintL logcount (const cl_I& x);
 147
 148 // (INTEGER-LENGTH x), wo x ein Integer ist. Ergebnis uintL.
 149 extern uintL integer_length (const cl_I& x);
 150
 151 // (ORD2 x) = max{n>=0: 2^n | x }, wo x ein Integer /=0 ist. Ergebnis uintL.
 152 extern uintL ord2 (const cl_I& x);
 153
 154 // power2p(x) stellt fest, ob ein Integer x>0 eine Zweierpotenz ist.
 155 // Ergebnis: n>0, wenn x=2^(n-1), 0 sonst.
 156 extern uintL power2p (const cl_I& x);
 157
 158 inline const cl_I operator| (const cl_I& x, const cl_I& y)
 159         { return logior(x,y); }
 160 inline const cl_I operator^ (const cl_I& x, const cl_I& y)
 161         { return logxor(x,y); }
 162 inline const cl_I operator& (const cl_I& x, const cl_I& y)
 163         { return logand(x,y); }
 164 inline const cl_I operator~ (const cl_I& x)
 165         { return lognot(x); }
 166 #ifdef WANT_OBFUSCATING_OPERATORS
 167 // This could be optimized to use in-place operations.
 168 inline cl_I& operator|= (cl_I& x, const cl_I& y) { return x = x | y; }
 169 inline cl_I& operator^= (cl_I& x, const cl_I& y) { return x = x ^ y; }
 170 inline cl_I& operator&= (cl_I& x, const cl_I& y) { return x = x & y; }
 171 #endif
 172
 173
 174 // Addition/Subtraktion von Integers
 175
 176 // (1+ x), wo x ein Integer ist. Ergebnis Integer.
 177 extern const cl_I plus1 (const cl_I& x);
 178
 179 // (1- x), wo x ein Integer ist. Ergebnis Integer.
 180 extern const cl_I minus1 (const cl_I& x);
 181
 182 // (+ x y), wo x und y Integers sind. Ergebnis Integer.
 183 extern const cl_I operator+ (const cl_I& x, const cl_I& y);
 184 // Dem C++-Compiler muß man auch das Folgende sagen:
 185 inline const cl_I operator+ (const int x, const cl_I& y)
 186         { return cl_I(x) + y; }
 187 inline const cl_I operator+ (const unsigned int x, const cl_I& y)
 188         { return cl_I(x) + y; }
 189 inline const cl_I operator+ (const long x, const cl_I& y)
 190         { return cl_I(x) + y; }
 191 inline const cl_I operator+ (const unsigned long x, const cl_I& y)
 192         { return cl_I(x) + y; }
 193 inline const cl_I operator+ (const cl_I& x, const int y)
 194         { return x + cl_I(y); }
 195 inline const cl_I operator+ (const cl_I& x, const unsigned int y)
 196         { return x + cl_I(y); }
 197 inline const cl_I operator+ (const cl_I& x, const long y)
 198         { return x + cl_I(y); }
 199 inline const cl_I operator+ (const cl_I& x, const unsigned long y)
 200         { return x + cl_I(y); }
 201
 202 // (- x), wenn x ein Integer ist. Ergebnis Integer.
 203 extern const cl_I operator- (const cl_I& x);
 204
 205 // (- x y), wo x und y Integers sind. Ergebnis Integer.
 206 extern const cl_I operator- (const cl_I& x, const cl_I& y);
 207 // Dem C++-Compiler muß man auch das Folgende sagen:
 208 inline const cl_I operator- (const int x, const cl_I& y)
 209         { return cl_I(x) - y; }
 210 inline const cl_I operator- (const unsigned int x, const cl_I& y)
 211         { return cl_I(x) - y; }
 212 inline const cl_I operator- (const long x, const cl_I& y)
 213         { return cl_I(x) - y; }
 214 inline const cl_I operator- (const unsigned long x, const cl_I& y)
 215         { return cl_I(x) - y; }
 216 inline const cl_I operator- (const cl_I& x, const int y)
 217         { return x - cl_I(y); }
 218 inline const cl_I operator- (const cl_I& x, const unsigned int y)
 219         { return x - cl_I(y); }
 220 inline const cl_I operator- (const cl_I& x, const long y)
 221         { return x - cl_I(y); }
 222 inline const cl_I operator- (const cl_I& x, const unsigned long y)
 223         { return x - cl_I(y); }
 224
 225 // (abs x), wenn x ein Integer ist. Ergebnis Integer.
 226 extern const cl_I abs (const cl_I& x);
 227
 228 // Shifts.
 229 inline const cl_I operator<< (const cl_I& x, sintL y) // assume 0 <= y < 2^31
 230         { return ash(x,y); }
 231 inline const cl_I operator<< (const cl_I& x, const cl_I& y) // assume y >= 0
 232         { return ash(x,y); }
 233 inline const cl_I operator>> (const cl_I& x, sintL y) // assume 0 <= y < 2^31
 234         { return ash(x,-y); }
 235 inline const cl_I operator>> (const cl_I& x, const cl_I& y) // assume y >= 0
 236         { return ash(x,-y); }
 237
 238
 239 // Vergleich von Integers
 240
 241 // cl_equal(x,y) vergleicht zwei Integers x und y auf Gleichheit.
 242 extern cl_boolean cl_equal (const cl_I& x, const cl_I& y);
 243 // cl_equal_hashcode(x) liefert einen cl_equal-invarianten Hashcode für x.
 244 extern uint32 cl_equal_hashcode (const cl_I& x);
 245
 246 // cl_compare(x,y) vergleicht zwei Integers x und y.
 247 // Ergebnis: 0 falls x=y, +1 falls x>y, -1 falls x<y.
 248 extern cl_signean cl_compare (const cl_I& x, const cl_I& y);
 249
 250 inline bool operator== (const cl_I& x, const cl_I& y)
 251         { return cl_equal(x,y); }
 252 inline bool operator!= (const cl_I& x, const cl_I& y)
 253         { return !cl_equal(x,y); }
 254 inline bool operator<= (const cl_I& x, const cl_I& y)
 255         { return cl_compare(x,y)<=0; }
 256 inline bool operator< (const cl_I& x, const cl_I& y)
 257         { return cl_compare(x,y)<0; }
 258 inline bool operator>= (const cl_I& x, const cl_I& y)
 259         { return cl_compare(x,y)>=0; }
 260 inline bool operator> (const cl_I& x, const cl_I& y)
 261         { return cl_compare(x,y)>0; }
 262
 263 // minusp(x) == (< x 0)
 264 extern cl_boolean minusp (const cl_I& x);
 265
 266 // plusp(x) == (> x 0)
 267 extern cl_boolean plusp (const cl_I& x);
 268
 269 // zerop(x) stellt fest, ob ein Integer = 0 ist.
 270 extern cl_boolean zerop (const cl_I& x);
 271
 272
 273 // BYTE-Operationen auf Integers
 274
 275 struct cl_byte {
 276         uintL size;
 277         uintL position;
 278 // Konstruktor:
 279         cl_byte (unsigned int s, unsigned int p) : size (s), position (p) {}
 280 };
 281
 282 // (LDB byte n), wo n ein Integer ist.
 283 extern const cl_I ldb (const cl_I& n, const cl_byte& b);
 284
 285 // ldb_test(n,byte) führt (LDB-TEST byte n) aus, wobei n ein Integer ist.
 286 // Ergebnis: cl_false wenn nein (also alle fraglichen Bits =0), cl_true wenn ja.
 287 extern cl_boolean ldb_test (const cl_I& n, const cl_byte& b);
 288
 289 // (MASK-FIELD byte n), wo n ein Integer ist.
 290 extern const cl_I mask_field (const cl_I& n, const cl_byte& b);
 291
 292 // (DEPOSIT-FIELD newbyte byte n), wo n und newbyte Integers sind.
 293 extern const cl_I deposit_field (const cl_I& newbyte, const cl_I& n, const cl_byte& b);
 294
 295 // (DPB newbyte byte n), wo n und newbyte Integers sind.
 296 extern const cl_I dpb (const cl_I& newbyte, const cl_I& n, const cl_byte& b);
 297
 298
 299 // Multiplikation ganzer Zahlen
 300
 301 // (* x y), wo x und y Integers sind. Ergebnis Integer.
 302 extern const cl_I operator* (const cl_I& x, const cl_I& y);
 303 // Dem C++-Compiler muß man auch das Folgende sagen:
 304 inline const cl_I operator* (const int x, const cl_I& y)
 305         { return cl_I(x) * y; }
 306 inline const cl_I operator* (const unsigned int x, const cl_I& y)
 307         { return cl_I(x) * y; }
 308 inline const cl_I operator* (const long x, const cl_I& y)
 309         { return cl_I(x) * y; }
 310 inline const cl_I operator* (const unsigned long x, const cl_I& y)
 311         { return cl_I(x) * y; }
 312 inline const cl_I operator* (const cl_I& x, const int y)
 313         { return x * cl_I(y); }
 314 inline const cl_I operator* (const cl_I& x, const unsigned int y)
 315         { return x * cl_I(y); }
 316 inline const cl_I operator* (const cl_I& x, const long y)
 317         { return x * cl_I(y); }
 318 inline const cl_I operator* (const cl_I& x, const unsigned long y)
 319         { return x * cl_I(y); }
 320
 321 // (EXPT x 2), wo x Integer ist.
 322 extern const cl_I square (const cl_I& x);
 323
 324 // (EXPT x y), wo x Integer, y Integer >0 ist.
 325 extern const cl_I expt_pos (const cl_I& x, uintL y);
 326 extern const cl_I expt_pos (const cl_I& x, const cl_I& y);
 327
 328 // Fakultät (! n), wo n Fixnum >=0 ist. Ergebnis Integer.
 329 extern const cl_I factorial (uintL n);
 330 //CL_REQUIRE(cl_I_factorial)
 331
 332 // Double factorial (!! n), with n Fixnum >=0.  Returns integer.
 333 extern const cl_I doublefactorial (uintL n);
 334
 335 // Binomialkoeffizient (n \choose k) = n! / k! (n-k)!, wo n,k >= 0 sind.
 336 extern const cl_I binomial (uintL n, uintL k);
 337
 338
 339 // Division ganzer Zahlen
 340
 341 // Return type for division operators.
 342 // x / y  --> (q,r) with x = y*q+r.
 343 struct cl_I_div_t {
 344         cl_I quotient;
 345         cl_I remainder;
 346 // Constructor.
 347         cl_I_div_t () {}
 348         cl_I_div_t (const cl_I& q, const cl_I& r) : quotient(q), remainder(r) {}
 349 };
 350
 351 // Dividiert zwei Integers x,y >=0 und liefert den Quotienten x/y >=0.
 352 // Bei y=0 Error. Die Division muß aufgehen, sonst Error.
 353 // exquopos(x,y)
 354 // > x,y: Integers >=0
 355 // < ergebnis: Quotient x/y, ein Integer >=0
 356   extern const cl_I exquopos (const cl_I& x, const cl_I& y);
 357
 358 // Dividiert zwei Integers x,y und liefert den Quotienten x/y.
 359 // Bei y=0 Error. Die Division muß aufgehen, sonst Error.
 360 // exquo(x,y)
 361 // > x,y: Integers
 362 // < ergebnis: Quotient x/y, ein Integer
 363   extern const cl_I exquo (const cl_I& x, const cl_I& y);
 364
 365 // mod(x,y) = (mod x y), wo x,y Integers sind.
 366   extern const cl_I mod (const cl_I& x, const cl_I& y);
 367
 368 // rem(x,y) = (rem x y), wo x,y Integers sind.
 369   extern const cl_I rem (const cl_I& x, const cl_I& y);
 370
 371 // Dividiert zwei Integers x,y und liefert Quotient und Rest
 372 // (q,r) := (floor x y)
 373 // floor2(x,y)
 374 // > x,y: Integers
 375 // < q,r: Quotient q, Rest r
 376   extern const cl_I_div_t floor2 (const cl_I& x, const cl_I& y);
 377   extern const cl_I floor1 (const cl_I& x, const cl_I& y);
 378
 379 // Dividiert zwei Integers x,y und liefert Quotient und Rest
 380 // (q,r) := (ceiling x y)
 381 // ceiling2(x,y)
 382 // > x,y: Integers
 383 // < q,r: Quotient q, Rest r
 384   extern const cl_I_div_t ceiling2 (const cl_I& x, const cl_I& y);
 385   extern const cl_I ceiling1 (const cl_I& x, const cl_I& y);
 386
 387 // Dividiert zwei Integers x,y und liefert Quotient und Rest
 388 // (q,r) := (truncate x y)
 389 // truncate2(x,y)
 390 // > x,y: Integers
 391 // < q,r: Quotient q, Rest r
 392   extern const cl_I_div_t truncate2 (const cl_I& x, const cl_I& y);
 393   extern const cl_I truncate1 (const cl_I& x, const cl_I& y);
 394
 395 // Dividiert zwei Integers x,y und liefert Quotient und Rest
 396 // (q,r) := (round x y)
 397 // round2(x,y)
 398 // > x,y: Integers
 399 // < q,r: Quotient q, Rest r
 400   extern const cl_I_div_t round2 (const cl_I& x, const cl_I& y);
 401   extern const cl_I round1 (const cl_I& x, const cl_I& y);
 402
 403
 404 // ggT und kgV von Integers
 405
 406 // Liefert den ggT zweier Integers.
 407 // gcd(a,b)
 408 // > a,b: zwei Integers
 409 // < ergebnis: (gcd a b), ein Integer >=0
 410   extern const cl_I gcd (const cl_I& a, const cl_I& b);
 411   extern uint32 gcd (uint32 a, uint32 b);
 412
 413 // Liefert den ggT zweier Integers samt Beifaktoren.
 414 // g = xgcd(a,b,&u,&v)
 415 // > a,b: zwei Integers
 416 // < u, v, g: Integers mit u*a+v*b = g >= 0
 417   extern const cl_I xgcd (const cl_I& a, const cl_I& b, cl_I* u, cl_I* v);
 418 // Im Fall A/=0, B/=0 genügt das Ergebnis (g,u,v) den Ungleichungen:
 419 //   Falls |A| = |B| : g = |A|, u = (signum A), v = 0.
 420 //   Falls |B| | |A|, |B| < |A| : g = |B|, u = 0, v = (signum B).
 421 //   Falls |A| | |B|, |A| < |B| : g = |A|, u = (signum A), v = 0.
 422 //   Sonst: |u| <= |B| / (2*g), |v| <= |A| / (2*g).
 423 //   In jedem Fall |u| <= |B|/g, |v| < |A|/g.
 424 // (Beweis: Im Prinzip macht man ja mehrere Euklid-Schritte auf einmal. Im
 425 // letzten Fall - oBdA |A| > |B| - braucht man mindestens zwei Euklid-Schritte,
 426 // also gilt im Euklid-Tableau
 427 //                 i         |A|            |B|         Erg.
 428 //                --------------------------------------------
 429 //                 0          1              0          |A|
 430 //                 1          0              1          |B|
 431 //                ...        ...            ...         ...
 432 //                n-1  -(-1)^n*x[n-1]  (-1)^n*y[n-1]   z[n-1]
 433 //                 n    (-1)^n*x[n]    -(-1)^n*y[n]     z[n]
 434 //                n+1  -(-1)^n*x[n+1]  (-1)^n*y[n+1]   z[n+1] = 0
 435 //                --------------------------------------------
 436 //                       g = z[n], |u|=x[n], |v|=y[n]
 437 // n>=2, z[0] > ... > z[n-1] > z[n] = g, g | z[n-1], also z[n-1] >= 2*g.
 438 // Da aber mit  (-1)^i*x[i]*|A| - (-1)^i*y[i]*|B| = z[i]  für i=0..n+1
 439 // und            x[i]*y[i+1] - x[i+1]*y[i] = (-1)^i  für i=0..n,
 440 //                x[i]*z[i+1] - x[i+1]*z[i] = (-1)^i*|B|  für i=0..n,
 441 //                y[i]*z[i+1] - y[i+1]*z[i] = -(-1)^i*|A|  für i=0..n
 442 // auch |A| = y[i+1]*z[i] + y[i]*z[i+1], |B| = x[i+1]*z[i] + x[i]*z[i+1]
 443 // für i=0..n (Cramersche Regel), folgt
 444 // |A| = y[n]*z[n-1] + y[n-1]*z[n] >= y[n]*2*g + 0 = |v|*2*g,
 445 // |B| = x[n]*z[n-1] + x[n-1]*z[n] >= x[n]*2*g + 0 = |u|*2*g.)
 446
 447 // Liefert den kgV zweier Integers.
 448 // lcm(a,b)
 449 // > a,b: zwei Integers
 450 // < ergebnis: (lcm a b), ein Integer >=0
 451   extern const cl_I lcm (const cl_I& a, const cl_I& b);
 452
 453
 454 // Wurzel aus ganzen Zahlen
 455
 456 // Zieht die Wurzel (ISQRT x) aus einem Integer.
 457 // isqrt(x,&w)
 458 // > x: Integer (sollte >=0 sein)
 459 // < w: (isqrt x)
 460 // < ergebnis: cl_true falls x Quadratzahl, cl_false sonst
 461   extern cl_boolean isqrt (const cl_I& x, cl_I* w);
 462 // Wenn das boolesche Ergebnis uninteressant ist:
 463   inline const cl_I isqrt (const cl_I& x) { cl_I w; isqrt(x,&w); return w; }
 464
 465 // Stellt fest, ob ein Integer >=0 eine Quadratzahl ist.
 466 // sqrtp(x,&w)
 467 // > x: ein Integer >=0
 468 // < w: Integer (sqrt x) falls x Quadratzahl
 469 // < ergebnis: cl_true   ..................., cl_false sonst
 470   extern cl_boolean sqrtp (const cl_I& x, cl_I* w);
 471
 472 // Stellt fest, ob ein Integer >=0 eine n-te Potenz ist.
 473 // rootp(x,n,&w)
 474 // > x: ein Integer >=0
 475 // > n: ein Integer >0
 476 // < w: Integer (expt x (/ n)) falls x eine n-te Potenz
 477 // < ergebnis: cl_true         ........................, cl_false sonst
 478   extern cl_boolean rootp (const cl_I& x, uintL n, cl_I* w);
 479   extern cl_boolean rootp (const cl_I& x, const cl_I& n, cl_I* w);
 480
 481
 482 // max(x,y) liefert (max x y), wo x und y ganze Zahlen sind.
 483 extern const cl_I max (const cl_I& x, const cl_I& y);
 484
 485 // min(x,y) liefert (min x y), wo x und y ganze Zahlen sind.
 486 extern const cl_I min (const cl_I& x, const cl_I& y);
 487
 488 // signum(x) liefert (signum x), wo x eine ganze Zahl ist.
 489 extern const cl_I signum (const cl_I& x);
 490
 491
 492 // Multipliziert ein Integer mit 10 und addiert eine weitere Ziffer.
 493 // mul_10_plus_x(y,x)
 494 // > y: Integer Y (>=0)
 495 // > x: Ziffernwert X (>=0,<10)
 496 // < ergebnis: Integer Y*10+X (>=0)
 497 extern const cl_I mul_10_plus_x (const cl_I& y, unsigned char x);
 498
 499
 500 // 2-adische Inverse.
 501 // cl_recip2adic(n,x)
 502 // > n: >0
 503 // > x: Integer, ungerade
 504 // < ergebnis: n-Bit-Zahl y == (x mod 2^n)^-1, d.h. y*x == 1 mod 2^n
 505 extern const cl_I cl_recip2adic (uintL n, const cl_I& x);
 506
 507 // 2-adische Division.
 508 // cl_div2adic(n,x,y)
 509 // > n: >0
 510 // > x: Integer
 511 // > y: Integer, ungerade
 512 // < ergebnis: n-Bit-Zahl z == (x mod 2^n)/(y mod 2^n), d.h. z*y == x mod 2^n
 513 extern const cl_I cl_div2adic (uintL n, const cl_I& x, const cl_I& y);
 514
 515
 516 // numerator(r) liefert den Zähler des Integer r.
 517 inline const cl_I numerator (const cl_I& r)
 518         { return r; }
 519 // denominator(r) liefert den Nenner (> 0) des Integer r.
 520 inline const cl_I denominator (const cl_I& r)
 521         { (void)r; return 1; }
 522
 523
 524 // Konversion zu einem C "float".
 525 extern float cl_float_approx (const cl_I& x);
 526
 527 // Konversion zu einem C "double".
 528 extern double cl_double_approx (const cl_I& x);
 529
 530
 531 // random_I(randomstate,n) liefert zu einem Integer n>0 ein zufälliges
 532 // Integer x mit 0 <= x < n.
 533 // > randomstate: ein Random-State, wird verändert
 534 extern const cl_I random_I (cl_random_state& randomstate, const cl_I& n);
 535
 536 inline const cl_I random_I (const cl_I& n)
 537         { return random_I(cl_default_random_state,n); }
 538
 539 // testrandom_I(randomstate) liefert ein zufälliges Integer zum Testen.
 540 // > randomstate: ein Random-State, wird verändert
 541 extern const cl_I testrandom_I (cl_random_state& randomstate);
 542
 543 inline const cl_I testrandom_I ()
 544         { return testrandom_I(cl_default_random_state); }
 545
 546
 547 #ifdef WANT_OBFUSCATING_OPERATORS
 548 // This could be optimized to use in-place operations.
 549 inline cl_I& operator+= (cl_I& x, const cl_I& y) { return x = x + y; }
 550 inline cl_I& operator+= (cl_I& x, const int y) { return x = x + y; }
 551 inline cl_I& operator+= (cl_I& x, const unsigned int y) { return x = x + y; }
 552 inline cl_I& operator+= (cl_I& x, const long y) { return x = x + y; }
 553 inline cl_I& operator+= (cl_I& x, const unsigned long y) { return x = x + y; }
 554 inline cl_I& operator++ /* prefix */ (cl_I& x) { return x = plus1(x); }
 555 inline void operator++ /* postfix */ (cl_I& x, int dummy) { (void)dummy; x = plus1(x); }
 556 inline cl_I& operator-= (cl_I& x, const cl_I& y) { return x = x - y; }
 557 inline cl_I& operator-= (cl_I& x, const int y) { return x = x - y; }
 558 inline cl_I& operator-= (cl_I& x, const unsigned int y) { return x = x - y; }
 559 inline cl_I& operator-= (cl_I& x, const long y) { return x = x - y; }
 560 inline cl_I& operator-= (cl_I& x, const unsigned long y) { return x = x - y; }
 561 inline cl_I& operator-- /* prefix */ (cl_I& x) { return x = minus1(x); }
 562 inline void operator-- /* postfix */ (cl_I& x, int dummy) { (void)dummy; x = minus1(x); }
 563 inline cl_I& operator*= (cl_I& x, const cl_I& y) { return x = x * y; }
 564 inline cl_I& operator<<= (cl_I& x, sintL y) // assume 0 <= y < 2^31
 565         { return x = x << y; }
 566 inline cl_I& operator<<= (cl_I& x, const cl_I& y) // assume y >= 0
 567         { return x = x << y; }
 568 inline cl_I& operator>>= (cl_I& x, sintL y) // assume 0 <= y < 2^31
 569         { return x = x >> y; }
 570 inline cl_I& operator>>= (cl_I& x, const cl_I& y) // assume y >= 0
 571         { return x = x >> y; }
 572 #if 0 // Defining operator/ collides with the operator/ (cl_RA, cl_RA).
 573 // operator/ should perform exquo(x,y), but people believe in the C semantics.
 574 // And it would be wiser to use floor1 and mod instead of truncate1 and rem,
 575 // but again, many C compilers implement / and % like this and people believe
 576 // in it.
 577 inline const cl_I operator/ (const cl_I& x, const cl_I& y) { return truncate1(x,y); }
 578 inline const cl_I operator% (const cl_I& x, const cl_I& y) { return rem(x,y); }
 579 inline cl_I& operator/= (cl_I& x, const cl_I& y) { return x = x / y; }
 580 inline cl_I& operator%= (cl_I& x, const cl_I& y) { return x = x % y; }
 581 #endif
 582 #endif
 583
 584
 585 // Runtime typing support.
 586 extern cl_class cl_class_fixnum;
 587 extern cl_class cl_class_bignum;
 588 static const void* const cl_I_classes_dummy[] = { &cl_I_classes_dummy,
 589         &cl_class_fixnum
 590 };
 591
 592
 593 // Debugging support.
 594 #ifdef CL_DEBUG
 595 extern int cl_I_debug_module;
 596 static void* const cl_I_debug_dummy[] = { &cl_I_debug_dummy,
 597         &cl_I_debug_module
 598 };
 599 #endif
 600
 601
 602 #endif /* _CL_INTEGER_H */