diff options
Diffstat (limited to 'third_party/bigint')
| -rw-r--r-- | third_party/bigint/BigIntegerAlgorithms.cc | 70 | ||||
| -rw-r--r-- | third_party/bigint/BigIntegerAlgorithms.hh | 25 | ||||
| -rw-r--r-- | third_party/bigint/ChangeLog | 146 | ||||
| -rwxr-xr-x | third_party/bigint/run-testsuite | 37 | ||||
| -rw-r--r-- | third_party/bigint/sample.cc | 125 | ||||
| -rw-r--r-- | third_party/bigint/testsuite.cc | 326 |
6 files changed, 0 insertions, 729 deletions
diff --git a/third_party/bigint/BigIntegerAlgorithms.cc b/third_party/bigint/BigIntegerAlgorithms.cc deleted file mode 100644 index 7edebda76a..0000000000 --- a/third_party/bigint/BigIntegerAlgorithms.cc +++ /dev/null @@ -1,70 +0,0 @@ -#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(orig) + s1*n(orig) == m(current) - * r2*m(orig) + s2*n(orig) == n(current) */ - for (;;) { - if (n.isZero()) { - r = r1; s = s1; g = m; - return; - } - // Subtract q times the second invariant from the first invariant. - m.divideWithRemainder(n, q); - r1 -= q*r2; s1 -= q*s2; - - if (m.isZero()) { - r = r2; s = s2; g = n; - return; - } - // Subtract q times the first invariant from the second invariant. - 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.bitLength(); - // For each bit of the exponent, most to least significant... - while (i > 0) { - i--; - // Square. - ans *= ans; - ans %= modulus; - // And multiply if the bit is a 1. - if (exponent.getBit(i)) { - ans *= base2; - ans %= modulus; - } - } - return ans; -} diff --git a/third_party/bigint/BigIntegerAlgorithms.hh b/third_party/bigint/BigIntegerAlgorithms.hh deleted file mode 100644 index b1dd943227..0000000000 --- a/third_party/bigint/BigIntegerAlgorithms.hh +++ /dev/null @@ -1,25 +0,0 @@ -#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/third_party/bigint/ChangeLog b/third_party/bigint/ChangeLog deleted file mode 100644 index ac6927c409..0000000000 --- a/third_party/bigint/ChangeLog +++ /dev/null @@ -1,146 +0,0 @@ - Change Log - -These entries tell you what was added, fixed, or improved in each version as -compared to the previous one. In case you haven't noticed, a version number -roughly corresponds to the release date of that version in `YYYY.MM.DD[.N]' -format, where `.N' goes `.2', `.3', etc. if there are multiple versions on the -same day. The topmost version listed is the one you have. - -2010.04.30 ----------- -- Strengthen the advice about build/IDE configuration in the README. - -2009.05.03 ----------- -- BigUnsigned::{get,set}Bit: Change two remaining `1 <<' to `Blk(1) <<' to work - on systems where sizeof(unsigned int) != sizeof(Blk). Bug reported by Brad - Spencer. -- dataToBigInteger: Change a `delete' to `delete []' to avoid leaking memory. - Bug reported by Nicolás Carrasco. - -2009.03.26 ----------- -- BigUnsignedInABase(std::string) Reject digits too big for the base. - Bug reported by Niakam Kazemi. - -2008.07.20 ----------- -Dennis Yew pointed out serious problems with ambiguities and unwanted -conversions when mixing BigInteger/BigUnsigned and primitive integers. To fix -these, I removed the implicit conversions from BigInteger/BigUnsigned to -primitive integers and from BigInteger to BigUnsigned. Removing the -BigInteger-to-BigUnsigned conversion required changing BigInteger to have a -BigUnsigned field instead of inheriting from it; this was a complex task but -ultimately gave a saner design. At the same time, I went through the entire -codebase, making the formatting and comments prettier and reworking anything I -thought was unclear. I also added a testsuite (currently for 32-bit systems -only); it doesn't yet cover the entire library but should help to ensure that -things work the way they should. - -A number of changes from version 2007.07.07 break compatibility with existing -code that uses the library, but updating that code should be pretty easy: -- BigInteger can no longer be implicitly converted to BigUnsigned. Use - getMagnitude() instead. -- BigUnsigned and BigInteger can no longer be implicitly converted to primitive - integers. Use the toInt() family of functions instead. -- The easy* functions have been renamed to more mature names: - bigUnsignedToString, bigIntegerToString, stringToBigUnsigned, - stringToBigInteger, dataToBigInteger. -- BigInteger no longer supports bitwise operations. Get the magnitude with - getMagnitude() and operate on that instead. -- The old {BigUnsigned,BigInteger}::{divide,modulo} copy-less options have been - removed. Use divideWithRemainder instead. -- Added a base argument to BigUnsignedInABase's digit-array constructor. I - ope no one used that constructor in its broken state anyway. - -Other notable changes: -- Added BigUnsigned functions setBlock, bitLength, getBit, setBit. -- The bit-shifting operations now support negative shift amounts, which shift in - the other direction. -- Added some big-integer algorithms in BigIntegerAlgorithms.hh: gcd, - extendedEuclidean, modinv, modexp. - -2007.07.07 ----------- -Update the "Running the sample program produces this output:" comment in -sample.cc for the bitwise operators. - -2007.06.14 ----------- -- Implement << and >> for BigUnsigned in response to email from Marco Schulze. -- Fix name: DOTR_ALIASED -> DTRT_ALIASED. -- Demonstrate all bitwise operators (&, |, ^, <<, >>) in sample.cc. - -2007.02.16 ----------- -Boris Dessy pointed out that the library threw an exception on "a *= a", so I changed all the put-here operations to handle aliased calls correctly using a temporary copy instead of throwing exceptions. - -2006.08.14 ----------- -In BigUnsigned::bitXor, change allocate(b2->len) to allocate(a2->len): we should allocate enough space for the longer number, not the shorter one! Thanks to Sriram Sankararaman for pointing this out. - -2006.05.03 ----------- -I ran the sample program using valgrind and discovered a `delete s' that should be `delete [] s' and a `len++' before an `allocateAndCopy(len)' that should have been after an `allocateAndCopy(len + 1)'. I fixed both. Yay for valgrind! - -2006.05.01 ----------- -I fixed incorrect results reported by Mohand Mezmaz and related memory corruption on platforms where Blk is bigger than int. I replaced (1 << x) with (Blk(1) << x) in two places in BigUnsigned.cc. - -2006.04.24 ----------- -Two bug fixes: BigUnsigned "++x" no longer segfaults when x grows in length, and BigUnsigned == and != are now redeclared so as to be usable. I redid the Makefile: I removed the *.tag mechanism and hard-coded the library's header dependencies, I added comments, and I made the Makefile more useful for building one's own programs instead of just the sample. - -2006.02.26 ----------- -A few tweaks in preparation for a group to distribute the library. The project Web site has moved; I updated the references. I fixed a typo and added a missing function in NumberlikeArray.hh. I'm using Eclipse now, so you get Eclipse project files. - -2005.03.30 ----------- -Sam Larkin found a bug in `BigInteger::subtract'; I fixed it. - -2005.01.18 ----------- -I fixed some problems with `easyDataToBI'. Due to some multiply declared variables, this function would not compile. However, it is a template function, so the compiler parses it and doesn't compile the parsed representation until something uses the function; this is how I missed the problems. I also removed debugging output from this function. - -2005.01.17 ----------- -A fix to some out-of-bounds accesses reported by Milan Tomic (see the comment under `BigUnsigned::divideWithRemainder'). `BigUnsigned::multiply' and `BigUnsigned::divideWithRemainder' implementations neatened up a bit with the help of a function `getShiftedBlock'. I (finally!) introduced a constant `BigUnsigned::N', the number of bits in a `BigUnsigned::Blk', which varies depending on machine word size. In both code and comments, it replaces the much clunkier `8*sizeof(Blk)'. Numerous other small changes. There's a new conversion routine `easyDataToBI' that will convert almost any format of binary data to a `BigInteger'. - -I have inserted a significant number of new comments. Most explain unobvious aspects of the code. - -2005.01.06 ----------- -Some changes to the way zero-length arrays are handled by `NumberlikeArray', which fixed a memory leak reported by Milan Tomic. - -2004.12.24.2 ------------- -I tied down a couple of loose ends involving division/modulo. I added an explanation of put-here vs. overloaded operators in the sample program; this has confused too many people. Miscellaneous other improvements. - -I believe that, at this point, the Big Integer Library makes no assumptions about the word size of the machine it is using. `BigUnsigned::Blk' is always an `unsigned long', whatever that may be, and its size is computed with `sizeof' when necessary. However, just in case, I would be interested to have someone test the library on a non-32-bit machine to see if it works. - -2004.12.24 ----------- -This is a _major_ upgrade to the library. Among the things that have changed: - -I wrote the original version of the library, particularly the four ``classical algorithms'' in `BigUnsigned.cc', using array indexing. Then I rewrote it to use pointers because I thought that would be faster. But recently, I revisited the code in `BigUnsigned.cc' and found that I could not begin to understand what it was doing. - -I have decided that the drawbacks of pointers, increased coding difficulty and reduced code readability, far outweigh their speed benefits. Plus, any modern optimizing compiler should produce fast code either way. Therefore, I rewrote the library to use array indexing again. (Thank goodness for regular-expression find-and-replace. It saved me a lot of time.) - -The put-here operations `divide' and `modulo' of each of `BigUnsigned' and `BigInteger' have been supplanted by a single operation `divideWithRemainder'. Read the profuse comments for more information on its exact behavior. - -There is a new class `BigUnsignedInABase' that is like `BigUnsigned' but uses a user-specified, small base instead of `256 ^ sizeof(unsigned long)'. Much of the code common to the two has been factored out into `NumberlikeArray'. - -`BigUnsignedInABase' facilitates conversion between `BigUnsigned's and digit-by-digit string representations using `std::string'. Convenience routines to do this conversion are in `BigIntegerUtils.hh'. `iostream' compatibility has been improved. - -I would like to thank Chris Morbitzer for the e-mail message that catalyzed this major upgrade. He wanted a way to convert a string to a BigInteger. One thing just led to another, roughly in reverse order from how they are listed here. - -2004.1216 ---------- -Brad Spencer pointed out a memory leak in `BigUnsigned::divide'. It is fixed in the December 16, 2004 version. - -2004.1205 ---------- -After months of inactivity, I fixed a bug in the `BigInteger' division routine; thanks to David Allen for reporting the bug. I also added simple routines for decimal output to `std::ostream's, and there is a demo that prints out powers of 3. - -~~~~ diff --git a/third_party/bigint/run-testsuite b/third_party/bigint/run-testsuite deleted file mode 100755 index ff73729164..0000000000 --- a/third_party/bigint/run-testsuite +++ /dev/null @@ -1,37 +0,0 @@ -#!/bin/bash - -bad= - -# If you encounter the following problem with Valgrind like I did: -# https://bugzilla.redhat.com/show_bug.cgi?id=455644 -# you can pass the environment variable NO_VALGRIND=1 to run the testsuite -# without it. -if [ "$NO_VALGRIND" ]; then - cmd=(./testsuite) -else - cmd=(valgrind --error-exitcode=1 --leak-check=full ./testsuite) -fi - -set -o pipefail -# Stdout goes directly to testsuite.out; stderr goes down the pipe. -if ! "${cmd[@]}" 2>&1 >testsuite.out | tee testsuite.err; then - echo >&2 'Memory errors!' - bad=1 -fi - -if grep 'LEAK SUMMARY' testsuite.err >/dev/null; then - echo >&2 'Memory leaks!' - bad=1 -fi - -if ! diff -u testsuite.expected testsuite.out; then - echo >&2 'Output is incorrect!' - bad=1 -fi - -if [ $bad ]; then - echo >&2 'Test suite failed!' - exit 1 -else - echo 'Test suite passed.' -fi diff --git a/third_party/bigint/sample.cc b/third_party/bigint/sample.cc deleted file mode 100644 index 62b41df327..0000000000 --- a/third_party/bigint/sample.cc +++ /dev/null @@ -1,125 +0,0 @@ -// Sample program demonstrating the use of the Big Integer Library. - -// Standard libraries -#include <string> -#include <iostream> - -// `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; - - /* 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. - - // The int literal is converted to a BigInteger. - BigInteger d(-314159265); - - /* 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 = stringToBigInteger(s); - - // You can convert the other way too. - std::string s2 = bigIntegerToString(f); - - // f is implicitly stringified and sent to std::cout. - std::cout << f << std::endl; - - /* 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); - 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); - // 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' - // 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. - int maxPower = 10; - BigUnsigned x(1), big314(314); - for (int power = 0; power <= maxPower; power++) { - std::cout << "314^" << power << " = " << x << std::endl; - x *= big314; // A BigInteger assignment operator - } - - // 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; - } - - return 0; -} - -/* -The original sample program produces this output: - -3141592653589793238462643383279 -314424 -313894 -83252135 -1185 -134 -0xFF -0xFF00FFFF -0xFF00FF00 -0x1FFFE00000 -0x3F -314^0 = 1 -314^1 = 314 -314^2 = 98596 -314^3 = 30959144 -314^4 = 9721171216 -314^5 = 3052447761824 -314^6 = 958468597212736 -314^7 = 300959139524799104 -314^8 = 94501169810786918656 -314^9 = 29673367320587092457984 -314^10 = 9317437338664347031806976 -12 -8 -1931 - -*/ diff --git a/third_party/bigint/testsuite.cc b/third_party/bigint/testsuite.cc deleted file mode 100644 index 7cb9768e64..0000000000 --- a/third_party/bigint/testsuite.cc +++ /dev/null @@ -1,326 +0,0 @@ -/* 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. - * - * NOTE: For now, the test suite expects a 32-bit system. On others, some tests - * may fail, and it may be ineffective at catching bugs. TODO: Remedy this. */ - -#include "BigIntegerLibrary.hh" - -#include <string> -#include <iostream> -using namespace std; - -// Evaluate expr and print the result or "error" as appropriate. -#define TEST(expr) do {\ - cout << "Line " << __LINE__ << ": ";\ - try {\ - cout << (expr);\ - } catch (const char *err) {\ - cout << "error";\ - }\ - cout << endl;\ -} while (0) - -const BigUnsigned &check(const BigUnsigned &x) { - unsigned int l = x.getLength(); - if (l != 0 && x.getBlock(l-1) == 0) - cout << "check: Unzapped number!" << endl; - if (l > x.getCapacity()) - cout << "check: Capacity inconsistent with length!" << endl; - return x; -} - -const BigInteger &check(const BigInteger &x) { - if (x.getSign() == 0 && !x.getMagnitude().isZero()) - cout << "check: Sign should not be zero!" << endl; - if (x.getSign() != 0 && x.getMagnitude().isZero()) - cout << "check: Sign should be zero!" << endl; - check(x.getMagnitude()); - return x; -} - -short pathologicalShort = ~((unsigned short)(~0) >> 1); -int pathologicalInt = ~((unsigned int)(~0) >> 1); -long pathologicalLong = ~((unsigned long)(~0) >> 1); - -int main() { - -try { - -BigUnsigned z(0), one(1), ten(10); -TEST(z); //0 -TEST(1); //1 -TEST(10); //10 - -// TODO: Comprehensively test the general and special cases of each function. - -// === Default constructors === - -TEST(check(BigUnsigned())); //0 -TEST(check(BigInteger())); //0 - -// === Block-array constructors === - -BigUnsigned::Blk myBlocks[3]; -myBlocks[0] = 3; -myBlocks[1] = 4; -myBlocks[2] = 0; -BigUnsigned bu(myBlocks, 3); -TEST(check(bu)); //17179869187 -TEST(check(BigInteger(myBlocks, 3))); //17179869187 -TEST(check(BigInteger(bu ))); //17179869187 - -// For nonzero magnitude, reject zero and invalid signs. -TEST(check(BigInteger(myBlocks, 3, BigInteger::positive))); //17179869187 -TEST(check(BigInteger(myBlocks, 3, BigInteger::negative))); //-17179869187 -TEST(check(BigInteger(myBlocks, 3, BigInteger::zero ))); //error -TEST(check(BigInteger(bu, BigInteger::positive))); //17179869187 -TEST(check(BigInteger(bu, BigInteger::negative))); //-17179869187 -TEST(check(BigInteger(bu, BigInteger::zero ))); //error - -// For zero magnitude, force the sign to zero without error. -BigUnsigned::Blk myZeroBlocks[1]; -myZeroBlocks[0] = 0; -TEST(check(BigInteger(myZeroBlocks, 1, BigInteger::positive))); //0 -TEST(check(BigInteger(myZeroBlocks, 1, BigInteger::negative))); //0 -TEST(check(BigInteger(myZeroBlocks, 1, BigInteger::zero ))); //0 - -// === BigUnsigned conversion limits === - -TEST(BigUnsigned(0).toUnsignedLong()); //0 -TEST(BigUnsigned(4294967295U).toUnsignedLong()); //4294967295 -TEST(stringToBigUnsigned("4294967296").toUnsignedLong()); //error - -TEST(BigUnsigned(0).toLong()); //0 -TEST(BigUnsigned(2147483647).toLong()); //2147483647 -TEST(BigUnsigned(2147483648U).toLong()); //error - -// int is the same as long on a 32-bit system -TEST(BigUnsigned(0).toUnsignedInt()); //0 -TEST(BigUnsigned(4294967295U).toUnsignedInt()); //4294967295 -TEST(stringToBigUnsigned("4294967296").toUnsignedInt()); //error - -TEST(BigUnsigned(0).toInt()); //0 -TEST(BigUnsigned(2147483647).toInt()); //2147483647 -TEST(BigUnsigned(2147483648U).toInt()); //error - -TEST(BigUnsigned(0).toUnsignedShort()); //0 -TEST(BigUnsigned(65535).toUnsignedShort()); //65535 -TEST(BigUnsigned(65536).toUnsignedShort()); //error - -TEST(BigUnsigned(0).toShort()); //0 -TEST(BigUnsigned(32767).toShort()); //32767 -TEST(BigUnsigned(32768).toShort()); //error - -// === BigInteger conversion limits === - -TEST(BigInteger(-1).toUnsignedLong()); //error -TEST(BigInteger(0).toUnsignedLong()); //0 -TEST(BigInteger(4294967295U).toUnsignedLong()); //4294967295 -TEST(stringToBigInteger("4294967296").toUnsignedLong()); //error - -TEST(stringToBigInteger("-2147483649").toLong()); //error -TEST(stringToBigInteger("-2147483648").toLong()); //-2147483648 -TEST(BigInteger(-2147483647).toLong()); //-2147483647 -TEST(BigInteger(0).toLong()); //0 -TEST(BigInteger(2147483647).toLong()); //2147483647 -TEST(BigInteger(2147483648U).toLong()); //error - -// int is the same as long on a 32-bit system -TEST(BigInteger(-1).toUnsignedInt()); //error -TEST(BigInteger(0).toUnsignedInt()); //0 -TEST(BigInteger(4294967295U).toUnsignedInt()); //4294967295 -TEST(stringToBigInteger("4294967296").toUnsignedInt()); //error - -TEST(stringToBigInteger("-2147483649").toInt()); //error -TEST(stringToBigInteger("-2147483648").toInt()); //-2147483648 -TEST(BigInteger(-2147483647).toInt()); //-2147483647 -TEST(BigInteger(0).toInt()); //0 -TEST(BigInteger(2147483647).toInt()); //2147483647 -TEST(BigInteger(2147483648U).toInt()); //error - -TEST(BigInteger(-1).toUnsignedShort()); //error -TEST(BigInteger(0).toUnsignedShort()); //0 -TEST(BigInteger(65535).toUnsignedShort()); //65535 -TEST(BigInteger(65536).toUnsignedShort()); //error - -TEST(BigInteger(-32769).toShort()); //error -TEST(BigInteger(-32768).toShort()); //-32768 -TEST(BigInteger(-32767).toShort()); //-32767 -TEST(BigInteger(0).toShort()); //0 -TEST(BigInteger(32767).toShort()); //32767 -TEST(BigInteger(32768).toShort()); //error - -// === Negative BigUnsigneds === - -// ...during construction -TEST(BigUnsigned(short(-1))); //error -TEST(BigUnsigned(pathologicalShort)); //error -TEST(BigUnsigned(-1)); //error -TEST(BigUnsigned(pathologicalInt)); //error -TEST(BigUnsigned(long(-1))); //error -TEST(BigUnsigned(pathologicalLong)); //error - -// ...during subtraction -TEST(BigUnsigned(5) - BigUnsigned(6)); //error -TEST(stringToBigUnsigned("314159265358979323") - stringToBigUnsigned("314159265358979324")); //error -TEST(check(BigUnsigned(5) - BigUnsigned(5))); //0 -TEST(check(stringToBigUnsigned("314159265358979323") - stringToBigUnsigned("314159265358979323"))); //0 -TEST(check(stringToBigUnsigned("4294967296") - BigUnsigned(1))); //4294967295 - -// === BigUnsigned addition === - -TEST(check(BigUnsigned(0) + 0)); //0 -TEST(check(BigUnsigned(0) + 1)); //1 -// Ordinary carry -TEST(check(stringToBigUnsigned("8589934591" /* 2^33 - 1*/) - + stringToBigUnsigned("4294967298" /* 2^32 + 2 */))); //12884901889 -// Creation of a new block -TEST(check(BigUnsigned(0xFFFFFFFFU) + 1)); //4294967296 - -// === BigUnsigned subtraction === - -TEST(check(BigUnsigned(1) - 0)); //1 -TEST(check(BigUnsigned(1) - 1)); //0 -TEST(check(BigUnsigned(2) - 1)); //1 -// Ordinary borrow -TEST(check(stringToBigUnsigned("12884901889") - - stringToBigUnsigned("4294967298"))); //8589934591 -// Borrow that removes a block -TEST(check(stringToBigUnsigned("4294967296") - 1)); //4294967295 - -// === BigUnsigned multiplication and division === - -BigUnsigned a = check(BigUnsigned(314159265) * 358979323); -TEST(a); //112776680263877595 -TEST(a / 123); //916883579381118 -TEST(a % 123); //81 - -TEST(BigUnsigned(5) / 0); //error - -// === Block accessors === - -BigUnsigned b; -TEST(b); //0 -TEST(b.getBlock(0)); //0 -b.setBlock(1, 314); -// Did b grow properly? And did we zero intermediate blocks? -TEST(check(b)); //1348619730944 -TEST(b.getLength()); //2 -TEST(b.getBlock(0)); //0 -TEST(b.getBlock(1)); //314 -// Did b shrink properly? -b.setBlock(1, 0); -TEST(check(b)); //0 - -BigUnsigned bb(314); -bb.setBlock(1, 159); -// Make sure we used allocateAndCopy, not allocate -TEST(bb.getBlock(0)); //314 -TEST(bb.getBlock(1)); //159 -// Blocks beyond the number should be zero regardless of whether they are -// within the capacity. -bb.add(1, 2); -TEST(bb.getBlock(0)); //3 -TEST(bb.getBlock(1)); //0 -TEST(bb.getBlock(2)); //0 -TEST(bb.getBlock(314159)); //0 - -// === Bit accessors === - -TEST(BigUnsigned(0).bitLength()); //0 -TEST(BigUnsigned(1).bitLength()); //1 -TEST(BigUnsigned(4095).bitLength()); //12 -TEST(BigUnsigned(4096).bitLength()); //13 -// 5 billion is between 2^32 (about 4 billion) and 2^33 (about 8 billion). -TEST(stringToBigUnsigned("5000000000").bitLength()); //33 - -// 25 is binary 11001. -BigUnsigned bbb(25); -TEST(bbb.getBit(4)); //1 -TEST(bbb.getBit(3)); //1 -TEST(bbb.getBit(2)); //0 -TEST(bbb.getBit(1)); //0 -TEST(bbb.getBit(0)); //1 -TEST(bbb.bitLength()); //5 -// Effectively add 2^32. -bbb.setBit(32, true); -TEST(bbb); //4294967321 -bbb.setBit(31, true); -bbb.setBit(32, false); -TEST(check(bbb)); //2147483673 - -// === Combining BigUnsigned, BigInteger, and primitive integers === - -BigUnsigned p1 = BigUnsigned(3) * 5; -TEST(p1); //15 -/* In this case, we would like g++ to implicitly promote the BigUnsigned to a - * BigInteger, but it seems to prefer converting the -5 to a BigUnsigned, which - * causes an error. If I take out constructors for BigUnsigned from signed - * primitive integers, the BigUnsigned(3) becomes ambiguous, and if I take out - * all the constructors but BigUnsigned(unsigned long), g++ uses that - * constructor and gets a wrong (positive) answer. Thus, I think we'll just - * have to live with this cast. */ -BigInteger p2 = BigInteger(BigUnsigned(3)) * -5; -TEST(p2); //-15 - -// === Test some previous bugs === - -{ - /* Test that BigInteger division sets the sign to zero. - * Bug reported by David Allen. */ - BigInteger num(3), denom(5), quotient; - num.divideWithRemainder(denom, quotient); - check(quotient); - num = 5; - num.divideWithRemainder(denom, quotient); - check(num); -} - -{ - /* Test that BigInteger subtraction sets the sign properly. - * Bug reported by Samuel Larkin. */ - BigInteger zero(0), three(3), ans; - ans = zero - three; - TEST(check(ans).getSign()); //-1 -} - -{ - /* Test that BigInteger multiplication shifts bits properly on systems - * where long is bigger than int. (Obviously, this would only catch the - * bug when run on such a system.) - * Bug reported by Mohand Mezmaz. */ - BigInteger f=4; f*=3; - TEST(check(f)); //12 -} - -{ - /* Test that bitwise XOR allocates the larger length. - * Bug reported by Sriram Sankararaman. */ - BigUnsigned a(0), b(3), ans; - ans = a ^ b; - TEST(ans); //3 -} - -{ - /* Test that an aliased multiplication works. - * Bug reported by Boris Dessy. */ - BigInteger num(5); - num *= num; - TEST(check(num)); //25 -} - -{ - /* Test that BigUnsignedInABase(std::string) constructor rejects digits - * too big for the specified base. - * Bug reported by Niakam Kazemi. */ - TEST(BigUnsignedInABase("f", 10)); //error -} - -} catch (const char *err) { - cout << "UNCAUGHT ERROR: " << err << endl; -} - -return 0; -} |