From f1de64cb711d21fe522429dd6698610bb5d27f42 Mon Sep 17 00:00:00 2001 From: Arjen Baart Date: Sun, 3 Nov 2019 12:16:09 +0100 Subject: [PATCH] Ported test cases for class Integer --- .gitignore | 5 + ChangeLog | 2 + doc/Integer.xml | 261 ++++++++++++++++++++++++ doc/Makefile.am | 2 +- doc/manual.xml | 2 + src/Integer.cpp | 53 +++-- src/Integer.h | 19 +- src/builtin.h | 2 - test/Makefile.am | 9 +- test/integer_assign.cpp | 60 ++++++ test/integer_factorial.cpp | 34 ++++ test/integer_factorial.exp | 24 +++ test/integer_fibonacci.cpp | 34 ++++ test/integer_fibonacci.exp | 15 ++ test/integer_modulo.cpp | 20 ++ test/integer_modulo.exp | 6 + test/integer_pow64.cpp | 21 ++ test/integer_pow64.exp | 11 ++ test/tInteger.cpp | 394 +++++++++++++++++++++++++++++++++++++ 19 files changed, 956 insertions(+), 18 deletions(-) create mode 100644 doc/Integer.xml create mode 100644 test/integer_assign.cpp create mode 100644 test/integer_factorial.cpp create mode 100644 test/integer_factorial.exp create mode 100644 test/integer_fibonacci.cpp create mode 100644 test/integer_fibonacci.exp create mode 100644 test/integer_modulo.cpp create mode 100644 test/integer_modulo.exp create mode 100644 test/integer_pow64.cpp create mode 100644 test/integer_pow64.exp create mode 100644 test/tInteger.cpp diff --git a/.gitignore b/.gitignore index 70845e0..0bc84cf 100644 --- a/.gitignore +++ b/.gitignore @@ -1 +1,6 @@ Makefile.in +aclocal.m4 +configure +missing +ylwrap + diff --git a/ChangeLog b/ChangeLog index bdaf9c2..f436736 100644 --- a/ChangeLog +++ b/ChangeLog @@ -1,3 +1,5 @@ + - Ported class Integer from the Gnu libg++ library. + Oct 31, 2019 - Release 0.2 ============================ diff --git a/doc/Integer.xml b/doc/Integer.xml new file mode 100644 index 0000000..7890ac3 --- /dev/null +++ b/doc/Integer.xml @@ -0,0 +1,261 @@ + + +Integer - Arbitrary length integer numbers + +The Integer class provides multiple precision integer arithmetic +facilities. Some representation details are discussed in the +Representation section. + + +Integers may be up to b * ((1 << b) - 1) bits long, where +b is the number of bits per short (typically 1048560 bits when +b = 16). The implementation assumes that a long is at least +twice as long as a short. This assumption hides beneath almost all +primitive operations, and would be very difficult to change. It also relies +on correct behavior of unsigned arithmetic operations. + + +Some of the arithmetic algorithms are very loosely based on those +provided in the MIT Scheme `bignum.c' release, which is +Copyright (c) 1987 Massachusetts Institute of Technology. Their use +here falls within the provisions described in the Scheme release. + + +
+Construction + +Integers may be constructed in the following ways: + + + +Declares an uninitialized Integer. + + +Set x and y to the Integer value 2; + + +Set u and v to the same value as x. + + + +
+ +
+Conversion + + +Used to coerce an Integer back into longs via the long +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. + + +Returns true iff the Integer is < MAXLONG and > MINLONG. + + +Coerce the Integer to a double, with potential +loss of precision. ++/-HUGE is returned if the Integer cannot fit into a double. + + +Returns true iff the Integer can fit into a double. + + +
+ +
+Operators + +All of the usual arithmetic operators are provided (+, -, *, /, +%, +=, ++, -=, --, *=, /=, %=, ==, !=, <, <=, >, >=). 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 ++ and --. Because C++ does not +distinguish prefix from postfix application, these are declared as +void operators, so that no confusion can result from applying +them as postfix. Thus, for Integers x and y, ++x; y = x; is +correct, but y = ++x; and y = x++; are not. + + +Bitwise operators (~, &, |, ^, <<, +>>, &=, |=, ^=, <<=, >>=) 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, Integer(-3) +& Integer(5) returns Integer(-1), not -3, as it would using +two's complement. Also, ~, 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. + +
+ +
+Functions + +The following utility functions are also provided. (All arguments +are Integers unless otherwise noted). + + + +Sets q to the quotient and r to the remainder of x and y. +(q and r are returned by reference). + + + +Returns x raised to the power p. + + + +Returns x raised to the power p. + + + +Returns the greatest common divisor of x and y. + + + +Returns the least common multiple of x and y. + + + +Returns the absolute value of x. + + + +Negates this in place. + + + +returns x * x; + + + +returns the floor of the square root of x. + + + +returns the floor of the base 2 logarithm of abs(x) + + + +returns -1 if x is negative, 0 if zero, else +1. +Using if (sign(x) == 0) is a generally faster method +of testing for zero than using relational operators. + + + +returns true if x is an even number + + + +returns true if x is an odd number. + + + +sets the b'th bit (counting right-to-left from zero) of x to 1. + + + +sets the b'th bit of x to 0. + + + +returns true if the b'th bit of x is 1. + + + +converts the base base char* string into its Integer form. + + + +prints the ascii string value of (*this) as a base base +number, in field width at least width. + + + +prints x in base ten format. + + + +reads x as a base ten number. + + + +returns a negative number if x<y, zero if x==y, or positive if x>y. + + + +like compare, but performs unsigned comparison. + + + +A faster way to say z = x + y. + + + +A faster way to say z = x - y. + + + +A faster way to say z = x * y. + + + +A faster way to say z = x / y. + + + +A faster way to say z = x % y. + + + +A faster way to say z = x & y. + + + +A faster way to say z = x | y. + + + +A faster way to say z = x ^ y. + + + +A faster way to say z = x << y. + + + +A faster way to say z = x >> y. + + + +A faster way to say z = pow(x, y). + + + +A faster way to say z = ~x. + + + +A faster way to say z = -x. + + + + +
+ +
+SEE ALSO + + +The Integer class in the Gnu libg++ manual. + + +
+ diff --git a/doc/Makefile.am b/doc/Makefile.am index 94b843e..76537f1 100644 --- a/doc/Makefile.am +++ b/doc/Makefile.am @@ -7,7 +7,7 @@ SUFFIXES = .obj .eps .png .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= diff --git a/doc/manual.xml b/doc/manual.xml index bbb9745..79bb2b9 100644 --- a/doc/manual.xml +++ b/doc/manual.xml @@ -13,5 +13,7 @@ xmlns:xi="http://www.w3.org/2001/XInclude"/> + diff --git a/src/Integer.cpp b/src/Integer.cpp index 1e69029..c6a931a 100644 --- a/src/Integer.cpp +++ b/src/Integer.cpp @@ -80,6 +80,17 @@ IntRep _OneRep = {1, 0, 1, {1}}; 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 @@ -110,7 +121,10 @@ inline static int docmp(const unsigned short* x, const unsigned short* y, int l) 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; } @@ -153,7 +167,7 @@ static inline void scpy(const unsigned short* src, unsigned short* dest,int nb) 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. @@ -166,7 +180,7 @@ inline static IntRep* Inew(int newlen) 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); @@ -300,11 +314,12 @@ IntRep* Icopy_ulong(IntRep* old, unsigned long x) 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) @@ -544,7 +559,7 @@ int compare(const IntRep* x, long y) 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; @@ -1203,7 +1218,7 @@ IntRep* div(const IntRep* x, const IntRep* y, IntRep* q) 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; @@ -1254,7 +1269,7 @@ IntRep* div(const IntRep* x, long y, IntRep* q) { 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; @@ -1324,7 +1339,7 @@ void divide(const Integer& Ix, long y, Integer& Iq, long& rem) 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; @@ -1414,7 +1429,7 @@ void divide(const Integer& Ix, const Integer& Iy, Integer& Iq, Integer& Ir) 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; @@ -1481,7 +1496,7 @@ IntRep* mod(const IntRep* x, const IntRep* y, IntRep* r) 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; @@ -1531,7 +1546,7 @@ IntRep* mod(const IntRep* x, long y, IntRep* r) { 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; @@ -1962,6 +1977,16 @@ IntRep* gcd(const IntRep* x, const IntRep* y) } +long lg(unsigned long x) +{ + long l = 0; + while (x > 1) + { + x = x >> 1; + ++l; + } + return l; +} long lg(const IntRep* x) { @@ -2151,6 +2176,7 @@ char* cvtItoa(const IntRep* x, char* fmt, int& fmtlen, int base, int showbase, int width, int align_right, char fillchar, char Xcase, int showpos) { + char* e = fmt + fmtlen - 1; char* s = e; *--s = 0; @@ -2180,7 +2206,7 @@ char* cvtItoa(const IntRep* x, char* fmt, int& fmtlen, int base, int showbase, Icheck(z); if (z->len == 0) { - while (rem != 0) + while (rem != 0 || *s == '\0') { char ch = rem % base; rem /= base; @@ -2218,6 +2244,7 @@ char* cvtItoa(const IntRep* x, char* fmt, int& fmtlen, int base, int showbase, } if (x->sgn == I_NEGATIVE) *--s = '-'; else if (showpos) *--s = '+'; + int w = e - s - 1; if (!align_right || w >= width) { @@ -2369,6 +2396,6 @@ int Integer::OK() const void Integer::error(const char* msg) const { - (*lib_error_handler)("Integer", msg); + lib_error_handler("Integer", msg); } diff --git a/src/Integer.h b/src/Integer.h index f004732..58da747 100644 --- a/src/Integer.h +++ b/src/Integer.h @@ -85,12 +85,18 @@ protected: 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); @@ -221,6 +227,7 @@ public: 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&); @@ -277,12 +284,17 @@ extern Integer lcm(const Integer& x, const Integer& y); // least common mult 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)) {} @@ -524,6 +536,11 @@ inline int operator == (const Integer& x, long y) 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; diff --git a/src/builtin.h b/src/builtin.h index d6a41a4..8a00f6e 100644 --- a/src/builtin.h +++ b/src/builtin.h @@ -69,8 +69,6 @@ unsigned int foldhash(double); 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); diff --git a/test/Makefile.am b/test/Makefile.am index 0d8369c..7a33525 100644 --- a/test/Makefile.am +++ b/test/Makefile.am @@ -5,7 +5,8 @@ LDADD = ../src/.libs/libACL.la 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 @@ -34,3 +35,9 @@ hour_now : hour_check_now 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 diff --git a/test/integer_assign.cpp b/test/integer_assign.cpp new file mode 100644 index 0000000..6bef070 --- /dev/null +++ b/test/integer_assign.cpp @@ -0,0 +1,60 @@ +/******************************************************* + * Unit test for the Integer class + * + * test contrustor and assignment of Integer objects + ****************************************************** + * + */ + +#include "Integer.h" +#include + +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; +} + diff --git a/test/integer_factorial.cpp b/test/integer_factorial.cpp new file mode 100644 index 0000000..c7f24a1 --- /dev/null +++ b/test/integer_factorial.cpp @@ -0,0 +1,34 @@ +/******************************************************* + * Unit test for the Integer class + * + * test several functions with a factorial calculation + ****************************************************** + * + */ + +#include "Integer.h" +#include + + +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"; +} diff --git a/test/integer_factorial.exp b/test/integer_factorial.exp new file mode 100644 index 0000000..fad52da --- /dev/null +++ b/test/integer_factorial.exp @@ -0,0 +1,24 @@ +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) diff --git a/test/integer_fibonacci.cpp b/test/integer_fibonacci.cpp new file mode 100644 index 0000000..098da80 --- /dev/null +++ b/test/integer_fibonacci.cpp @@ -0,0 +1,34 @@ +/******************************************************* + * Unit test for the Integer class + * + * test several functions with a fibonacci calculation + ****************************************************** + * + */ + +#include "Integer.h" +#include + + +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"; +} diff --git a/test/integer_fibonacci.exp b/test/integer_fibonacci.exp new file mode 100644 index 0000000..0d1f2fe --- /dev/null +++ b/test/integer_fibonacci.exp @@ -0,0 +1,15 @@ +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) diff --git a/test/integer_modulo.cpp b/test/integer_modulo.cpp new file mode 100644 index 0000000..b20b812 --- /dev/null +++ b/test/integer_modulo.cpp @@ -0,0 +1,20 @@ +/******************************************************* + * Unit test for the Integer class + * + * test the Integer modulo function + ****************************************************** + * + */ + +#include "Integer.h" +#include + + +void modtest(); + +int main() +{ + modtest(); + + std::cout << "\nEnd of test\n"; +} diff --git a/test/integer_modulo.exp b/test/integer_modulo.exp new file mode 100644 index 0000000..25b6ce1 --- /dev/null +++ b/test/integer_modulo.exp @@ -0,0 +1,6 @@ +2^32 = 4294967296 +2^32 % (2^32-1) = 1 +2^32 % (2^32-1) = 1 + +End of test +PASS integer_modulo (exit status: 0) diff --git a/test/integer_pow64.cpp b/test/integer_pow64.cpp new file mode 100644 index 0000000..fc2ea86 --- /dev/null +++ b/test/integer_pow64.cpp @@ -0,0 +1,21 @@ +/******************************************************* + * Unit test for the Integer class + * + * test cases with 2 ^ 64 numbers + ****************************************************** + * + */ + +#include "Integer.h" +#include + + +void anothertest(); + +int main() +{ + anothertest(); + //modtest(); + + std::cout << "\nEnd of test\n"; +} diff --git a/test/integer_pow64.exp b/test/integer_pow64.exp new file mode 100644 index 0000000..e9c53ba --- /dev/null +++ b/test/integer_pow64.exp @@ -0,0 +1,11 @@ +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) diff --git a/test/tInteger.cpp b/test/tInteger.cpp new file mode 100644 index 0000000..d0b7c83 --- /dev/null +++ b/test/tInteger.cpp @@ -0,0 +1,394 @@ +/* + a test file for Integer class + */ + +#include +#include + +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 +} -- 2.20.1