From 0afe80d551aa9b66b574b956cf681692399fc728 Mon Sep 17 00:00:00 2001 From: Matt McCutchen Date: Wed, 30 Jan 2008 18:15:31 -0500 Subject: [PATCH] - Add some big-integer algorithms. - Improve names of BigIntegerUtils conversion functions. - Make stringToBigInteger recognize a leading + sign. - Remove false claim that BigIntegerUtils provides istream >> operator. - Improve BigUnsigned shift operators: now just one version that handles a positive or negative int shift distance. - Throw exceptions on /, % by zero (just not divideWithRemainder). - Apply previously forgotten cleanups to BigInteger /=, %=. - Start a testsuite. There's only one test. - Clean up Makefile a bit. - Improve comments in sample.cc. --- .gitignore | 3 ++ BigInteger.hh | 19 ++++---- BigIntegerAlgorithms.cc | 72 ++++++++++++++++++++++++++++++ BigIntegerAlgorithms.hh | 25 +++++++++++ BigIntegerLibrary.hh | 1 + BigIntegerUtils.cc | 29 +++++------- BigIntegerUtils.hh | 27 +++++------ BigUnsigned.cc | 22 ++++++++- BigUnsigned.hh | 46 +++++-------------- Makefile | 53 +++++++++++++++------- sample.cc | 99 +++++++++++++++++++++-------------------- testsuite.cc | 17 +++++++ 12 files changed, 272 insertions(+), 141 deletions(-) create mode 100644 BigIntegerAlgorithms.cc create mode 100644 BigIntegerAlgorithms.hh create mode 100644 testsuite.cc diff --git a/.gitignore b/.gitignore index 5d93982..9cad653 100644 --- a/.gitignore +++ b/.gitignore @@ -1,2 +1,5 @@ *.o sample +testsuite +testsuite.expected +testsuite.out diff --git a/BigInteger.hh b/BigInteger.hh index 11be062..cf6e910 100644 --- a/BigInteger.hh +++ b/BigInteger.hh @@ -157,12 +157,14 @@ inline BigInteger BigInteger::operator *(const BigInteger &x) const { return ans; } inline BigInteger BigInteger::operator /(const BigInteger &x) const { + if (x.isZero()) throw "BigInteger::operator /: division by zero"; BigInteger q, r; r = *this; r.divideWithRemainder(x, q); return q; } inline BigInteger BigInteger::operator %(const BigInteger &x) const { + if (x.isZero()) throw "BigInteger::operator %: division by zero"; BigInteger q, r; r = *this; r.divideWithRemainder(x, q); @@ -191,18 +193,19 @@ inline void BigInteger::operator *=(const BigInteger &x) { multiply(*this, x); } inline void BigInteger::operator /=(const BigInteger &x) { - // Updated for divideWithRemainder - BigInteger thisCopy(*this); - thisCopy.divideWithRemainder(x, *this); - // quotient left in *this - // don't care about remainder left in thisCopy + if (x.isZero()) throw "BigInteger::operator /=: division by zero"; + /* The following technique is slightly faster than copying *this first + * when x is large. */ + BigInteger q; + divideWithRemainder(x, q); + // *this contains the remainder, but we overwrite it with the quotient. + *this = q; } inline void BigInteger::operator %=(const BigInteger &x) { - // Shortcut (woohoo!) + if (x.isZero()) throw "BigInteger::operator %=: division by zero"; BigInteger q; + // Mods *this by x. Don't care about quotient left in q. divideWithRemainder(x, q); - // remainder left in *this - // don't care about quotient left in q } // This one is trivial inline void BigInteger::flipSign() { diff --git a/BigIntegerAlgorithms.cc b/BigIntegerAlgorithms.cc new file mode 100644 index 0000000..66cea24 --- /dev/null +++ b/BigIntegerAlgorithms.cc @@ -0,0 +1,72 @@ +#include "BigIntegerAlgorithms.hh" + +BigUnsigned gcd(BigUnsigned a, BigUnsigned b) { + BigUnsigned trash; + // Neat in-place alternating technique. + for (;;) { + if (b.isZero()) + return a; + a.divideWithRemainder(b, trash); + if (a.isZero()) + return b; + b.divideWithRemainder(a, trash); + } +} + +void extendedEuclidean(BigInteger m, BigInteger n, + BigInteger &g, BigInteger &r, BigInteger &s) { + if (&g == &r || &g == &s || &r == &s) + throw "BigInteger extendedEuclidean: Outputs are aliased"; + BigInteger r1(1), s1(0), r2(0), s2(1), q; + /* Invariants: + * r1*m + s1*n == m(orig) + * r2*m + s2*n == n(orig) */ + for (;;) { + if (n.isZero()) { + r = r1; s = s1; g = m; + return; + } + m.divideWithRemainder(n, q); + r1 -= q*r2; s1 -= q*s2; + + if (m.isZero()) { + r = r2; s = s2; g = n; + return; + } + n.divideWithRemainder(m, q); + r2 -= q*r1; s2 -= q*s1; + } +} + +BigUnsigned modinv(const BigInteger &x, const BigUnsigned &n) { + BigInteger g, r, s; + extendedEuclidean(x, n, g, r, s); + if (g == 1) + // r*x + s*n == 1, so r*x === 1 (mod n), so r is the answer. + return (r % n).getMagnitude(); // (r % n) will be nonnegative + else + throw "BigInteger modinv: x and n have a common factor"; +} + +BigUnsigned modexp(const BigInteger &base, const BigUnsigned &exponent, + const BigUnsigned &modulus) { + BigUnsigned ans = 1, base2 = (base % modulus).getMagnitude(); + BigUnsigned::Index i = exponent.getLength(); + // For each block of the exponent, most to least significant... + while (i > 0) { + i--; + BigUnsigned::Blk eb = exponent.getBlock(i); + // For each bit, most to least significant... + for (BigUnsigned::Blk mask = ~((~BigUnsigned::Blk(0)) >> 1); + mask != 0; mask >>= 1) { + // Square and maybe multiply. + ans *= ans; + ans %= modulus; + if (eb & mask) { + ans *= base2; + ans %= modulus; + } + } + } + return ans; +} diff --git a/BigIntegerAlgorithms.hh b/BigIntegerAlgorithms.hh new file mode 100644 index 0000000..b1dd943 --- /dev/null +++ b/BigIntegerAlgorithms.hh @@ -0,0 +1,25 @@ +#ifndef BIGINTEGERALGORITHMS_H +#define BIGINTEGERALGORITHMS_H + +#include "BigInteger.hh" + +/* Some mathematical algorithms for big integers. + * This code is new and, as such, experimental. */ + +// Returns the greatest common divisor of a and b. +BigUnsigned gcd(BigUnsigned a, BigUnsigned b); + +/* Extended Euclidean algorithm. + * Given m and n, finds gcd g and numbers r, s such that r*m + s*n == g. */ +void extendedEuclidean(BigInteger m, BigInteger n, + BigInteger &g, BigInteger &r, BigInteger &s); + +/* Returns the multiplicative inverse of x modulo n, or throws an exception if + * they have a common factor. */ +BigUnsigned modinv(const BigInteger &x, const BigUnsigned &n); + +// Returns (base ^ exponent) % modulus. +BigUnsigned modexp(const BigInteger &base, const BigUnsigned &exponent, + const BigUnsigned &modulus); + +#endif diff --git a/BigIntegerLibrary.hh b/BigIntegerLibrary.hh index ea38cfe..2a0ebee 100644 --- a/BigIntegerLibrary.hh +++ b/BigIntegerLibrary.hh @@ -3,5 +3,6 @@ #include "NumberlikeArray.hh" #include "BigUnsigned.hh" #include "BigInteger.hh" +#include "BigIntegerAlgorithms.hh" #include "BigUnsignedInABase.hh" #include "BigIntegerUtils.hh" diff --git a/BigIntegerUtils.cc b/BigIntegerUtils.cc index 3ac75dc..44073af 100644 --- a/BigIntegerUtils.cc +++ b/BigIntegerUtils.cc @@ -1,33 +1,27 @@ #include "BigIntegerUtils.hh" #include "BigUnsignedInABase.hh" -/* - * This file includes: - * (1) `std::string <=> BigUnsigned/BigInteger' conversion routines easier than `BigUnsignedInABase' - * (2) << and >> operators for BigUnsigned/BigInteger, std::istream/std::ostream - */ - -std::string easyBUtoString(const BigUnsigned &x) { +std::string bigUnsignedToString(const BigUnsigned &x) { return std::string(BigUnsignedInABase(x, 10)); } -std::string easyBItoString(const BigInteger &x) { +std::string bigIntegerToString(const BigInteger &x) { return (x.getSign() == BigInteger::negative) - ? (std::string("-") + easyBUtoString(x.getMagnitude())) - : (easyBUtoString(x.getMagnitude())); + ? (std::string("-") + bigUnsignedToString(x.getMagnitude())) + : (bigUnsignedToString(x.getMagnitude())); } -BigUnsigned easyStringToBU(const std::string &s) { +BigUnsigned stringToBigUnsigned(const std::string &s) { return BigUnsigned(BigUnsignedInABase(s, 10)); } -BigInteger easyStringToBI(const std::string &s) { - return (s[0] == '-') ? - BigInteger(easyStringToBU(s.substr(1, s.length() - 1)), BigInteger::negative) : - BigInteger(easyStringToBU(s)); +BigInteger stringToBigInteger(const std::string &s) { + // Recognize a sign followed by a BigUnsigned. + return (s[0] == '-') ? BigInteger(stringToBigUnsigned(s.substr(1, s.length() - 1)), BigInteger::negative) + : (s[0] == '+') ? BigInteger(stringToBigUnsigned(s.substr(1, s.length() - 1))) + : BigInteger(stringToBigUnsigned(s)); } -// Outputs x to os, obeying the flags `dec', `hex', `bin', and `showbase'. std::ostream &operator <<(std::ostream &os, const BigUnsigned &x) { BigUnsignedInABase::Base base; long osFlags = os.flags(); @@ -47,8 +41,7 @@ std::ostream &operator <<(std::ostream &os, const BigUnsigned &x) { os << s; return os; } -// Outputs x to os, obeying the flags `dec', `hex', `bin', and `showbase'. -// My somewhat arbitrary policy: a negative sign comes before a base indicator (like -0xFF). + std::ostream &operator <<(std::ostream &os, const BigInteger &x) { if (x.getSign() == BigInteger::negative) os << '-'; diff --git a/BigIntegerUtils.hh b/BigIntegerUtils.hh index 16900f4..2f6d22f 100644 --- a/BigIntegerUtils.hh +++ b/BigIntegerUtils.hh @@ -5,21 +5,19 @@ #include #include -/* - * This file includes: - * (1) `std::string <=> BigUnsigned/BigInteger' conversion routines easier than `BigUnsignedInABase' - * (2) << and >> operators for BigUnsigned/BigInteger, std::istream/std::ostream - */ +/* This file provides: + * - Convenient std::string <-> BigUnsigned/BigInteger conversion routines + * - std::ostream << operators for BigUnsigned/BigInteger */ -// Conversion routines. Base 10 only. -std::string easyBUtoString(const BigUnsigned &x); -std::string easyBItoString(const BigInteger &x); -BigUnsigned easyStringToBU(const std::string &s); -BigInteger easyStringToBI(const std::string &s); +// std::string conversion routines. Base 10 only. +std::string bigUnsignedToString(const BigUnsigned &x); +std::string bigIntegerToString(const BigInteger &x); +BigUnsigned stringToBigUnsigned(const std::string &s); +BigInteger stringToBigInteger(const std::string &s); // Creates a BigInteger from data such as `char's; read below for details. template -BigInteger easyDataToBI(const T* data, BigInteger::Index length, BigInteger::Sign sign); +BigInteger dataToBigInteger(const T* data, BigInteger::Index length, BigInteger::Sign sign); // Outputs x to os, obeying the flags `dec', `hex', `bin', and `showbase'. std::ostream &operator <<(std::ostream &os, const BigUnsigned &x); @@ -28,10 +26,7 @@ std::ostream &operator <<(std::ostream &os, const BigUnsigned &x); // My somewhat arbitrary policy: a negative sign comes before a base indicator (like -0xFF). std::ostream &operator <<(std::ostream &os, const BigInteger &x); -/* - * ================================= - * BELOW THIS POINT are template definitions; above are declarations. See `NumberlikeArray.hh'. - */ +// BEGIN TEMPLATE DEFINITIONS. /* * Converts binary data to a BigInteger. @@ -47,7 +42,7 @@ std::ostream &operator <<(std::ostream &os, const BigInteger &x); * the result contain the desired binary data. */ template -BigInteger easyDataToBI(const T* data, BigInteger::Index length, BigInteger::Sign sign) { +BigInteger dataToBigInteger(const T* data, BigInteger::Index length, BigInteger::Sign sign) { // really ceiling(numBytes / sizeof(BigInteger::Blk)) unsigned int pieceSizeInBits = 8 * sizeof(T); unsigned int piecesPerBlock = sizeof(BigInteger::Blk) / sizeof(T); diff --git a/BigUnsigned.cc b/BigUnsigned.cc index db407c5..9e5a347 100644 --- a/BigUnsigned.cc +++ b/BigUnsigned.cc @@ -625,8 +625,17 @@ void BigUnsigned::bitXor(const BigUnsigned &a, const BigUnsigned &b) { zapLeadingZeros(); } -void BigUnsigned::bitShiftLeft(const BigUnsigned &a, unsigned int b) { +void BigUnsigned::bitShiftLeft(const BigUnsigned &a, int b) { DTRT_ALIASED(this == &a, bitShiftLeft(a, b)); + if (b < 0) { + if (b << 1 == 0) + throw "BigUnsigned::bitShiftLeft: " + "Pathological shift amount not implemented"; + else { + bitShiftRight(a, -b); + return; + } + } Index shiftBlocks = b / N; unsigned int shiftBits = b % N; // + 1: room for high bits nudged left into another block @@ -642,8 +651,17 @@ void BigUnsigned::bitShiftLeft(const BigUnsigned &a, unsigned int b) { len--; } -void BigUnsigned::bitShiftRight(const BigUnsigned &a, unsigned int b) { +void BigUnsigned::bitShiftRight(const BigUnsigned &a, int b) { DTRT_ALIASED(this == &a, bitShiftRight(a, b)); + if (b < 0) { + if (b << 1 == 0) + throw "BigUnsigned::bitShiftRight: " + "Pathological shift amount not implemented"; + else { + bitShiftLeft(a, -b); + return; + } + } // This calculation is wacky, but expressing the shift as a left bit shift // within each block lets us use getShiftedBlock. Index rightShiftBlocks = (b + N - 1) / N; diff --git a/BigUnsigned.hh b/BigUnsigned.hh index 624c87f..12dc534 100644 --- a/BigUnsigned.hh +++ b/BigUnsigned.hh @@ -166,8 +166,10 @@ public: void bitAnd(const BigUnsigned &a, const BigUnsigned &b); void bitOr(const BigUnsigned &a, const BigUnsigned &b); void bitXor(const BigUnsigned &a, const BigUnsigned &b); - void bitShiftLeft(const BigUnsigned &a, unsigned int b); - void bitShiftRight(const BigUnsigned &a, unsigned int b); + /* Negative shift amounts translate to opposite-direction shifts, + * except for -2^(8*sizeof(int)-1) which is unimplemented. */ + void bitShiftLeft(const BigUnsigned &a, int b); + void bitShiftRight(const BigUnsigned &a, int b); /* `a.divideWithRemainder(b, q)' is like `q = a / b, a %= b'. * / and % use semantics similar to Knuth's, which differ from the @@ -191,10 +193,6 @@ public: BigUnsigned operator &(const BigUnsigned &x) const; BigUnsigned operator |(const BigUnsigned &x) const; BigUnsigned operator ^(const BigUnsigned &x) const; - BigUnsigned operator <<(unsigned int b) const; - BigUnsigned operator >>(unsigned int b) const; - // Additional operators in an attempt to avoid overloading tangles. - // XXX Why exactly are these needed? BigUnsigned operator <<(int b) const; BigUnsigned operator >>(int b) const; @@ -207,10 +205,6 @@ public: void operator &=(const BigUnsigned &x); void operator |=(const BigUnsigned &x); void operator ^=(const BigUnsigned &x); - void operator <<=(unsigned int b); - void operator >>=(unsigned int b); - // Additional operators in an attempt to avoid overloading tangles. - // XXX Why exactly are these needed? void operator <<=(int b); void operator >>=(int b); @@ -251,12 +245,14 @@ inline BigUnsigned BigUnsigned::operator *(const BigUnsigned &x) const { return ans; } inline BigUnsigned BigUnsigned::operator /(const BigUnsigned &x) const { + if (x.isZero()) throw "BigUnsigned::operator /: division by zero"; BigUnsigned q, r; r = *this; r.divideWithRemainder(x, q); return q; } inline BigUnsigned BigUnsigned::operator %(const BigUnsigned &x) const { + if (x.isZero()) throw "BigUnsigned::operator %: division by zero"; BigUnsigned q, r; r = *this; r.divideWithRemainder(x, q); @@ -277,26 +273,16 @@ inline BigUnsigned BigUnsigned::operator ^(const BigUnsigned &x) const { ans.bitXor(*this, x); return ans; } -inline BigUnsigned BigUnsigned::operator <<(unsigned int b) const { +inline BigUnsigned BigUnsigned::operator <<(int b) const { BigUnsigned ans; ans.bitShiftLeft(*this, b); return ans; } -inline BigUnsigned BigUnsigned::operator >>(unsigned int b) const { +inline BigUnsigned BigUnsigned::operator >>(int b) const { BigUnsigned ans; ans.bitShiftRight(*this, b); return ans; } -inline BigUnsigned BigUnsigned::operator <<(int b) const { - if (b < 0) - throw "BigUnsigned::operator <<(int): Negative shift amounts are not allowed"; - return *this << (unsigned int)(b); -} -inline BigUnsigned BigUnsigned::operator >>(int b) const { - if (b < 0) - throw "BigUnsigned::operator >>(int): Negative shift amounts are not allowed"; - return *this >> (unsigned int)(b); -} inline void BigUnsigned::operator +=(const BigUnsigned &x) { add(*this, x); @@ -308,6 +294,7 @@ inline void BigUnsigned::operator *=(const BigUnsigned &x) { multiply(*this, x); } inline void BigUnsigned::operator /=(const BigUnsigned &x) { + if (x.isZero()) throw "BigUnsigned::operator /=: division by zero"; /* The following technique is slightly faster than copying *this first * when x is large. */ BigUnsigned q; @@ -316,6 +303,7 @@ inline void BigUnsigned::operator /=(const BigUnsigned &x) { *this = q; } inline void BigUnsigned::operator %=(const BigUnsigned &x) { + if (x.isZero()) throw "BigUnsigned::operator %=: division by zero"; BigUnsigned q; // Mods *this by x. Don't care about quotient left in q. divideWithRemainder(x, q); @@ -329,21 +317,11 @@ inline void BigUnsigned::operator |=(const BigUnsigned &x) { inline void BigUnsigned::operator ^=(const BigUnsigned &x) { bitXor(*this, x); } -inline void BigUnsigned::operator <<=(unsigned int b) { - bitShiftLeft(*this, b); -} -inline void BigUnsigned::operator >>=(unsigned int b) { - bitShiftRight(*this, b); -} inline void BigUnsigned::operator <<=(int b) { - if (b < 0) - throw "BigUnsigned::operator <<=(int): Negative shift amounts are not supported"; - *this <<= (unsigned int)(b); + bitShiftLeft(*this, b); } inline void BigUnsigned::operator >>=(int b) { - if (b < 0) - throw "BigUnsigned::operator >>=(int): Negative shift amounts are not supported"; - *this >>= (unsigned int)(b); + bitShiftRight(*this, b); } #endif diff --git a/Makefile b/Makefile index db8cb4f..68e7a00 100644 --- a/Makefile +++ b/Makefile @@ -1,26 +1,49 @@ -# -# Matt McCutchen's Big Integer Library -# - # Mention default target. -all : +all: # Implicit rule to compile C++ files. Modify to your taste. -%.o : %.cc +%.o: %.cc g++ -c -O2 -Wall -Wextra -pedantic $< # Components of the library. -library-objects = BigUnsigned.o BigInteger.o BigUnsignedInABase.o BigIntegerUtils.o -library-headers = NumberlikeArray.hh BigUnsigned.hh BigUnsignedInABase.hh BigInteger.hh BigIntegerLibrary.hh +library-objects = \ + BigUnsigned.o \ + BigInteger.o \ + BigIntegerAlgorithms.o \ + BigUnsignedInABase.o \ + BigIntegerUtils.o \ + +library-headers = \ + NumberlikeArray.hh \ + BigUnsigned.hh \ + BigInteger.hh \ + BigIntegerAlgorithms.hh \ + BigUnsignedInABase.hh \ + BigIntegerLibrary.hh \ # To ``make the library'', make all its objects using the implicit rule. -library : $(library-objects) +library: $(library-objects) + +# Conservatively assume that all the objects depend on all the headers. +$(library-objects): $(library-headers) -# Extra dependencies from `#include'. -BigUnsigned.o : NumberlikeArray.hh BigUnsigned.hh -BigInteger.o : NumberlikeArray.hh BigUnsigned.hh BigInteger.hh -BigUnsignedInABase.o : NumberlikeArray.hh BigUnsigned.hh BigUnsignedInABase.hh -BigIntegerUtils.o : NumberlikeArray.hh BigUnsigned.hh BigUnsignedInABase.hh BigInteger.hh +# TESTSUITE +# Compiling the testsuite. +testsuite.o: $(library-headers) +testsuite: testsuite.o $(library-objects) + g++ $^ -o $@ +# Extract the expected output from the testsuite source. +testsuite.expected: testsuite.cc + sed -nre 's,^.*//,,p' $< >$@ +# Run the testsuite. +.PHONY: test +test: testsuite testsuite.expected + ./testsuite >testsuite.out + @if diff -u testsuite.expected testsuite.out; then\ + echo 'All tests passed.';\ + else\ + echo >&2 'At least one test failed!'; exit 1;\ + fi # The rules below build a program that uses the library. They are preset to # build ``sample'' from ``sample.cc''. You can change the name(s) of the @@ -37,7 +60,7 @@ $(program-objects) : $(library-headers) # How to link the program. The implicit rule covers individual objects. $(program) : $(program-objects) $(library-objects) - g++ $(program-objects) $(library-objects) -o $(program) + g++ $^ -o $@ # Delete all generated files we know about. clean : diff --git a/sample.cc b/sample.cc index 149b18b..62b41df 100644 --- a/sample.cc +++ b/sample.cc @@ -1,74 +1,74 @@ -/* - * Sample program demonstrating the most important features of the Big - * Integer Library - */ +// Sample program demonstrating the use of the Big Integer Library. // Standard libraries #include #include -// For the BigInteger class itself. -#include "BigInteger.hh" - -// For the 4 routines `easy BI/BU <=> string' and `iostream' integration. -#include "BigIntegerUtils.hh" +// `BigIntegerLibrary.hh' includes all of the library headers. +#include "BigIntegerLibrary.hh" int main() { + /* The library throws `const char *' error messages when things go + * wrong. It's a good idea to catch them using a `try' block like this + * one. Your C++ compiler might need a command-line option to compile + * code that uses exceptions. */ try { BigInteger a; // a is 0 int b = 535; - a = b; // From int to BigInteger implicitly... - b = a.toInt(); // ...and back explicitly. - /* - * If a were too big for an int you'd get a runtime exception. - * The Big Integer Library throws C-strings (that is, - * `const char *'s) when something goes wrong. It's a good idea - * to catch them; the `try/catch' construct wrapping all this - * code is an example of how to do this. Some C++ compilers need - * a special command-line option to compile code that uses - * exceptions. - */ + /* Any primitive integer can be converted implicitly to a + * BigInteger. */ + a = b; + + /* The reverse conversion requires a method call (implicit + * conversions were previously supported but caused trouble). + * If a were too big for an int, the library would throw an + * exception. */ + b = a.toInt(); BigInteger c(a); // Copy a BigInteger. - // d is -314159265. The `int' literal is converted to a - // BigInteger. + // The int literal is converted to a BigInteger. BigInteger d(-314159265); - // This won't compile because the number is too big to be an - // integer literal. + /* This won't compile (at least on 32-bit machines) because the + * number is too big to be a primitive integer literal, and + * there's no such thing as a BigInteger literal. */ //BigInteger e(3141592653589793238462643383279); // Instead you can convert the number from a string. std::string s("3141592653589793238462643383279"); - BigInteger f = easyStringToBI(s); + BigInteger f = stringToBigInteger(s); // You can convert the other way too. - std::string s2 = easyBItoString(f); + std::string s2 = bigIntegerToString(f); - // f is stringified and send to std::cout. + // f is implicitly stringified and sent to std::cout. std::cout << f << std::endl; - /* - * Let's do some math! - * - * The Big Integer Library provides lots of overloaded operators - * and corresponding assignment operators. So you can do `a + b' - * with BigIntegers just as with normal integers. The named - * methods `add', `divideWithRemainder', etc. are more advanced - * ``put-here operations''; see `BigUnsigned.hh' for details. - */ + /* Let's do some math! The library overloads most of the + * mathematical operators (including assignment operators) to + * work on BigIntegers. There are also ``copy-less'' + * operations; see `BigUnsigned.hh' for details. */ + + // Arithmetic operators BigInteger g(314159), h(265); - // All five ``return-by-value'' arithmetic operators. - std::cout << (g + h) << '\n' << (g - h) << '\n' << (g * h) - << '\n' << (g / h) << '\n' << (g % h) << std::endl; + std::cout << (g + h) << '\n' + << (g - h) << '\n' + << (g * h) << '\n' + << (g / h) << '\n' + << (g % h) << std::endl; + // Bitwise operators BigUnsigned i(0xFF0000FF), j(0x0000FFFF); - // All five ``return-by-value'' bitwise operators. + // The library's << operator recognizes base flags. std::cout.flags(std::ios::hex | std::ios::showbase); - std::cout << (i & j) << '\n' << (i | j) << '\n' << (i ^ j) << '\n' - << (j << 21) << '\n' << (j >> 10) << '\n'; + std::cout << (i & j) << '\n' + << (i | j) << '\n' + << (i ^ j) << '\n' + // Shift distances are ordinary unsigned ints. + << (j << 21) << '\n' + << (j >> 10) << '\n'; std::cout.flags(std::ios::dec); // Let's do some heavy lifting and calculate powers of 314. @@ -79,12 +79,12 @@ int main() { x *= big314; // A BigInteger assignment operator } - /* - * If you want to experiment with the library, - * you can add your own test code here. - */ - // std::cout << "Beginning of custom test code:" << std::endl; + // Some big-integer algorithms (albeit on small integers). + std::cout << gcd(BigUnsigned(60), 72) << '\n' + << modinv(BigUnsigned(7), 11) << '\n' + << modexp(BigUnsigned(314), 159, 2653) << std::endl; + // Add your own code here to experiment with the library. } catch(char const* err) { std::cout << "The library threw an exception:\n" << err << std::endl; @@ -94,7 +94,7 @@ int main() { } /* -Running the sample program produces this output: +The original sample program produces this output: 3141592653589793238462643383279 314424 @@ -118,5 +118,8 @@ Running the sample program produces this output: 314^8 = 94501169810786918656 314^9 = 29673367320587092457984 314^10 = 9317437338664347031806976 +12 +8 +1931 */ diff --git a/testsuite.cc b/testsuite.cc new file mode 100644 index 0000000..c91c8ad --- /dev/null +++ b/testsuite.cc @@ -0,0 +1,17 @@ +/* Test suite for the library. First, it ``tests'' that all the constructs it + * uses compile successfully. Then, its output to stdout is compared to the + * expected output automatically extracted from slash-slash comments below. */ + +#include "BigIntegerLibrary.hh" + +#include +#include +using namespace std; + +int main() { + +BigUnsigned z(0), one(1), ten(10); +cout << z << ',' << one << ',' << ten << endl; //0,1,10 + +return 0; +} -- 2.34.1