Makefile.in
+aclocal.m4
+configure
+missing
+ylwrap
+
+ - Ported class Integer from the Gnu libg++ library.
+
Oct 31, 2019 - Release 0.2
============================
--- /dev/null
+<?xml version="1.0"?>
+<chapter>
+<heading>Integer - Arbitrary length integer numbers</heading>
+<para>
+The <code>Integer</code> class provides multiple precision integer arithmetic
+facilities. Some representation details are discussed in the
+Representation section.
+</para>
+<para>
+<code>Integers</code> may be up to <code>b * ((1 << b) - 1)</code> bits long, where
+<code>b</code> is the number of bits per short (typically 1048560 bits when
+<code>b = 16</code>). The implementation assumes that a <code>long</code> is at least
+twice as long as a <code>short</code>. This assumption hides beneath almost all
+primitive operations, and would be very difficult to change. It also relies
+on correct behavior of <emph>unsigned</emph> arithmetic operations.
+</para>
+<para>
+Some of the arithmetic algorithms are very loosely based on those
+provided in the MIT Scheme <tt>`bignum.c'</tt> release, which is
+Copyright (c) 1987 Massachusetts Institute of Technology. Their use
+here falls within the provisions described in the Scheme release.
+</para>
+
+<section>
+<heading>Construction</heading>
+<para>
+Integers may be constructed in the following ways:
+</para>
+<description>
+<item tag="Integer x;">
+Declares an uninitialized Integer.
+</item>
+<item tag="Integer x = 2; Integer y(2);">
+Set x and y to the Integer value 2;
+</item>
+<item tag="Integer u(x); Integer v = x;">
+Set u and v to the same value as x.
+</item>
+</description>
+
+</section>
+
+<section>
+<heading>Conversion</heading>
+<description>
+<item tag="long as_long()">
+Used to coerce an <code>Integer</code> back into longs via the <code>long</code>
+coercion operator. If the Integer cannot fit into a long, this returns
+MINLONG or MAXLONG (depending on the sign) where MINLONG is the most
+negative, and MAXLONG is the most positive representable long.
+</item>
+<item tag="int fits_in_long()">
+Returns true iff the <code>Integer</code> is <code>< MAXLONG</code> and <code>> MINLONG</code>.
+</item>
+<item tag="double as_double()">
+Coerce the <code>Integer</code> to a <code>double</code>, with potential
+loss of precision.
+<code>+/-HUGE</code> is returned if the Integer cannot fit into a double.
+</item>
+<item tag="int fits_in_double()">
+Returns true iff the <code>Integer</code> can fit into a double.
+</item>
+</description>
+</section>
+
+<section>
+<heading>Operators</heading>
+<para>
+All of the usual arithmetic operators are provided (<code>+, -, *, /,
+%, +=, ++, -=, --, *=, /=, %=, ==, !=, <, <=, >, >=</code>). All operators
+support special versions for mixed arguments of Integers and regular
+C++ longs in order to avoid useless coercions, as well as to allow
+automatic promotion of shorts and ints to longs, so that they may be
+applied without additional Integer coercion operators. The only
+operators that behave differently than the corresponding int or long
+operators are <code>++</code> and <code>--</code>. Because C++ does not
+distinguish prefix from postfix application, these are declared as
+<code>void</code> operators, so that no confusion can result from applying
+them as postfix. Thus, for Integers x and y, <code> ++x; y = x; </code> is
+correct, but <code> y = ++x; </code> and <code> y = x++; </code> are not.
+</para>
+<para>
+Bitwise operators (<code>~</code>, <code>&</code>, <code>|</code>, <code>^</code>, <code><<</code>,
+<code>>></code>, <code>&=</code>, <code>|=</code>, <code>^=</code>, <code><<=</code>, <code>>>=</code>) are
+also provided. However, these operate on sign-magnitude, rather than
+two's complement representations. The sign of the result is arbitrarily
+taken as the sign of the first argument. For example, <code>Integer(-3)
+& Integer(5)</code> returns <code>Integer(-1)</code>, not -3, as it would using
+two's complement. Also, <code>~</code>, the complement operator, complements
+only those bits needed for the representation. Bit operators are also
+provided in the BitSet and BitString classes. One of these classes
+should be used instead of Integers when the results of bit manipulations
+are not interpreted numerically.
+</para>
+</section>
+
+<section>
+<heading>Functions</heading>
+<para>
+The following utility functions are also provided. (All arguments
+are Integers unless otherwise noted).
+</para>
+<description>
+<item tag="void divide(const Integer& x, const Integer& y, Integer& q, Integer& r)">
+Sets <emph>q</emph> to the quotient and <emph>r</emph> to the remainder of <emph>x</emph> and <emph>y</emph>.
+(<emph>q</emph> and <emph>r</emph> are returned by reference).
+</item>
+
+<item tag="Integer pow(const Integer& x, const Integer& p)">
+Returns <emph>x</emph> raised to the power <emph>p</emph>.
+</item>
+
+<item tag="Integer Ipow(long x, long p)">
+Returns <emph>x</emph> raised to the power <emph>p</emph>.
+</item>
+
+<item tag="Integer gcd(const Integer& x, const Integer& p)">
+Returns the greatest common divisor of <emph>x</emph> and <emph>y</emph>.
+</item>
+
+<item tag="Integer lcm(const Integer& x, const Integer& p)">
+Returns the least common multiple of <emph>x</emph> and <emph>y</emph>.
+</item>
+
+<item tag="Integer abs(const Integer& x)">
+Returns the absolute value of <emph>x</emph>.
+</item>
+
+<item tag="Method: void Integer::negate()">
+Negates <code>this</code> in place.
+</item>
+
+<item tag="Integer sqr(x)">
+returns x * x;
+</item>
+
+<item tag="Integer sqrt(x)">
+returns the floor of the square root of x.
+</item>
+
+<item tag="long lg(x)">
+returns the floor of the base 2 logarithm of abs(x)
+</item>
+
+<item tag="int sign(x)">
+returns -1 if x is negative, 0 if zero, else +1.
+Using <code>if (sign(x) == 0)</code> is a generally faster method
+of testing for zero than using relational operators.
+</item>
+
+<item tag="int even(x)">
+returns true if x is an even number
+</item>
+
+<item tag="int odd(x)">
+returns true if x is an odd number.
+</item>
+
+<item tag="void setbit(Integer& x, long b)">
+sets the b'th bit (counting right-to-left from zero) of x to 1.
+</item>
+
+<item tag="void clearbit(Integer& x, long b)">
+sets the b'th bit of x to 0.
+</item>
+
+<item tag="int testbit(Integer x, long b)">
+returns true if the b'th bit of x is 1.
+</item>
+
+<item tag="Integer atoI(char* asciinumber, int base = 10)">
+converts the base base char* string into its Integer form.
+</item>
+
+<item tag="void Integer::printon(ostream& s, int base = 10, int width = 0)">
+prints the ascii string value of <code>(*this)</code> as a base <code>base</code>
+number, in field width at least <code>width</code>.
+</item>
+
+<item tag="ostream << x">
+prints x in base ten format.
+</item>
+
+<item tag="istream >> x">
+reads x as a base ten number.
+</item>
+
+<item tag="int compare(Integer x, Integer y)">
+returns a negative number if x<y, zero if x==y, or positive if x>y.
+</item>
+
+<item tag="int ucompare(Integer x, Integer y)">
+like compare, but performs unsigned comparison.
+</item>
+
+<item tag="add(x, y, z)">
+A faster way to say z = x + y.
+</item>
+
+<item tag="sub(x, y, z)">
+A faster way to say z = x - y.
+</item>
+
+<item tag="mul(x, y, z)">
+A faster way to say z = x * y.
+</item>
+
+<item tag="div(x, y, z)">
+A faster way to say z = x / y.
+</item>
+
+<item tag="mod(x, y, z)">
+A faster way to say z = x % y.
+</item>
+
+<item tag="I_and(x, y, z)">
+A faster way to say z = x & y.
+</item>
+
+<item tag="I_or(x, y, z)">
+A faster way to say z = x | y.
+</item>
+
+<item tag="I_xor(x, y, z)">
+A faster way to say z = x ^ y.
+</item>
+
+<item tag="lshift(x, y, z)">
+A faster way to say z = x << y.
+</item>
+
+<item tag="rshift(x, y, z)">
+A faster way to say z = x >> y.
+</item>
+
+<item tag="pow(x, y, z)">
+A faster way to say z = pow(x, y).
+</item>
+
+<item tag="complement(x, z)">
+A faster way to say z = ~x.
+</item>
+
+<item tag="negate(x, z)">
+A faster way to say z = -x.
+</item>
+
+</description>
+
+</section>
+
+<section>
+<heading>SEE ALSO</heading>
+<para>
+<reference xml:link="simple"
+ href="https://www.slac.stanford.edu/comp/unix/gnu-info/libg++_toc.html#SEC31">
+The Integer class in the Gnu libg++ manual.
+</reference>
+</para>
+</section>
+</chapter>
.obj.eps:
tgif -print -eps -color $<
-XMLS = manual.xml string.xml date.xml hour.xml utc.xml
+XMLS = manual.xml string.xml date.xml hour.xml utc.xml Integer.xml
IMAGES=
PICTURES=
xmlns:xi="http://www.w3.org/2001/XInclude"/>
<xi:include href="utc.xml"
xmlns:xi="http://www.w3.org/2001/XInclude"/>
+ <xi:include href="Integer.xml"
+ xmlns:xi="http://www.w3.org/2001/XInclude"/>
</book>
</doc>
IntRep _MinusOneRep = {1, 0, 0, {1}};
+void lib_error_handler (const char* kind, const char* msg)
+{
+ fputs(kind, stderr);
+ fputs(" Error: ", stderr);
+ fputs(msg, stderr);
+ fputs("\n", stderr);
+ abort();
+}
+
+
+
// utilities to extract and transfer bits
// get low bits
int diff = 0;
const unsigned short* xs = &(x[l]);
const unsigned short* ys = &(y[l]);
- while (l-- > 0 && (diff = (*--xs) - (*--ys)) == 0);
+ while (l-- > 0 && diff == 0)
+ {
+ diff = (*--xs) - (*--ys);
+ }
return diff;
}
static inline void nonnil(const IntRep* rep)
{
if (rep == 0)
- (*lib_error_handler)("Integer", "operation on uninitialized Integer");
+ lib_error_handler("Integer", "operation on uninitialized Integer");
}
// allocate a new Irep. Pad to something close to a power of two.
while (allocsiz < siz) allocsiz <<= 1; // find a power of 2
allocsiz -= MALLOC_MIN_OVERHEAD;
if (allocsiz >= MAXIntRep_SIZE * sizeof(short))
- (*lib_error_handler)("Integer", "Requested length out of range");
+ lib_error_handler("Integer", "Requested length out of range");
IntRep* rep = (IntRep *) new char[allocsiz];
rep->sz = (allocsiz - sizeof(IntRep) + sizeof(short)) / sizeof(short);
unsigned short src[SHORT_PER_LONG];
unsigned short srclen = 0;
- while (x != 0)
+ do
{
src[srclen++] = extract(x);
x = down(x);
}
+ while (x != 0);
IntRep* rep;
if (old == 0 || srclen > old->sz)
int xsgn = x->sgn;
if (y == 0)
{
- if (xl == 0)
+ if (xl == 0 || xl == 1 && x->s[0] == 0)
return 0;
else if (xsgn == I_NEGATIVE)
return -1;
nonnil(y);
int xl = x->len;
int yl = y->len;
- if (yl == 0) (*lib_error_handler)("Integer", "attempted division by zero");
+ if (yl == 0) lib_error_handler("Integer", "attempted division by zero");
int comp = ucompare(x, y);
int xsgn = x->sgn;
{
nonnil(x);
int xl = x->len;
- if (y == 0) (*lib_error_handler)("Integer", "attempted division by zero");
+ if (y == 0) lib_error_handler("Integer", "attempted division by zero");
unsigned short ys[SHORT_PER_LONG];
unsigned long u;
nonnil(x);
IntRep* q = Iq.rep;
int xl = x->len;
- if (y == 0) (*lib_error_handler)("Integer", "attempted division by zero");
+ if (y == 0) lib_error_handler("Integer", "attempted division by zero");
unsigned short ys[SHORT_PER_LONG];
unsigned long u;
int xl = x->len;
int yl = y->len;
if (yl == 0)
- (*lib_error_handler)("Integer", "attempted division by zero");
+ lib_error_handler("Integer", "attempted division by zero");
int comp = ucompare(x, y);
int xsgn = x->sgn;
nonnil(y);
int xl = x->len;
int yl = y->len;
- if (yl == 0) (*lib_error_handler)("Integer", "attempted division by zero");
+ if (yl == 0) lib_error_handler("Integer", "attempted division by zero");
int comp = ucompare(x, y);
int xsgn = x->sgn;
{
nonnil(x);
int xl = x->len;
- if (y == 0) (*lib_error_handler)("Integer", "attempted division by zero");
+ if (y == 0) lib_error_handler("Integer", "attempted division by zero");
unsigned short ys[SHORT_PER_LONG];
unsigned long u;
}
+long lg(unsigned long x)
+{
+ long l = 0;
+ while (x > 1)
+ {
+ x = x >> 1;
+ ++l;
+ }
+ return l;
+}
long lg(const IntRep* x)
{
int width, int align_right, char fillchar, char Xcase,
int showpos)
{
+
char* e = fmt + fmtlen - 1;
char* s = e;
*--s = 0;
Icheck(z);
if (z->len == 0)
{
- while (rem != 0)
+ while (rem != 0 || *s == '\0')
{
char ch = rem % base;
rem /= base;
}
if (x->sgn == I_NEGATIVE) *--s = '-';
else if (showpos) *--s = '+';
+
int w = e - s - 1;
if (!align_right || w >= width)
{
void Integer::error(const char* msg) const
{
- (*lib_error_handler)("Integer", msg);
+ lib_error_handler("Integer", msg);
}
public:
Integer();
Integer(long);
+ Integer(int);
Integer(unsigned long);
Integer(IntRep*);
Integer(const Integer&);
~Integer();
+// for debugging
+ unsigned short len() { return rep->len; }
+ unsigned short *numbers () { return rep->s; }
+
+
void operator = (const Integer&);
void operator = (long);
int operator == (const Integer&, const Integer&);
int operator == (const Integer&, long);
+ int operator == (const Integer&, int);
int operator != (const Integer&, const Integer&);
int operator != (const Integer&, long);
int operator < (const Integer&, const Integer&);
typedef Integer IntTmp; // for backward compatibility
-inline Integer::Integer() :rep(&_ZeroRep) {}
+inline Integer::Integer()
+{
+ rep = &_ZeroRep;
+}
inline Integer::Integer(IntRep* r) :rep(r) {}
inline Integer::Integer(long y) :rep(Icopy_long(0, y)) {}
+inline Integer::Integer(int y) :rep(Icopy_long(0, long(y))) {}
+
inline Integer::Integer(unsigned long y) :rep(Icopy_ulong(0, y)) {}
inline Integer::Integer(const Integer& y) :rep(Icopy(0, y.rep)) {}
return compare(x, y) == 0;
}
+inline int operator == (const Integer& x, int y)
+{
+ return compare(x, long(y)) == 0;
+}
+
inline int operator != (const Integer& x, const Integer& y)
{
return compare(x, y) != 0;
extern _VOLATILE_VOID default_one_arg_error_handler(const char*);
extern _VOLATILE_VOID default_two_arg_error_handler(const char*, const char*);
-extern two_arg_error_handler_t lib_error_handler;
-
extern two_arg_error_handler_t
set_lib_error_handler(two_arg_error_handler_t f);
check_PROGRAMS = string_assign string_basics string_compare string_cat string_substring string_regex \
date_assign date_parse date_compare date_arithmetic date_attributes date_check_today \
hour_assign hour_parse hour_compare hour_arithmetic hour_check_now \
- utc_assign utc_compare utc_arithmetic
+ utc_assign utc_compare utc_arithmetic \
+ integer_assign integer_factorial integer_fibonacci integer_pow64 integer_modulo
string_assign_SOURCES = string_assign.cpp
string_basics_SOURCES = string_basics.cpp
utc_assign_SOURCES = utc_assign.cpp
utc_compare_SOURCES = utc_compare.cpp
utc_arithmetic_SOURCES = utc_arithmetic.cpp
+
+integer_assign_SOURCES = integer_assign.cpp
+integer_factorial_SOURCES = integer_factorial.cpp tInteger.cpp
+integer_fibonacci_SOURCES = integer_fibonacci.cpp tInteger.cpp
+integer_pow64_SOURCES = integer_pow64.cpp tInteger.cpp
+integer_modulo_SOURCES = integer_modulo.cpp tInteger.cpp
--- /dev/null
+/*******************************************************
+ * Unit test for the Integer class
+ *
+ * test contrustor and assignment of Integer objects
+ ******************************************************
+ *
+ */
+
+#include "Integer.h"
+#include <assert.h>
+
+int main()
+{
+ // Default contructor: all zero
+ Integer i0;
+
+ std::cout << "The default contructor makes a zero number: \"" << i0 << "\"\n";
+ std::cout.flush();
+ assert(i0 == 0);
+
+ // Constructors with a literal value
+ Integer i1(5);
+
+ std::cout << "Contructor with a number = 5: \"" << i1 << "\"\n";
+ std::cout.flush();
+ assert(i1 == 5);
+
+ // Initializer with a literal value
+ Integer i2 = 42;
+
+ std::cout << "Initializer with a number = 42: \"" << i2 << "\"\n";
+ std::cout.flush();
+ assert(i2 == 42);
+
+ // Assignment of a literal value
+ Integer i3;
+ i3 = 123;
+
+ std::cout << "Assignment with a number = 123: \"" << i3 << "\"\n";
+ std::cout.flush();
+ assert(i3 == 123);
+
+ // Contructor with an Integer object
+ Integer i4(i2);
+
+ std::cout << "Contructor with Integer: \"" << i4 << "\"\n";
+ std::cout.flush();
+ assert(i4 == i2);
+
+ // Assignment of a Integer object
+ Integer i5;
+ i5 = i3;
+
+ std::cout << "Assignment with Integer: \"" << i5 << "\"\n";
+ std::cout.flush();
+ assert(i5 == i3);
+
+ return 0;
+}
+
--- /dev/null
+/*******************************************************
+ * Unit test for the Integer class
+ *
+ * test several functions with a factorial calculation
+ ******************************************************
+ *
+ */
+
+#include "Integer.h"
+#include <assert.h>
+
+
+void facttest(Integer& one, Integer& two);
+
+int main()
+{
+ Integer one = 1;
+ std::cout << "one = " << one << "\n";
+ assert(one.OK());
+ assert(one == 1);
+ std::cout << "one + 1 = " << (one + long(1)) << "\n";
+
+ Integer two = 2;
+ std::cout << "two = " << two << "\n";
+ assert(two.OK());
+ assert(two == 2);
+
+ facttest(one, two);
+ //anothertest();
+ //iotest();
+ //modtest();
+
+ std::cout << "\nEnd of test\n";
+}
--- /dev/null
+one = 1
+one + 1 = 2
+two = 2
+fact30 = factorial(30) = 265252859812191058636308480000000
+fact28 = factorial(28) = 304888344611713860501504000000
+fact30 + fact28 = 265557748156802772496809984000000
+fact30 - fact28 = 264947971467579344775806976000000
+fact30 * fact28 = 80872505331661933764010628483512781121876047953920000000000000
+fact30 / fact28 = 870
+fact30 % fact28 = 0
+-fact30 = -265252859812191058636308480000000
+lg(fact30) = 107
+gcd(fact30, fact28) = 304888344611713860501504000000
+sqrt(fact30) = 16286585271694955
+negfact31 = -8222838654177922817725562880000000
+fact30 + negfact31 = -7957585794365731759089254400000000
+fact30 - negfact31 = 8488091513990113876361871360000000
+fact30 * negfact31 = -2181131468794922353615366650200339706856997013317222400000000000000
+fact30 / negfact31 = 0
+fact30 % negfact31 = 265252859812191058636308480000000
+gcd(fact30, negfact31) = 265252859812191058636308480000000
+
+End of test
+PASS integer_factorial (exit status: 0)
--- /dev/null
+/*******************************************************
+ * Unit test for the Integer class
+ *
+ * test several functions with a fibonacci calculation
+ ******************************************************
+ *
+ */
+
+#include "Integer.h"
+#include <assert.h>
+
+
+void fibtest();
+
+int main()
+{
+ Integer one = 1;
+ std::cout << "one = " << one << "\n";
+ assert(one.OK());
+ assert(one == 1);
+ std::cout << "one + 1 = " << (one + long(1)) << "\n";
+
+ Integer two = 2;
+ std::cout << "two = " << two << "\n";
+ assert(two.OK());
+ assert(two == 2);
+
+ fibtest();
+ //anothertest();
+ //iotest();
+ //modtest();
+
+ std::cout << "\nEnd of test\n";
+}
--- /dev/null
+one = 1
+one + 1 = 2
+two = 2
+fib50 = fibonacci(50) = 12586269025
+fib48 = fibonacci(48) = 4807526976
+fib48 + fib50 = 17393796001
+fib48 - fib50 = -7778742049
+fib48 * fib50 = 60508827864880718400
+fib48 / fib50 = 0
+fib48 % fib50 = 4807526976
+gcd(fib50, fib48) = 1
+sqrt(fib50) = 112188
+
+End of test
+PASS integer_fibonacci (exit status: 0)
--- /dev/null
+/*******************************************************
+ * Unit test for the Integer class
+ *
+ * test the Integer modulo function
+ ******************************************************
+ *
+ */
+
+#include "Integer.h"
+#include <assert.h>
+
+
+void modtest();
+
+int main()
+{
+ modtest();
+
+ std::cout << "\nEnd of test\n";
+}
--- /dev/null
+2^32 = 4294967296
+2^32 % (2^32-1) = 1
+2^32 % (2^32-1) = 1
+
+End of test
+PASS integer_modulo (exit status: 0)
--- /dev/null
+/*******************************************************
+ * Unit test for the Integer class
+ *
+ * test cases with 2 ^ 64 numbers
+ ******************************************************
+ *
+ */
+
+#include "Integer.h"
+#include <assert.h>
+
+
+void anothertest();
+
+int main()
+{
+ anothertest();
+ //modtest();
+
+ std::cout << "\nEnd of test\n";
+}
--- /dev/null
+pow64 = Ipow(2, 64) = 18446744073709551616
+lg(pow64) = 64
+s64 = 1 << 64 = 18446744073709551616
+s32 = s64 >> 32 = 4294967296
+comps64 = ~s64 = 18446744073709551615
+comps64 & s32 = 4294967296
+comps64 | s32 = 18446744073709551615
+comps64 ^ s32 = 18446744069414584319
+
+End of test
+PASS integer_pow64 (exit status: 0)
--- /dev/null
+/*
+ a test file for Integer class
+ */
+
+#include <Integer.h>
+#include <assert.h>
+
+Integer factorial(Integer n)
+{
+ Integer f;
+ if (n < long(0))
+ f = 0;
+ else
+ {
+ f = 1;
+ while (n > long(0))
+ {
+ f *= n;
+ --n;
+ }
+ }
+ return f;
+}
+
+Integer fibonacci(long n)
+{
+ Integer f;
+ if (n <= 0)
+ f = 0;
+ else
+ {
+ f = 1;
+ Integer prev = 0;
+ Integer tmp;
+ while (n > 1)
+ {
+ tmp = f;
+ f += prev;
+ prev = tmp;
+ --n;
+ }
+ }
+ return f;
+}
+
+
+void identitytest(Integer& a, Integer& b, Integer& c)
+{
+ assert( -(-a) == a);
+ assert( (a + b) == (b + a));
+ assert( (a + (-b)) == (a - b));
+ assert( (a * b) == (b * a));
+ assert( (a * (-b)) == -(a * b));
+ assert( (a / (-b)) == -(a / b));
+ assert( (a - b) == -(b - a));
+ assert( (a + (b + c)) == ((a + b) + c));
+ assert( (a * (b * c)) == ((a * b) * c));
+ assert( (a * (b + c)) == ((a * b) + (a * c)));
+ assert( ((a - b) + b) == a);
+ assert( ((a + b) - b) == a);
+ assert( ((a * b) / b) == a);
+ assert( ((a * b) % b) == 0);
+ assert( (b * (a / b) + (a % b)) == a);
+ assert( ((a + b) % c) == ((a % c) + (b % c)) % c);
+}
+
+void utiltest(Integer& a)
+{
+ assert(sqrt(sqr(a)) == a);
+ assert(sqr(sqrt(a)) <= a);
+
+ Integer x = 1;
+ for (int i = 0; i < 10; ++i)
+ {
+ assert(pow(a, i) == x);
+ x *= a;
+ }
+ setbit(x, 0);
+ assert(testbit(x, 0));
+ assert(odd(x));
+ assert(!even(x));
+ clearbit(x, 0);
+ clearbit(x, 1);
+ assert(even(x));
+ assert(!odd(x));
+ assert(x % long(4) == 0);
+
+}
+
+void bittest(Integer& a, Integer& b, Integer& c)
+{
+ assert( (a | b) == (b | a));
+ assert( (a & b) == (b & a));
+ assert( (a ^ b) == (b ^ a));
+ assert( (a | (b | c)) == ((a | b) | c));
+ assert( (a & (b & c)) == ((a & b) & c));
+ assert( (a & (b | c)) == ((a & b) | (a & c)));
+ assert( (a | (b & c)) == ((a | b) & (a | c)));
+ assert( (a & (a | b)) == a);
+ assert( (a | (a & b)) == a);
+}
+
+void accumtest(Integer& a, Integer& b, Integer& c)
+{
+ Integer x = a;
+ x *= b;
+ assert(x == (a * b));
+ x += c;
+ assert(x == ((a * b) + c));
+ x -= a;
+ assert(x == (((a * b) + c) - a));
+ x /= b;
+ assert(x == ((((a * b) + c) - a) / b));
+ x %= c;
+ assert(x == (((((a * b) + c) - a) / b) % c));
+ x &= a;
+ assert(x == ((((((a * b) + c) - a) / b) % c) & a));
+ x |= b;
+ assert(x == (((((((a * b) + c) - a) / b) % c) & a) | b));
+ x ^= c;
+ assert(x == ((((((((a * b) + c) - a) / b) % c) & a) | b) ^ c));
+
+ assert(x.OK());
+}
+
+void longidentitytest(Integer& a, long b, long c)
+{
+ assert( (a + b) == (b + a));
+ assert( (a + (-b)) == (a - b));
+ assert( (a * b) == (b * a));
+ assert( (a * (-b)) == -(a * b));
+ assert( (a / (-b)) == -(a / b));
+ assert( (a - b) == -(b - a));
+ assert( (a + (b + c)) == ((a + b) + c));
+ assert( (a * (b * c)) == ((a * b) * c));
+ assert( (a * (b + c)) == ((a * b) + (a * c)));
+ assert( ((a - b) + b) == a);
+ assert( ((a + b) - b) == a);
+ assert( ((a * b) / b) == a);
+ assert( ((a * b) % b) == 0);
+ assert( (b * (a / b) + (a % b)) == a);
+ assert( ((a + b) % c) == ((a % c) + (b % c)) % c);
+}
+
+void longbittest(Integer& a, long b, long c)
+{
+ assert( (a | b) == (b | a));
+ assert( (a & b) == (b & a));
+ assert( (a ^ b) == (b ^ a));
+ assert( (a | (b | c)) == ((a | b) | c));
+ assert( (a & (b & c)) == ((a & b) & c));
+ assert( (a & (b | c)) == ((a & b) | (a & c)));
+ assert( (a | (b & c)) == ((a | b) & (a | c)));
+ assert( (a & (a | b)) == a);
+ assert( (a | (a & b)) == a);
+}
+
+void longaccumtest(Integer& a, long b, long c)
+{
+ Integer x = a;
+ x *= b;
+ assert(x == (a * b));
+ x += c;
+ assert(x == ((a * b) + c));
+ x -= a;
+ assert(x == (((a * b) + c) - a));
+ x /= b;
+ assert(x == ((((a * b) + c) - a) / b));
+ x %= c;
+ assert(x == (((((a * b) + c) - a) / b) % c));
+ x &= a;
+ assert(x == ((((((a * b) + c) - a) / b) % c) & a));
+ x |= b;
+ assert(x == (((((((a * b) + c) - a) / b) % c) & a) | b));
+ x ^= c;
+ assert(x == ((((((((a * b) + c) - a) / b) % c) & a) | b) ^ c));
+
+ assert(x.OK());
+}
+
+void anothertest()
+{
+ long k;
+
+ Integer pow64 = Ipow(2, 64);
+ std::cout << "pow64 = Ipow(2, 64) = " << pow64 << "\n";
+ assert(pow64.OK());
+ std::cout << "lg(pow64) = " << lg(pow64) << "\n";
+ assert(lg(pow64) == 64);
+
+ for (k = 0; k < 64; ++k)
+ assert(testbit(pow64, k) == 0);
+
+ assert(testbit(pow64, k) != 0);
+
+ Integer s64 = 1;
+ s64 <<= 64;
+ std::cout << "s64 = 1 << 64 = " << s64 << "\n";
+ assert(s64.OK());
+
+ assert(s64 == pow64);
+ assert(s64 >= pow64);
+ assert(s64 <= pow64);
+ assert(!(s64 != pow64));
+ assert(!(s64 > pow64));
+ assert(!(s64 < pow64));
+
+ Integer s32 = s64 >> long(32);
+ std::cout << "s32 = s64 >> 32 = " << s32 << "\n";
+ assert(s32.OK());
+ assert(lg(s32) == 32);
+ assert(!(pow64 == s32));
+ assert(!(pow64 < s32));
+ assert(!(pow64 <= s32));
+ assert(pow64 != s32);
+ assert(pow64 >= s32);
+ assert(pow64 > s32);
+
+ Integer comps64 = ~s64;
+ std::cout << "comps64 = ~s64 = " << comps64 << "\n";
+ for (k = 0; k < 64; ++k) assert(testbit(comps64, k) == !testbit(s64, k));
+ Integer result = (comps64 & s32);
+ std::cout << "comps64 & s32 = " << result << "\n";
+ assert(result.OK());
+ result = (comps64 | s32);
+ std::cout << "comps64 | s32 = " << result << "\n";
+ assert(result.OK());
+ result = (comps64 ^ s32);
+ std::cout << "comps64 ^ s32 = " << result << "\n";
+ assert(result.OK());
+
+ identitytest(s64, s32, comps64);
+ bittest(s32, s64, comps64);
+ accumtest(comps64, s32, pow64);
+ utiltest(s32);
+ longidentitytest(s64, 1000, 50);
+ longbittest(s64, 12345, 67890);
+ longaccumtest(s32, 100000, 1);
+
+}
+
+void iotest()
+{
+ Integer result;
+ std::cout << "\nenter an Integer: ";
+ std::cin >> result;
+ std::cout << "number = " << result << "\n";
+ assert(result.OK());
+}
+
+void fibtest()
+{
+ Integer fib50 = fibonacci(50);
+ std::cout << "fib50 = fibonacci(50) = " << fib50 << "\n";
+ assert(fib50.OK());
+ Integer fib48 = fibonacci(48);
+ std::cout << "fib48 = fibonacci(48) = " << fib48 << "\n";
+ assert(fib48.OK());
+
+ Integer result = fib48 + fib50;
+ std::cout << "fib48 + fib50 = " << result << "\n";
+ result = fib48 - fib50;
+ std::cout << "fib48 - fib50 = " << result << "\n";
+ result = fib48 * fib50;
+ std::cout << "fib48 * fib50 = " << result << "\n";
+ result = fib48 / fib50;
+ std::cout << "fib48 / fib50 = " << result << "\n";
+ result = fib48 % fib50;
+ std::cout << "fib48 % fib50 = " << result << "\n";
+ result = gcd(fib50, fib48);
+ std::cout << "gcd(fib50, fib48) = " << result << "\n";
+ result = sqrt(fib50);
+ std::cout << "sqrt(fib50) = " << result << "\n";
+
+ identitytest(result, fib50, fib48);
+ bittest(result, fib50, fib48);
+ accumtest(result, fib50, fib48);
+ utiltest(fib48);
+ longidentitytest(fib50, 1000, 50);
+ longaccumtest(fib48, 100000, 1);
+}
+
+
+void facttest(Integer& one, Integer& two)
+{
+ Integer fact30(factorial(30));
+ std::cout << "fact30 = factorial(30) = " << fact30 << "\n";
+ assert(fact30.OK());
+
+ Integer fact28(factorial(28));
+ std::cout << "fact28 = factorial(28) = " << fact28 << "\n";
+ assert(fact28.OK());
+ assert(fact30 == fact28 * long(870));
+
+ Integer result = fact30 + fact28;
+ std::cout << "fact30 + fact28 = " << result << "\n";
+ result = fact30 - fact28;
+ std::cout << "fact30 - fact28 = " << result << "\n";
+ result = fact30 * fact28;
+ std::cout << "fact30 * fact28 = " << result << "\n";
+ result = fact30 / fact28;
+ std::cout << "fact30 / fact28 = " << result << "\n";
+ result = fact30 % fact28;
+ std::cout << "fact30 % fact28 = " << result << "\n";
+
+ result = -fact30;
+ std::cout << "-fact30 = " << result << "\n";
+ assert(abs(result) == fact30);
+
+ std::cout << "lg(fact30) = " << lg(fact30) << "\n";
+ assert(lg(fact30) == 107);
+
+ result = gcd(fact30, fact28);
+ std::cout << "gcd(fact30, fact28) = " << result << "\n";
+ assert(result == fact28);
+
+ result = sqrt(fact30);
+ std::cout << "sqrt(fact30) = " << result << "\n";
+
+ Integer negfact31 = fact30 * -31;
+ Integer posfact31 = abs(negfact31);
+ assert(negfact31.OK());
+ assert(posfact31.OK());
+ std::cout << "negfact31 = " << negfact31 << "\n";
+ result = fact30 + negfact31;
+ std::cout << "fact30 + negfact31 = " << result << "\n";
+ result = fact30 - negfact31;
+ std::cout << "fact30 - negfact31 = " << result << "\n";
+ result = fact30 * negfact31;
+ std::cout << "fact30 * negfact31 = " << result << "\n";
+ result = fact30 / negfact31;
+ std::cout << "fact30 / negfact31 = " << result << "\n";
+ result = fact30 % negfact31;
+ std::cout << "fact30 % negfact31 = " << result << "\n";
+ result = gcd(fact30, negfact31);
+ std::cout << "gcd(fact30, negfact31) = " << result << "\n";
+ assert(result == fact30);
+
+ identitytest(one, one, one);
+ identitytest(one, one, one);
+ identitytest(one, two, fact30);
+ identitytest(fact30, posfact31, fact28);
+ identitytest(fact30, negfact31, fact28);
+ identitytest(negfact31, posfact31, fact28);
+
+ bittest(one, one, one);
+ bittest(one, one, one);
+ bittest(one, two, fact30);
+ bittest(fact30, posfact31, fact28);
+
+ accumtest(one, one, one);
+ accumtest(one, one, one);
+ accumtest(one, two, fact30);
+ accumtest(fact30, posfact31, fact28);
+
+ utiltest(one);
+ utiltest(fact30);
+ utiltest(posfact31);
+
+ longidentitytest(one, 1, 1);
+ longidentitytest(one, 2, 3);
+ longidentitytest(fact30, 3, -20);
+ longidentitytest(fact30, 4, 20000);
+ longidentitytest(negfact31, -100, 20000);
+
+ longbittest(one, 1, 1);
+ longbittest(one, 2, 3);
+ longbittest(fact30, 4, 20000);
+ longbittest(fact28, 1000, 50);
+
+ longaccumtest(one, 1, 1);
+ longaccumtest(one, 2, 3);
+ longaccumtest(fact30, 4, 20000);
+ longaccumtest(fact30, 1000, 50);
+ longaccumtest(fact28, 10000000, 100000000);
+}
+
+void modtest()
+{
+ Integer b, e, m;
+
+ m = 1; m <<= 32;
+ b = m + 1;
+
+ e = Ipow( 2, 32 );
+ b = Ipow( 2, 32 ); // use b as a comparison
+ std::cout << "2^32 = " << e << "\n";
+
+ e %= (e-1); // do same op two ways...
+ b = b % (b - 1);
+
+ std::cout << "2^32 % (2^32-1) = " << e << "\n"; // e is incorrect here
+ std::cout << "2^32 % (2^32-1) = " << b << "\n"; // but b is ok
+}
projects / ACL.git / commitdiff