#include "cln/number.h"
#include "cln/integer_class.h"
+#include "cln/exception.h"
#include "cln/random.h"
namespace cln {
inline unsigned int cl_I_to_uint (const cl_I& x) { return cl_I_to_UL(x); }
#endif
+// Convert an integer to a 64-bit 'quad' type.
+#ifdef intQsize
+ extern uint64 cl_I_to_UQ (const cl_I& obj);
+ extern sint64 cl_I_to_Q (const cl_I& obj);
+#endif
+
// Convert an integer to a C `long' or `unsigned long'.
#if (long_bitsize==32)
inline long cl_I_to_long (const cl_I& x) { return cl_I_to_L(x); }
inline unsigned long cl_I_to_ulong (const cl_I& x) { return cl_I_to_UL(x); }
#elif (long_bitsize==64)
- extern uint64 cl_I_to_UQ (const cl_I& obj);
- extern sint64 cl_I_to_Q (const cl_I& obj);
inline long cl_I_to_long (const cl_I& x) { return cl_I_to_Q(x); }
inline unsigned long cl_I_to_ulong (const cl_I& x) { return cl_I_to_UQ(x); }
#endif
+// Convert an integer to a counter type.
+#if (intCsize==long_bitsize)
+ inline uintC cl_I_to_UC (const cl_I& x) { return cl_I_to_ulong(x); }
+ inline sintC cl_I_to_C (const cl_I& x) { return cl_I_to_long(x); }
+#elif (intCsize==int_bitsize)
+ inline uintC cl_I_to_UC (const cl_I& x) { return cl_I_to_uint(x); }
+ inline sintC cl_I_to_C (const cl_I& x) { return cl_I_to_int(x); }
+#endif
+
+// Convert an integer to an exponent type.
+#if (intEsize==intLsize)
+ inline uintE cl_I_to_UE (const cl_I& x) { return cl_I_to_UL(x); }
+ inline sintE cl_I_to_E (const cl_I& x) { return cl_I_to_L(x); }
+#elif (intEsize==intQsize)
+ inline uintE cl_I_to_UE (const cl_I& x) { return cl_I_to_UQ(x); }
+ inline sintE cl_I_to_E (const cl_I& x) { return cl_I_to_Q(x); }
+#endif
+
// Logische Operationen auf Integers:
// Ergebnis Integer.
extern const cl_I lognot (const cl_I& x);
-// Konstanten für BOOLE:
+// Konstanten für BOOLE:
typedef enum {
boole_clr,
boole_set,
// Ergebnis Integer.
extern const cl_I boole (cl_boole op, const cl_I& x, const cl_I& y);
-// Prüft, ob (LOGTEST x y), wo x und y Integers sind.
+// Prüft, ob (LOGTEST x y), wo x und y Integers sind.
// (LOGTEST x y) = (NOT (ZEROP (LOGAND x y))).
// < ergebnis: /=0, falls ja; =0, falls nein.
-extern cl_boolean logtest (const cl_I& x, const cl_I& y);
+extern bool logtest (const cl_I& x, const cl_I& y);
-// Prüft, ob (LOGBITP x y), wo x und y Integers sind.
+// Prüft, ob (LOGBITP x y), wo x und y Integers sind.
// Ergebnis: /=0, wenn ja; =0, wenn nein.
-extern cl_boolean logbitp (uintL x, const cl_I& y);
-extern cl_boolean logbitp (const cl_I& x, const cl_I& y);
+extern bool logbitp (uintC x, const cl_I& y);
+extern bool logbitp (const cl_I& x, const cl_I& y);
-// Prüft, ob (ODDP x), wo x ein Integer ist.
+// Prüft, ob (ODDP x), wo x ein Integer ist.
// Ergebnis: /=0, falls ja; =0, falls nein.
-extern cl_boolean oddp (const cl_I& x);
+extern bool oddp (const cl_I& x);
-// Prüft, ob (EVENP x), wo x ein Integer ist.
+// Prüft, ob (EVENP x), wo x ein Integer ist.
// Ergebnis: /=0, falls ja; =0, falls nein.
-inline cl_boolean evenp (const cl_I& x)
- { return (cl_boolean) (!oddp(x)); }
+inline bool evenp (const cl_I& x)
+ { return !oddp(x); }
// (ASH x y), wo x und y Integers sind. Ergebnis Integer.
-extern const cl_I ash (const cl_I& x, sintL y);
+extern const cl_I ash (const cl_I& x, sintC y);
extern const cl_I ash (const cl_I& x, const cl_I& y);
-// (LOGCOUNT x), wo x ein Integer ist. Ergebnis uintL.
-extern uintL logcount (const cl_I& x);
+// Thrown when shift amount is too large.
+class ash_exception : public runtime_exception {
+public:
+ explicit ash_exception (const cl_I& badamount);
+};
+
+// (LOGCOUNT x), wo x ein Integer ist. Ergebnis uintC.
+extern uintC logcount (const cl_I& x);
-// (INTEGER-LENGTH x), wo x ein Integer ist. Ergebnis uintL.
-extern uintL integer_length (const cl_I& x);
+// (INTEGER-LENGTH x), wo x ein Integer ist. Ergebnis uintC.
+extern uintC integer_length (const cl_I& x);
-// (ORD2 x) = max{n>=0: 2^n | x }, wo x ein Integer /=0 ist. Ergebnis uintL.
-extern uintL ord2 (const cl_I& x);
+// (ORD2 x) = max{n>=0: 2^n | x }, wo x ein Integer /=0 ist. Ergebnis uintC.
+extern uintC ord2 (const cl_I& x);
// power2p(x) stellt fest, ob ein Integer x>0 eine Zweierpotenz ist.
// Ergebnis: n>0, wenn x=2^(n-1), 0 sonst.
-extern uintL power2p (const cl_I& x);
+extern uintC power2p (const cl_I& x);
inline const cl_I operator| (const cl_I& x, const cl_I& y)
{ return logior(x,y); }
{ return logand(x,y); }
inline const cl_I operator~ (const cl_I& x)
{ return lognot(x); }
-#ifdef WANT_OBFUSCATING_OPERATORS
// This could be optimized to use in-place operations.
inline cl_I& operator|= (cl_I& x, const cl_I& y) { return x = x | y; }
inline cl_I& operator^= (cl_I& x, const cl_I& y) { return x = x ^ y; }
inline cl_I& operator&= (cl_I& x, const cl_I& y) { return x = x & y; }
-#endif
// Addition/Subtraktion von Integers
// (+ x y), wo x und y Integers sind. Ergebnis Integer.
extern const cl_I operator+ (const cl_I& x, const cl_I& y);
-// Dem C++-Compiler muß man auch das Folgende sagen:
+// Dem C++-Compiler muß man auch das Folgende sagen:
inline const cl_I operator+ (const int x, const cl_I& y)
{ return cl_I(x) + y; }
inline const cl_I operator+ (const unsigned int x, const cl_I& y)
{ return cl_I(x) + y; }
inline const cl_I operator+ (const unsigned long x, const cl_I& y)
{ return cl_I(x) + y; }
+#ifdef HAVE_LONGLONG
+inline const cl_I operator+ (const long long x, const cl_I& y)
+ { return cl_I(x) + y; }
+inline const cl_I operator+ (const unsigned long long x, const cl_I& y)
+ { return cl_I(x) + y; }
+#endif
inline const cl_I operator+ (const cl_I& x, const int y)
{ return x + cl_I(y); }
inline const cl_I operator+ (const cl_I& x, const unsigned int y)
{ return x + cl_I(y); }
inline const cl_I operator+ (const cl_I& x, const unsigned long y)
{ return x + cl_I(y); }
+#ifdef HAVE_LONGLONG
+inline const cl_I operator+ (const cl_I& x, const long long y)
+ { return x + cl_I(y); }
+inline const cl_I operator+ (const cl_I& x, const unsigned long long y)
+ { return x + cl_I(y); }
+#endif
// (- x), wenn x ein Integer ist. Ergebnis Integer.
extern const cl_I operator- (const cl_I& x);
// (- x y), wo x und y Integers sind. Ergebnis Integer.
extern const cl_I operator- (const cl_I& x, const cl_I& y);
-// Dem C++-Compiler muß man auch das Folgende sagen:
+// Dem C++-Compiler muß man auch das Folgende sagen:
inline const cl_I operator- (const int x, const cl_I& y)
{ return cl_I(x) - y; }
inline const cl_I operator- (const unsigned int x, const cl_I& y)
{ return cl_I(x) - y; }
inline const cl_I operator- (const unsigned long x, const cl_I& y)
{ return cl_I(x) - y; }
+#ifdef HAVE_LONGLONG
+inline const cl_I operator- (const long long x, const cl_I& y)
+ { return cl_I(x) - y; }
+inline const cl_I operator- (const unsigned long long x, const cl_I& y)
+ { return cl_I(x) - y; }
+#endif
inline const cl_I operator- (const cl_I& x, const int y)
{ return x - cl_I(y); }
inline const cl_I operator- (const cl_I& x, const unsigned int y)
{ return x - cl_I(y); }
inline const cl_I operator- (const cl_I& x, const unsigned long y)
{ return x - cl_I(y); }
+#ifdef HAVE_LONGLONG
+inline const cl_I operator- (const cl_I& x, const long long y)
+ { return x - cl_I(y); }
+inline const cl_I operator- (const cl_I& x, const unsigned long long y)
+ { return x - cl_I(y); }
+#endif
// (abs x), wenn x ein Integer ist. Ergebnis Integer.
extern const cl_I abs (const cl_I& x);
// Shifts.
-inline const cl_I operator<< (const cl_I& x, sintL y) // assume 0 <= y < 2^31
+inline const cl_I operator<< (const cl_I& x, sintC y) // assume 0 <= y < 2^(intCsize-1)
{ return ash(x,y); }
inline const cl_I operator<< (const cl_I& x, const cl_I& y) // assume y >= 0
{ return ash(x,y); }
-inline const cl_I operator>> (const cl_I& x, sintL y) // assume 0 <= y < 2^31
+inline const cl_I operator>> (const cl_I& x, sintC y) // assume 0 <= y < 2^(intCsize-1)
{ return ash(x,-y); }
inline const cl_I operator>> (const cl_I& x, const cl_I& y) // assume y >= 0
{ return ash(x,-y); }
// Vergleich von Integers
// equal(x,y) vergleicht zwei Integers x und y auf Gleichheit.
-extern cl_boolean equal (const cl_I& x, const cl_I& y);
-// equal_hashcode(x) liefert einen equal-invarianten Hashcode für x.
+extern bool equal (const cl_I& x, const cl_I& y);
+// equal_hashcode(x) liefert einen equal-invarianten Hashcode für x.
extern uint32 equal_hashcode (const cl_I& x);
// compare(x,y) vergleicht zwei Integers x und y.
{ return compare(x,y)>0; }
// minusp(x) == (< x 0)
-extern cl_boolean minusp (const cl_I& x);
+extern bool minusp (const cl_I& x);
// plusp(x) == (> x 0)
-extern cl_boolean plusp (const cl_I& x);
+extern bool plusp (const cl_I& x);
// zerop(x) stellt fest, ob ein Integer = 0 ist.
-extern cl_boolean zerop (const cl_I& x);
+extern bool zerop (const cl_I& x);
// BYTE-Operationen auf Integers
struct cl_byte {
- uintL size;
- uintL position;
+ uintC size;
+ uintC position;
// Konstruktor:
- cl_byte (unsigned int s, unsigned int p) : size (s), position (p) {}
+ cl_byte (uintC s, uintC p) : size (s), position (p) {}
};
// (LDB byte n), wo n ein Integer ist.
extern const cl_I ldb (const cl_I& n, const cl_byte& b);
-// ldb_test(n,byte) führt (LDB-TEST byte n) aus, wobei n ein Integer ist.
-// Ergebnis: cl_false wenn nein (also alle fraglichen Bits =0), cl_true wenn ja.
-extern cl_boolean ldb_test (const cl_I& n, const cl_byte& b);
+// ldb_test(n,byte) führt (LDB-TEST byte n) aus, wobei n ein Integer ist.
+// Ergebnis: false wenn nein (also alle fraglichen Bits =0), true wenn ja.
+extern bool ldb_test (const cl_I& n, const cl_byte& b);
// (MASK-FIELD byte n), wo n ein Integer ist.
extern const cl_I mask_field (const cl_I& n, const cl_byte& b);
// (* x y), wo x und y Integers sind. Ergebnis Integer.
extern const cl_I operator* (const cl_I& x, const cl_I& y);
-// Dem C++-Compiler muß man auch das Folgende sagen:
+// Dem C++-Compiler muß man auch das Folgende sagen:
inline const cl_I operator* (const int x, const cl_I& y)
{ return cl_I(x) * y; }
inline const cl_I operator* (const unsigned int x, const cl_I& y)
{ return cl_I(x) * y; }
inline const cl_I operator* (const unsigned long x, const cl_I& y)
{ return cl_I(x) * y; }
+#ifdef HAVE_LONGLONG
+inline const cl_I operator* (const long long x, const cl_I& y)
+ { return cl_I(x) * y; }
+inline const cl_I operator* (const unsigned long long x, const cl_I& y)
+ { return cl_I(x) * y; }
+#endif
inline const cl_I operator* (const cl_I& x, const int y)
{ return x * cl_I(y); }
inline const cl_I operator* (const cl_I& x, const unsigned int y)
{ return x * cl_I(y); }
inline const cl_I operator* (const cl_I& x, const unsigned long y)
{ return x * cl_I(y); }
+#ifdef HAVE_LONGLONG
+inline const cl_I operator* (const cl_I& x, const long long y)
+ { return x * cl_I(y); }
+inline const cl_I operator* (const cl_I& x, const unsigned long long y)
+ { return x * cl_I(y); }
+#endif
// (EXPT x 2), wo x Integer ist.
extern const cl_I square (const cl_I& x);
extern const cl_I expt_pos (const cl_I& x, uintL y);
extern const cl_I expt_pos (const cl_I& x, const cl_I& y);
-// Fakultät (! n), wo n Fixnum >=0 ist. Ergebnis Integer.
+// Fakultät (! n), wo n Fixnum >=0 ist. Ergebnis Integer.
extern const cl_I factorial (uintL n);
-//CL_REQUIRE(cl_I_factorial)
// Double factorial (!! n), with n Fixnum >=0. Returns integer.
extern const cl_I doublefactorial (uintL n);
};
// Dividiert zwei Integers x,y >=0 und liefert den Quotienten x/y >=0.
-// Bei y=0 Error. Die Division muß aufgehen, sonst Error.
+// Bei y=0 Error. Die Division muß aufgehen, sonst Error.
// exquopos(x,y)
// > x,y: Integers >=0
// < ergebnis: Quotient x/y, ein Integer >=0
extern const cl_I exquopos (const cl_I& x, const cl_I& y);
// Dividiert zwei Integers x,y und liefert den Quotienten x/y.
-// Bei y=0 Error. Die Division muß aufgehen, sonst Error.
+// Bei y=0 Error. Die Division muß aufgehen, sonst Error.
// exquo(x,y)
// > x,y: Integers
// < ergebnis: Quotient x/y, ein Integer
extern const cl_I exquo (const cl_I& x, const cl_I& y);
+// Thrown when quotient is no integer.
+class exquo_exception : public runtime_exception {
+public:
+ exquo_exception (const cl_I& x, const cl_I& y);
+};
+
// mod(x,y) = (mod x y), wo x,y Integers sind.
extern const cl_I mod (const cl_I& x, const cl_I& y);
// > a,b: zwei Integers
// < ergebnis: (gcd a b), ein Integer >=0
extern const cl_I gcd (const cl_I& a, const cl_I& b);
- extern uint32 gcd (uint32 a, uint32 b);
+ extern uintV gcd (uintV a, uintV b);
// Liefert den ggT zweier Integers samt Beifaktoren.
// g = xgcd(a,b,&u,&v)
// > a,b: zwei Integers
// < u, v, g: Integers mit u*a+v*b = g >= 0
extern const cl_I xgcd (const cl_I& a, const cl_I& b, cl_I* u, cl_I* v);
-// Im Fall A/=0, B/=0 genügt das Ergebnis (g,u,v) den Ungleichungen:
+// Im Fall A/=0, B/=0 genügt das Ergebnis (g,u,v) den Ungleichungen:
// Falls |A| = |B| : g = |A|, u = (signum A), v = 0.
// Falls |B| | |A|, |B| < |A| : g = |B|, u = 0, v = (signum B).
// Falls |A| | |B|, |A| < |B| : g = |A|, u = (signum A), v = 0.
// --------------------------------------------
// g = z[n], |u|=x[n], |v|=y[n]
// n>=2, z[0] > ... > z[n-1] > z[n] = g, g | z[n-1], also z[n-1] >= 2*g.
-// Da aber mit (-1)^i*x[i]*|A| - (-1)^i*y[i]*|B| = z[i] für i=0..n+1
-// und x[i]*y[i+1] - x[i+1]*y[i] = (-1)^i für i=0..n,
-// x[i]*z[i+1] - x[i+1]*z[i] = (-1)^i*|B| für i=0..n,
-// y[i]*z[i+1] - y[i+1]*z[i] = -(-1)^i*|A| für i=0..n
+// Da aber mit (-1)^i*x[i]*|A| - (-1)^i*y[i]*|B| = z[i] für i=0..n+1
+// und x[i]*y[i+1] - x[i+1]*y[i] = (-1)^i für i=0..n,
+// x[i]*z[i+1] - x[i+1]*z[i] = (-1)^i*|B| für i=0..n,
+// y[i]*z[i+1] - y[i+1]*z[i] = -(-1)^i*|A| für i=0..n
// auch |A| = y[i+1]*z[i] + y[i]*z[i+1], |B| = x[i+1]*z[i] + x[i]*z[i+1]
-// für i=0..n (Cramersche Regel), folgt
+// für i=0..n (Cramersche Regel), folgt
// |A| = y[n]*z[n-1] + y[n-1]*z[n] >= y[n]*2*g + 0 = |v|*2*g,
// |B| = x[n]*z[n-1] + x[n-1]*z[n] >= x[n]*2*g + 0 = |u|*2*g.)
// isqrt(x,&w)
// > x: Integer (sollte >=0 sein)
// < w: (isqrt x)
-// < ergebnis: cl_true falls x Quadratzahl, cl_false sonst
- extern cl_boolean isqrt (const cl_I& x, cl_I* w);
+// < ergebnis: true falls x Quadratzahl, false sonst
+ extern bool isqrt (const cl_I& x, cl_I* w);
// Wenn das boolesche Ergebnis uninteressant ist:
inline const cl_I isqrt (const cl_I& x) { cl_I w; isqrt(x,&w); return w; }
// sqrtp(x,&w)
// > x: ein Integer >=0
// < w: Integer (sqrt x) falls x Quadratzahl
-// < ergebnis: cl_true ..................., cl_false sonst
- extern cl_boolean sqrtp (const cl_I& x, cl_I* w);
+// < ergebnis: true ..................., false sonst
+ extern bool sqrtp (const cl_I& x, cl_I* w);
// Stellt fest, ob ein Integer >=0 eine n-te Potenz ist.
// rootp(x,n,&w)
// > x: ein Integer >=0
// > n: ein Integer >0
// < w: Integer (expt x (/ n)) falls x eine n-te Potenz
-// < ergebnis: cl_true ........................, cl_false sonst
- extern cl_boolean rootp (const cl_I& x, uintL n, cl_I* w);
- extern cl_boolean rootp (const cl_I& x, const cl_I& n, cl_I* w);
+// < ergebnis: true ........................, false sonst
+ extern bool rootp (const cl_I& x, uintL n, cl_I* w);
+ extern bool rootp (const cl_I& x, const cl_I& n, cl_I* w);
// max(x,y) liefert (max x y), wo x und y ganze Zahlen sind.
extern const cl_I cl_div2adic (uintL n, const cl_I& x, const cl_I& y);
-// numerator(r) liefert den Zähler des Integer r.
+// numerator(r) liefert den Zähler des Integer r.
inline const cl_I numerator (const cl_I& r)
{ return r; }
// denominator(r) liefert den Nenner (> 0) des Integer r.
extern double double_approx (const cl_I& x);
-// random_I(randomstate,n) liefert zu einem Integer n>0 ein zufälliges
+// random_I(randomstate,n) liefert zu einem Integer n>0 ein zufälliges
// Integer x mit 0 <= x < n.
-// > randomstate: ein Random-State, wird verändert
+// > randomstate: ein Random-State, wird verändert
extern const cl_I random_I (random_state& randomstate, const cl_I& n);
inline const cl_I random_I (const cl_I& n)
{ return random_I(default_random_state,n); }
-// testrandom_I(randomstate) liefert ein zufälliges Integer zum Testen.
-// > randomstate: ein Random-State, wird verändert
+// testrandom_I(randomstate) liefert ein zufälliges Integer zum Testen.
+// > randomstate: ein Random-State, wird verändert
extern const cl_I testrandom_I (random_state& randomstate);
inline const cl_I testrandom_I ()
{ return testrandom_I(default_random_state); }
-#ifdef WANT_OBFUSCATING_OPERATORS
// This could be optimized to use in-place operations.
inline cl_I& operator+= (cl_I& x, const cl_I& y) { return x = x + y; }
inline cl_I& operator+= (cl_I& x, const int y) { return x = x + y; }
inline cl_I& operator-- /* prefix */ (cl_I& x) { return x = minus1(x); }
inline void operator-- /* postfix */ (cl_I& x, int dummy) { (void)dummy; x = minus1(x); }
inline cl_I& operator*= (cl_I& x, const cl_I& y) { return x = x * y; }
-inline cl_I& operator<<= (cl_I& x, sintL y) // assume 0 <= y < 2^31
+inline cl_I& operator<<= (cl_I& x, sintC y) // assume 0 <= y < 2^(intCsize-1)
{ return x = x << y; }
inline cl_I& operator<<= (cl_I& x, const cl_I& y) // assume y >= 0
{ return x = x << y; }
-inline cl_I& operator>>= (cl_I& x, sintL y) // assume 0 <= y < 2^31
+inline cl_I& operator>>= (cl_I& x, sintC y) // assume 0 <= y < 2^(intCsize-1)
{ return x = x >> y; }
inline cl_I& operator>>= (cl_I& x, const cl_I& y) // assume y >= 0
{ return x = x >> y; }
inline cl_I& operator/= (cl_I& x, const cl_I& y) { return x = x / y; }
inline cl_I& operator%= (cl_I& x, const cl_I& y) { return x = x % y; }
#endif
-#endif
// Runtime typing support.