include/cln/integer.h

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