- 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.
*.o
sample
+testsuite
+testsuite.expected
+testsuite.out
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);
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() {
--- /dev/null
+#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;
+}
--- /dev/null
+#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
#include "NumberlikeArray.hh"
#include "BigUnsigned.hh"
#include "BigInteger.hh"
+#include "BigIntegerAlgorithms.hh"
#include "BigUnsignedInABase.hh"
#include "BigIntegerUtils.hh"
#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();
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 << '-';
#include <string>
#include <iostream>
-/*
- * 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 <class T>
-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);
// 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.
* the result contain the desired binary data.
*/
template <class T>
-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);
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
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;
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
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;
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);
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);
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);
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;
*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);
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
-#
-# 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
# 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 :
-/*
- * 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 <string>
#include <iostream>
-// 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.
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;
}
/*
-Running the sample program produces this output:
+The original sample program produces this output:
3141592653589793238462643383279
314424
314^8 = 94501169810786918656
314^9 = 29673367320587092457984
314^10 = 9317437338664347031806976
+12
+8
+1931
*/
--- /dev/null
+/* 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 <string>
+#include <iostream>
+using namespace std;
+
+int main() {
+
+BigUnsigned z(0), one(1), ten(10);
+cout << z << ',' << one << ',' << ten << endl; //0,1,10
+
+return 0;
+}
Matt McCutchen's Web Site / bigint / bigint.git / commitdiff