/*************************************************************************** * Copyright (C) 2005 by Jeff Ferr * * root@sat * * * * This program is free software; you can redistribute it and/or modify * * it under the terms of the GNU General Public License as published by * * the Free Software Foundation; either version 2 of the License, or * * (at your option) any later version. * * * * This program is distributed in the hope that it will be useful, * * but WITHOUT ANY WARRANTY; without even the implied warranty of * * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the * * GNU General Public License for more details. * * * * You should have received a copy of the GNU General Public License * * along with this program; if not, write to the * * Free Software Foundation, Inc., * * 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. * a***************************************************************************/ #ifndef J_BIGINTEGER_H #define J_BIGINTEGER_H #include "jobject.h" #include #include namespace jmath { /** * \brief Immutable arbitrary-precision integers. * Additionally, BigInteger provides operations for modular arithmetic, GCD * calculation, primality testing, prime generation, bit manipulation, * and a few other miscellaneous operations. * Semantics of shift operations extend those of shift operators * to allow for negative shift distances. A right-shift with a negative * shift distance results in a left shift, and vice-versa. The unsigned * right shift operator (>>>) is omitted, as this operation makes * little sense in combination with the "infinite word size" abstraction * provided by this class. * Bit operations operate on a single bit of the two's-complement * representation of their operand. If necessary, the operand is sign- * extended so that it contains the designated bit. None of the single-bit * operations can produce a BigInteger with a different sign from the * BigInteger being operated on, as they affect only a single bit, and the * "infinite word size" abstraction provided by this class ensures that there * are infinitely many "virtual sign bits" preceding each BigInteger. * * \author Jeff Ferr */ class BigInteger : public virtual jcommon::Object{ private: /** * \brief The signum of this BigInteger: -1 for negative, 0 for zero, or * 1 for positive. Note that the BigInteger zero must have * a signum of 0. This is necessary to ensures that there is exactly one * representation for each BigInteger value. */ int _signal; /** \brief */ uint8_t *_integer; /** * \brief The magnitude of this BigInteger, in big-endian order: the * zeroth element of this array is the most-significant int of the * magnitude. The magnitude must be "minimal" in that the most-significant * int (mag[0]) must be non-zero. This is necessary to * ensure that there is exactly one representation for each BigInteger * value. Note that this implies that the BigInteger zero has a * zero-length mag array. */ int _integer_length; public: /** * \brief Translates the std::string representation of a BigInteger in the specified * radix into a BigInteger. The std::string representation consists of an * optional minus sign followed by a sequence of one or more digits in the * specified radix. The character-to-digit mapping is provided by * Character.digit. The std::string may not contain any extraneous * characters (whitespace, for example). * * \param val std::string representation of BigInteger. * \param radix radix to be used in interpreting val. */ BigInteger(std::string value, int radix = 10); /** * \brief * */ virtual ~BigInteger(); /** * \brief * */ bool IsValid(std::string value, int radix); /** * \brief Returns a positive BigInteger that is probably prime, with the * specified bitLength. The probability that a BigInteger returned * by this method is composite does not exceed 2-100. * * \param bitLength bitLength of the returned BigInteger. * \param rnd source of random bits used to select candidates to be * tested for primality. * \return a BigInteger of bitLength bits that is probably prime */ static BigInteger * ProbablePrime(int length); /** * \brief Returns the first integer greater than this BigInteger that * is probably prime. The probability that the number returned by this * method is composite does not exceed 2-100. This method will * never skip over a prime when searching: if it returns p, there * is no prime q such that this < q < p. * * \return the first integer greater than this BigInteger that is probably prime. */ BigInteger * NextProbablePrime(); /** * \brief * */ bool operator==(const BigInteger &value); /** * \brief * */ bool operator>(const BigInteger &value); /** * \brief * */ bool operator<(const BigInteger &value); /** * \brief Returns a BigInteger whose value is (this + val). * * \param val value to be added to this BigInteger. * \return this + val */ BigInteger & operator+(BigInteger &value); /** * Returns a BigInteger whose value is (this - val). * * @param val value to be subtracted from this BigInteger. * @return this - val */ BigInteger & operator-(BigInteger &value); /** * Returns a BigInteger whose value is (this / val). * * \param val value by which this BigInteger is to be divided. * \return this / val */ BigInteger & Divide(BigInteger *value); /** * Returns an array of two BigIntegers containing (this / val) * followed by (this % val). * * \param val value by which this BigInteger is to be divided, and the remainder computed. * \return an array of two BigIntegers: the quotient (this / val) * is the initial element, and the remainder (this % val) * is the final element. */ BigInteger & DivideAndRemainder(BigInteger *value); /** * Returns a BigInteger whose value is (this % val). * * @param val value by which this BigInteger is to be divided, and the * remainder computed. * @return this % val * @throws ArithmeticException val==0 */ BigInteger & Remainder(BigInteger *value); /** * \brief Returns a BigInteger whose value is (thisexponent). * Note that exponent is an integer rather than a BigInteger. * * \param exponent exponent to which this BigInteger is to be raised. * \return thisexponent */ BigInteger & Pow(int exponent); /** * \brief Returns a BigInteger whose value is the greatest common divisor of * abs(this) and abs(val). Returns 0 if * this==0 && val==0. * * \param val value with which the GCD is to be computed. * \return GCD(abs(this), abs(val)) */ BigInteger & GCD(BigInteger *val); /** * Returns a BigInteger whose value is the absolute value of this * BigInteger. * * @return abs(this) */ BigInteger & Absolute(); /** * Returns a BigInteger whose value is (-this). * * @return -this */ BigInteger & Negate(); /** * Returns the signum function of this BigInteger. * * @return -1, 0 or 1 as the value of this BigInteger is negative, zero or * positive. */ bool IsNegative(); /** * \brief Returns a BigInteger whose value is (this mod m). This method * differs from remainder in that it always returns a * non-negative BigInteger. * * \param m the modulus. * \return this mod m */ BigInteger & Mod(BigInteger *value); /** * Returns a BigInteger whose value is (this << n). * The shift distance, n, may be negative, in which case * this method performs a right shift. * (Computes floor(this * 2n).) * * @param n shift distance, in bits. * @return this << n * @see #shiftRight */ BigInteger & ShiftLeft(int n); /** * Returns a BigInteger whose value is (this >> n). Sign * extension is performed. The shift distance, n, may be * negative, in which case this method performs a left shift. * (Computes floor(this / 2n).) * * @param n shift distance, in bits. * @return this >> n * @see #shiftLeft */ BigInteger & ShiftRight(int n); /** * \brief Returns a BigInteger whose value is (this & val). (This * method returns a negative BigInteger if and only if this and val are * both negative.) * * \param val value to be AND'ed with this BigInteger. * \return this & val */ BigInteger & And(BigInteger *value); /** * \brief Returns a BigInteger whose value is (this | val). (This method * returns a negative BigInteger if and only if either this or val is * negative.) * * \param val value to be OR'ed with this BigInteger. * \return this | val */ BigInteger & Or(BigInteger *value); /** * \brief Returns a BigInteger whose value is (this ^ val). (This method * returns a negative BigInteger if and only if exactly one of this and * val are negative.) * * \param val value to be XOR'ed with this BigInteger. * \return this ^ val */ BigInteger & Xor(BigInteger *value); /** * Returns a BigInteger whose value is (~this). (This method * returns a negative value if and only if this BigInteger is * non-negative.) * * @return ~this */ BigInteger & Not(); /** * Returns a BigInteger whose value is (this & ~val). This * method, which is equivalent to and(val.not()), is provided as * a convenience for masking operations. (This method returns a negative * BigInteger if and only if this is negative and val is * positive.) * * \param val value to be complemented and AND'ed with this BigInteger. * \return this & ~val */ BigInteger & AndNot(BigInteger *value); /** * \brief Returns true if and only if the designated bit is set. * (Computes ((this & (1<<n)) != 0).) * * \param n index of bit to test. * \return true if and only if the designated bit is set. */ bool TestBit(int n); /** * Returns a BigInteger whose value is equivalent to this BigInteger * with the designated bit set. (Computes (this | (1<<n)).) * * @param n index of bit to set. * @return this | (1<<n) */ BigInteger & SetBit(int n); /** * \brief Returns a BigInteger whose value is equivalent to this BigInteger * with the designated bit cleared. * (Computes (this & ~(1<<n)).) * * \param n index of bit to clear. * \return this & ~(1<<n) */ BigInteger & ClearBit(int n); /** * \brief Returns a BigInteger whose value is equivalent to this BigInteger * with the designated bit flipped. * (Computes (this ^ (1<<n)).) * * \param n index of bit to flip. * \return this ^ (1<<n) */ BigInteger & FlipBit(int n); /** * \brief Returns the index of the rightmost (lowest-order) one bit in this * BigInteger (the number of zero bits to the right of the rightmost * one bit). Returns -1 if this BigInteger contains no one bits. * (Computes (this==0? -1 : log2(this & -this)).) * * Initialize lowestSetBit field the first time this method is * executed. This method depends on the atomicity of int modifies; * without this guarantee, it would have to be synchronized. * * \return index of the rightmost one bit in this BigInteger. */ int GetLowestSetBit(); /** * \brief Returns the number of bits in the minimal two's-complement * representation of this BigInteger, excluding a sign bit. * For positive BigIntegers, this is equivalent to the number of bits in * the ordinary binary representation. (Computes * (ceil(log2(this < 0 ? -this : this+1))).) * * Initialize bitLength field the first time this method is executed. * This method depends on the atomicity of int modifies; without * this guarantee, it would have to be synchronized. * * \return number of bits in the minimal two's-complement * representation of this BigInteger, excluding a sign bit. */ int GetBitLength(); /** * \brief Returns true if this BigInteger is probably prime, * false if it's definitely composite. If * certainty is <= 0, true is * returned. * * \param certainty a measure of the uncertainty that the caller is * willing to tolerate: if the call returns true * the probability that this BigInteger is prime exceeds * (1 - 1/2certainty). The execution time of * this method is proportional to the value of this parameter. * \return true if this BigInteger is probably prime, * false if it's definitely composite. */ bool IsProbablePrime(int certainty); /** * Compares this BigInteger with the specified BigInteger. This method is * provided in preference to individual methods for each of the six * boolean comparison operators (<, ==, >, >=, !=, <=). The * suggested idiom for performing these comparisons is: * (x.compareTo(y) <op> 0), * where <op> is one of the six comparison operators. * * @param val BigInteger to which this BigInteger is to be compared. * @return -1, 0 or 1 as this BigInteger is numerically less than, equal * to, or greater than val. */ int Compare(jcommon::Object *o); /** * Compares this BigInteger with the specified jcommon::Object *for equality. * * @param x jcommon::Object *to which this BigInteger is to be compared. * @return true if and only if the specified jcommon::Object *is a * BigInteger whose value is numerically equal to this BigInteger. */ bool Equals(jcommon::Object *o); /** * \brief Returns the minimum of this BigInteger and val. * * \param val value with which the minimum is to be computed. * \return the BigInteger whose value is the lesser of this BigInteger and * val. If they are equal, either may be returned. */ BigInteger & Minimum(BigInteger *value); /** * \brief Returns the maximum of this BigInteger and val. * * \param val value with which the maximum is to be computed. * \return the BigInteger whose value is the greater of this and * val. If they are equal, either may be returned. */ BigInteger & Maximum(BigInteger *value); /** * \brief Returns the hash code for this BigInteger. * * \return hash code for this BigInteger. */ virtual unsigned long long Hash(); /** * \brief Returns the std::string representation of this BigInteger in the * given radix. If the radix is outside the range from {@link * Character#MIN_RADIX} to {@link Character#MAX_RADIX} inclusive, * it will default to 10 (as is the case for * Integer.tostd::string). The digit-to-character mapping * provided by Character.forDigit is used, and a minus * sign is prepended if appropriate. (This representation is * compatible with the {@link #BigInteger(std::string, int) (std::string, * int)} constructor.) * * \param radix radix of the std::string representation. * @return std::string representation of this BigInteger in the given radix. */ std::string what(int radix); /** * Returns the decimal std::string representation of this BigInteger. * The digit-to-character mapping provided by * Character.forDigit is used, and a minus sign is * prepended if appropriate. (This representation is compatible * with the {@link #BigInteger(std::string) (std::string)} constructor, and * allows for std::string concatenation with Java's + operator.) * * @return decimal std::string representation of this BigInteger. * @see Character#forDigit * @see #BigInteger(java.lang.std::string) */ std::string what(); /** * \brief Converts this BigInteger to an int. This * conversion is analogous to a narrowing * primitive conversion from long to * int as defined in the Java Language * Specification: if this BigInteger is too big to fit in an * int, only the low-order 32 bits are returned. * Note that this conversion can lose information about the * overall magnitude of the BigInteger value as well as return a * result with the opposite sign. * * \return this BigInteger converted to an int. */ long long GetValue(); }; }; #endif