Software Público Brasileiro

/***************************************************************************
 *   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 <string>

#include <stdint.h>

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 (&gt;&gt;&gt;) 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 <i>must</i> 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 <i>big-endian</i> 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 (<tt>mag[0]</tt>) 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
		 * <tt>Character.digit</tt>.  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 <tt>val</tt>.
		 */
		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<sup>-100</sup>.
		 *
		 * \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 <tt>bitLength</tt> bits that is probably prime
		 */
		static BigInteger * ProbablePrime(int length);
		
		/**
		 * \brief Returns the first integer greater than this <code>BigInteger</code> that
		 * is probably prime.  The probability that the number returned by this
		 * method is composite does not exceed 2<sup>-100</sup>. This method will
		 * never skip over a prime when searching: if it returns <tt>p</tt>, there
		 * is no prime <tt>q</tt> such that <tt>this &lt; q &lt; p</tt>.
		 *
		 * \return the first integer greater than this <code>BigInteger</code> 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 <tt>(this + val)</tt>.
		 *
		 * \param  val value to be added to this BigInteger.
		 * \return <tt>this + val</tt>
		 */
		BigInteger & operator+(BigInteger &value);
		
		/**
		 * Returns a BigInteger whose value is <tt>(this - val)</tt>.
		 *
		 * @param  val value to be subtracted from this BigInteger.
		 * @return <tt>this - val</tt>
		 */
		BigInteger & operator-(BigInteger &value);
		
		/**
		 * Returns a BigInteger whose value is <tt>(this / val)</tt>.
		 *
		 * \param  val value by which this BigInteger is to be divided.
		 * \return <tt>this / val</tt>
		 */
		BigInteger & Divide(BigInteger *value);
		
		/**
		 * Returns an array of two BigIntegers containing <tt>(this / val)</tt>
		 * followed by <tt>(this % val)</tt>.
		 *
		 * \param  val value by which this BigInteger is to be divided, and the remainder computed.
		 * \return an array of two BigIntegers: the quotient <tt>(this / val)</tt>
		 *	       is the initial element, and the remainder <tt>(this % val)</tt>
		 *	       is the final element.
		 */
		BigInteger & DivideAndRemainder(BigInteger *value);
		
		/**
		 * Returns a BigInteger whose value is <tt>(this % val)</tt>.
		 *
		 * @param  val value by which this BigInteger is to be divided, and the
		 *	       remainder computed.
		 * @return <tt>this % val</tt>
		 * @throws ArithmeticException <tt>val==0</tt>
		 */
		BigInteger & Remainder(BigInteger *value);
		
		/**
		 * \brief Returns a BigInteger whose value is <tt>(this<sup>exponent</sup>)</tt>.
		 * Note that <tt>exponent</tt> is an integer rather than a BigInteger.
		 *
		 * \param  exponent exponent to which this BigInteger is to be raised.
		 * \return <tt>this<sup>exponent</sup></tt>
		 */
		BigInteger & Pow(int exponent);
		
		/**
		 * \brief Returns a BigInteger whose value is the greatest common divisor of
		 * <tt>abs(this)</tt> and <tt>abs(val)</tt>.  Returns 0 if
		 * <tt>this==0 &amp;&amp; val==0</tt>.
		 *
		 * \param  val value with which the GCD is to be computed.
		 * \return <tt>GCD(abs(this), abs(val))</tt>
		 */
		BigInteger & GCD(BigInteger *val);
		
		/**
		 * Returns a BigInteger whose value is the absolute value of this
		 * BigInteger. 
		 *
		 * @return <tt>abs(this)</tt>
		 */
		BigInteger & Absolute();
		
		/**
		 * Returns a BigInteger whose value is <tt>(-this)</tt>.
		 *
		 * @return <tt>-this</tt>
		 */
		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 <tt>(this mod m</tt>).  This method
		 * differs from <tt>remainder</tt> in that it always returns a
		 * <i>non-negative</i> BigInteger.
		 *
		 * \param  m the modulus.
		 * \return <tt>this mod m</tt>
		 */
		BigInteger & Mod(BigInteger *value);
		
		/**
		 * Returns a BigInteger whose value is <tt>(this &lt;&lt; n)</tt>.
		 * The shift distance, <tt>n</tt>, may be negative, in which case
		 * this method performs a right shift.
		 * (Computes <tt>floor(this * 2<sup>n</sup>)</tt>.)
		 *
		 * @param  n shift distance, in bits.
		 * @return <tt>this &lt;&lt; n</tt>
		 * @see #shiftRight
		 */
		BigInteger & ShiftLeft(int n);
		
		/**
		 * Returns a BigInteger whose value is <tt>(this &gt;&gt; n)</tt>.  Sign
		 * extension is performed.  The shift distance, <tt>n</tt>, may be
		 * negative, in which case this method performs a left shift.
		 * (Computes <tt>floor(this / 2<sup>n</sup>)</tt>.) 
		 *
		 * @param  n shift distance, in bits.
		 * @return <tt>this &gt;&gt; n</tt>
		 * @see #shiftLeft
		 */
		BigInteger & ShiftRight(int n);
		
		/**
		 * \brief Returns a BigInteger whose value is <tt>(this &amp; val)</tt>.  (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 <tt>this &amp; val</tt>
		 */
		BigInteger & And(BigInteger *value);
		
		/**
		 * \brief Returns a BigInteger whose value is <tt>(this | val)</tt>.  (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 <tt>this | val</tt>
		 */
		BigInteger & Or(BigInteger *value);
		
		/**
		 * \brief Returns a BigInteger whose value is <tt>(this ^ val)</tt>.  (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 <tt>this ^ val</tt>
		 */
		BigInteger & Xor(BigInteger *value);
		
		/**
		 * Returns a BigInteger whose value is <tt>(~this)</tt>.  (This method
		 * returns a negative value if and only if this BigInteger is
		 * non-negative.)
		 *
		 * @return <tt>~this</tt>
		 */
		BigInteger & Not();
		
		/**
		 * Returns a BigInteger whose value is <tt>(this &amp; ~val)</tt>.  This
		 * method, which is equivalent to <tt>and(val.not())</tt>, is provided as
		 * a convenience for masking operations.  (This method returns a negative
		 * BigInteger if and only if <tt>this</tt> is negative and <tt>val</tt> is
		 * positive.)
		 *
		 * \param val value to be complemented and AND'ed with this BigInteger.
		 * \return <tt>this &amp; ~val</tt>
		 */
		BigInteger & AndNot(BigInteger *value);
		
		
		/**
		 * \brief Returns <tt>true</tt> if and only if the designated bit is set.
		 * (Computes <tt>((this &amp; (1&lt;&lt;n)) != 0)</tt>.)
		 *
		 * \param  n index of bit to test.
		 * \return <tt>true</tt> 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 <tt>(this | (1&lt;&lt;n))</tt>.)
		 *
		 * @param  n index of bit to set.
		 * @return <tt>this | (1&lt;&lt;n)</tt>
		 */
		BigInteger & SetBit(int n);
		
		/**
		 * \brief Returns a BigInteger whose value is equivalent to this BigInteger
		 * with the designated bit cleared.
		 * (Computes <tt>(this &amp; ~(1&lt;&lt;n))</tt>.)
		 *
		 * \param  n index of bit to clear.
		 * \return <tt>this & ~(1&lt;&lt;n)</tt>
		 */
		BigInteger & ClearBit(int n);
		
		/**
		 * \brief Returns a BigInteger whose value is equivalent to this BigInteger
		 * with the designated bit flipped.
		 * (Computes <tt>(this ^ (1&lt;&lt;n))</tt>.)
		 *
		 * \param  n index of bit to flip.
		 * \return <tt>this ^ (1&lt;&lt;n)</tt>
		 */
		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 <tt>(this==0? -1 : log<sub>2</sub>(this &amp; -this))</tt>.)
		 *
		 * 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, <i>excluding</i> a sign bit.
		 * For positive BigIntegers, this is equivalent to the number of bits in
		 * the ordinary binary representation.  (Computes
		 * <tt>(ceil(log<sub>2</sub>(this &lt; 0 ? -this : this+1)))</tt>.)
		 *
		 * 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, <i>excluding</i> a sign bit.
		 */
		int GetBitLength();
		
		/**
		 * \brief Returns <tt>true</tt> if this BigInteger is probably prime,
		 * <tt>false</tt> if it's definitely composite.  If
		 * <tt>certainty</tt> is <tt> &lt;= 0</tt>, <tt>true</tt> is
		 * returned.
		 *
		 * \param  certainty a measure of the uncertainty that the caller is
		 *	       willing to tolerate: if the call returns <tt>true</tt>
		 *	       the probability that this BigInteger is prime exceeds
		 *	       <tt>(1 - 1/2<sup>certainty</sup>)</tt>.  The execution time of
		 * 	       this method is proportional to the value of this parameter.
		 * \return <tt>true</tt> if this BigInteger is probably prime,
		 * 	       <tt>false</tt> 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 (&lt;, ==, &gt;, &gt;=, !=, &lt;=).  The
		 * suggested idiom for performing these comparisons is:
		 * <tt>(x.compareTo(y)</tt> &lt;<i>op</i>&gt; <tt>0)</tt>,
		 * where &lt;<i>op</i>&gt; 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 <tt>val</tt>.
		 */
		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 <tt>true</tt> 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 <tt>val</tt>.
		 *
		 * \param  val value with which the minimum is to be computed.
		 * \return the BigInteger whose value is the lesser of this BigInteger and 
		 *	       <tt>val</tt>.  If they are equal, either may be returned.
		 */
		BigInteger & Minimum(BigInteger *value);

		/**
		 * \brief Returns the maximum of this BigInteger and <tt>val</tt>.
		 *
		 * \param  val value with which the maximum is to be computed.
		 * \return the BigInteger whose value is the greater of this and
		 * <tt>val</tt>.  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
		 * <tt>Integer.tostd::string</tt>).  The digit-to-character mapping
		 * provided by <tt>Character.forDigit</tt> is used, and a minus
		 * sign is prepended if appropriate.  (This representation is
		 * compatible with the {@link #BigInteger(std::string, int) (std::string,
		 * <code>int</code>)} 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
		 * <tt>Character.forDigit</tt> 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 <code>int</code>.  This
		 * conversion is analogous to a <a
		 * href="http://java.sun.com/docs/books/jls/second_edition/html/conversions.doc.html#25363"><i>narrowing
		 * primitive conversion</i></a> from <code>long</code> to
		 * <code>int</code> as defined in the <a
		 * href="http://java.sun.com/docs/books/jls/html/">Java Language
		 * Specification</a>: if this BigInteger is too big to fit in an
		 * <code>int</code>, 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 <code>int</code>.
		 */
		long long GetValue();
			
};
		
};

#endif