Next: , Previous: Building MPIR.Net, Up: .Net Interface   [Index]


13.3 MPIR.Net Integers

Class: HugeInt : IntegerExpression, IDisposable

The MPIR.Net type for the MPIR multi-precision integer is HugeInt. A closely related type is IntegerExpression, which is returned from all operators and methods whose value semantics are to compute another number from the source instance and any arguments. HugeInt derives from IntegerExpression, and many operations are defined on the expression class. Operations defined on HugeInt but not on IntegerExpression are typically those that modify the value of the source number itself, and thus performing them on an expression is meaningless. Because through inheritance all operations are available on HugeInt, the descriptions below do not specifically indicate whether each operator or method is defined for expressions, or just for HugeInt instances. For the sake of brevity, they are listed as if they were methods of the HugeInt class. Visual Studio provides Intellisense and immediate feedback to help sort out which operations are available on expressions.

Below is a brief summary of the supported multi-precision integer methods and operators. To avoid repetition, implementation details are ommitted. Since MPIR native functions are called behind the scenes, review Integer Functions for further details about the native implementations.

Constructor: HugeInt ()
Constructor: HugeInt (int/long n)
Constructor: HugeInt (uint/ulong n)
Constructor: HugeInt (double n)

Constructs a HugeInt object. Single-limb constructors vary by architecture, 32-bit builds take an int or uint argument, 64-bit builds take a long or ulong. Any necessary conversion follows the corresponding C function, for example double follows mpz_set_d (see Assigning Integers).

Constructor: HugeInt (string s)
Constructor: HugeInt (string s, int base)

Constructs a HugeInt converted from a string using mpz_set_str (see Assigning Integers). If the string is not a valid integer, an exception is thrown.

Constructor: HugeInt (IntegerExpression e)

Evaluates the supplied expression and saves its result to the new instance. Because HugeInt is derived from IntegerExpression, this constructor can be used to make a copy of an existing variable, i.e. HugeInt a = new HugeInt(b); without creating any permanent association between them.

Static Method: static HugeInt Allocate (uint/ulong bits)
Method: void Reallocate (uint/ulong bits)

Controls the capacity in bits of the allocated integer.

Property: int AllocatedSize

Returns the number of limbs currently allocated.

Method: ulong Size ()

Returns the number of limbs currently used.

Method: long GetLimb (mp_size_t index)

Returns the specified limb.

Method: bool FitsUlong () //64-bit builds only
Method: bool FitsLong () //64-bit builds only
Method: bool FitsUint ()
Method: bool FitsInt ()
Method: bool FitsUshort ()
Method: bool FitsShort ()
Method: long ApproximateSizeInBase (int base)

Checks whether the number would fit in one of the built-in .Net types.

Method: string ToString ()
Method: string ToString (int base)
Method: string ToString (int base, bool lowercase)

Returns the string representation of the number. The default base is 10, and the parameterless overload is limited to 256 least significant digits by default, producing a leading ellipsis (i.e. ...12345) when the number has more digits. This is done to prevent huge numbers from unexpectedly consuming large amounts of memory in the debugger. The maximum number of digits output is configurable via the MpirSettings.ToStringDigits property, where zero means unlimited. The other overloads always output all digits.

Method: int ToInt () //32-bit builds
Method: uint ToUint () //32-bit builds
Method: long ToLong () //64-bit builds
Method: ulong ToUlong () //64-bit builds
Method: double ToDouble ()
Method: double ToDouble (out int/long exp)

Converts the number to a primitive (built-in) .Net type, assuming it fits, which can be determined by calling one of the Fits... methods.

Property: IntegerExpression Value

Getting this property is essentially a no-op, as it returns the object instance itself. This never needs to be done explicitly, but is used implicitly in statements like a.Value += 5;

Setting the Value property evaluates the assigned expression and saves the result to the object.

Method: void SetTo (int/long value) // 32/64-bit builds
Method: void SetTo (uint/ulong value) // 32/64-bit builds
Method: void SetTo (double value)
Method: void SetTo (string value)
Method: void SetTo (string value, int base)
Method: void SetTo (RationalExpression value)
Method: void SetTo (FloatExpression value)

Sets the value of existing variable from types other than IntegerExpression.

Method: void Swap (HugeInt a)

Swaps the values of the two objects. This is an O(1) operation.

Arithmetic operators (+, -, *, /, %) are overloaded to allow integers to participate in expressions much like primitive integers can. Single-limb primitive types can be used. These operators will also accept RationalExpression arguments, producing a RationalExpression result. Some expression types expose additional methods, these are listed below. Invoking these methods does not prevent the expression from participating in further expressions.

Expressions resulting from division or computing a modulo allow setting an explicit rounding mode:

c.Value = (a / b).Rounding(RoundingModes.Ceiling) + 4;
d.Value = (a % b).Rounding(RoundingModes.Floor) + 4;

Division expressions optionally allow the remainder to be saved:

c.Value = (a / b).SavingRemainderTo(e) + 4;

When dividing by a limb, the remainder is a single limb and is saved to an unsigned limb variable. However, passing this variable as an out argument would not work because of the deferred evaluation. Instead, a delegate is passed which is called during evaluation:

ulong/uint remainder; // 64/32-bit builds
d.Value = (a / 100).SettingRemainderTo(x => remainder = x) + 4;

Symmetrically, the modulo expressions (%) allow the quotient to be saved:

c.Value = (a % b).SavingQuotientTo(e).RoundingMode(RoundingModes.Ceiling) + 4;
ulong/uint quotient; // 64/32-bit builds
d.Value = (a % 100).SettingQuotientTo(x => quotient = x) + 4;
Method: uint/ulong Mod (uint/ulong divisor)
Method: uint/ulong Mod (uint/ulong divisor, RoundingModes roundingMode)

Computes the absolute value of the remainder from division of the source number by the specified divisor. This operation differs from using the % operator by where the result is saved. The % operator returns an expression, and a HugeInt variable is required to receive the result when the expression is assigned to its Value property. The Mod method, on the other hand, computes and returns the remainder immediately since it’s a primitive type (single limb), and no destination HugeInt variable is needed.

Operator ^ serves dual purposes: when the right operand is a single limb, it raises the source number to a power, if the right operand is an IntegerExpression it performs a bitwise XOR.

Comparison operators (==, !=, <, <=, >, >=) accept IntegerExpression, single-limb, or double arguments, but do not accept RationalExpression because that would require an awkward explicit cast when comparing with null.

Method: int CompareTo (IntegerExpression a)
Method: bool Equals (IntegerExpression a)

Implement IComparable<IntegerExpression> and IEquatable<IntegerExpression> for strongly-typed comparisons.

Method: int CompareTo (object a)
Method: bool Equals (object a)

Implement IComparable and equality check for any object. These accept a RationalExpression as an argument, allowing cross-type comparisons not possible with operators.

Method: int GetHashCode ()

This object override computes the hash code. This is an O(N) operation where N is the number of limbs in use. Changing a number’s Value changes its hash code, so this should not be done on any object that has been added to a hash table or dictionary.

Method: int CompareAbsTo (IntegerExpression a)
Method: int CompareAbsTo (uint/ulong a)
Method: int CompareAbsTo (double a)

Compares the absolute value of the number with the operand.

Method: int Sign ()

Returns the number’s sign.

Bit shift operators (<<, >>) accept an unsigned limb operand.

The right shift (>>) expression provides a method to compute the modulo, rather than the default quotient:

var a = new HugeInt("0x1357");
Debug.WriteLine((a >> 8).ToString(16)); //prints 13
Debug.WriteLine((a >> 8).Remainder().ToString(16)); //prints 57

Bitwize operators (&, |, ^, ~) are defined for IntegerExpression operands only. Note that operator ^ is also defined for a limb operand, and in that case computes a power.

Method: bool GetBit (uint/ulong position)
Method: void SetBit (uint/ulong position, bool value)
Method: void ComplementBit (uint/ulong position)

Allows access to individual bits of the number, using a "virtual" two’s complement representation.

Method: uint/ulong PopCount () // 32/64-bit builds

Gets the number of set bits in the number.

Method: uint/ulong HammingDistance (IntegerExpression target) // 32/64-bit builds

Gets the hamming distance between this number and target.

Method: uint/ulong FindBit (bool value, uint/ulong start) // 32/64-bit builds

Scans the number for next set or cleared bit (depending on value).

Method: IntegerExpression Abs ()

Returns an expression that computes the absolute value of the number.

Method: IntegerExpression DivideExactly (IntegerExpression divisor)
Method: IntegerExpression DivideExactly (uint/ulong divisor) // 32/64-bit builds

Returns an expression that performs a fast division where it is known that there is no remainder.

Method: IntegerExpression PowerMod (IntegerExpression power, IntegerExpression modulo)
Method: IntegerExpression PowerMod (uint/ulong power, IntegerExpression modulo) // 32/64-bit builds

Returns an expression that raises the source to the specified power modulo modulo.

Method: bool IsDivisibleBy (IntegerExpression a)
Method: bool IsDivisibleBy (uint/ulong a)
Method: bool IsDivisibleByPowerOf2 (uint/ulong power)
Method: bool IsCongruentTo (IntegerExpression a, IntegerExpression modulo)
Method: bool IsCongruentTo (uint/ulong a, uint/ulong modulo)
Method: bool IsCongruentToModPowerOf2 (IntegerExpression a, uint/ulong power)
Method: bool IsPerfectPower ()
Method: bool IsPerfectSquare ()

Performs various divisibility checks. These methods return a bool result, and therefore are executed immediately. If they are called on an expression, the expression is evaluated to a temporary which is discarded immediately afterwards. If you will need this result again, assign the expression to a HugeInt variable and call the method on it.

Method: long Write (Stream stream)
Method: long Read (Stream stream)

Writes and reads integers to/from streams using the raw binary format.

Method: long Write (TextWriter writer)
Method: long Write (TextWriter writer, int base)
Method: long Write (TextWriter writer, int base, bool lowercase)
Method: long Read (TextReader reader)
Method: long Read (TextReader reader, int base)

Writes and reads integers as text.

Method: void Import<T> (T[] data, long limbCount, int bytesPerLimb, LimbOrder limbOrder, Endianness endianness, int nails)
Method: long Export<T> (T[] data, int bytesPerLimb, LimbOrder limbOrder, Endianness endianness, int nails)
Method: T[] Export<T> (int bytesPerLimb, LimbOrder limbOrder, Endianness endianness, int nails)

Imports/exports the absolute value of the number to/from arbitrary words of data.

Method: bool IsProbablePrime (MpirRandom random, int probability, ulong/uint pretested)
Method: bool IsLikelyPrime (MpirRandom random, ulong/uint pretested)
Static Method: static int Jacobi (HugeInteger a, HugeInteger b)
Static Method: static int Legendre (HugeInteger a, HugeInteger b)
Static Method: static int Kronecker (HugeInteger a, HugeInteger b)
Static Method: static int Kronecker (HugeInteger a, int/long b)
Static Method: static int Kronecker (HugeInteger a, uint/ulong b)
Static Method: static int Kronecker (int/long a, HugeInteger b)
Static Method: static int Kronecker (uint/ulong a, HugeInteger b)
Static Method: static IntegerExpression Power (uint/ulong value, uint/ulong power)
Static Method: static IntegerExpression Factorial (uint/ulong value)
Static Method: static IntegerExpression Factorial (uint/ulong value, uint/ulong order)
Static Method: static IntegerExpression Primorial (uint/ulong value)
Static Method: static IntegerExpression Binomial (uint/ulong n, uint/ulong k)
Static Method: static IntegerExpression Binomial (IntegerExpression n, uint/ulong k)

Performs various number-theoretic computations.

Static Method: static IntegerSequenceExpression Fibonacci (int/long n)
Static Method: static IntegerSequenceExpression Lucas (int/long n)

These two methods return a specialized expression that provides an additional method to optionally save the previous number in the sequence, in addition to the number requested, for example:

var b = new HugeInt();
var c = new HugeInt(HugeInt.Fibonacci(300).SavingPreviousTo(b));
Method: IntegerSquareRootExpression SquareRoot ()

Returns an expression that evaluates to the square root of the number. The expression provides a method to optionally save the remainder to a second variable:

a.Value = b.SquareRoot().SavingRemainderTo(c);
Method: IntegerRootExpression Root (ulong/uint power)

Returns an expression that evaluates to the root of the specified power of the number. The expression provides two optional methods. One allows to save the remainder to a second variable, and the other allows to set a boolean flag indicating whether the root operation was exact. Note that computing the remainder is more costly than just getting an exact flag.

bool exact = false;
a.Value = b.Root(3).SavingRemainderTo(r);
c.Value = d.Root(4).SettingExactTo(x => exact = x);
e.Value = f.Root(5).SavingRemainderTo(r).SettingExactTo(x => exact = x);
Method: IntegerExpression NextPrimeCandidate (MpirRandom random)

Returns an expression that looks for the next possible prime greater than the source number.

Method: uint/ulong Gcd (uint/ulong a)

Computes the greatest common divisor with the specified single-limb number.

Method: IntegerGcdExpression Gcd (IntegerExpression a)

Returns an expression that computes the greatest common divisor of the source number and a. Provides a method to optionally calculate the related Diophantine equation multiplier(s):

c.Value = a.Gcd(b).SavingDiophantineMultipliersTo(s, t);

If either s or t is null, that coefficient is not computed.

Method: IntegerExpression Lcm (IntegerExpression a)
Method: IntegerExpression Lcm (uint/ulong a)

Computes the least common multiple with a.

Method: IntegerExpression Invert (IntegerExpression modulo)

Returns an expression to compute the inverse of the source number modulo modulo.

Method: IntegerRemoveFactorsExpression RemoveFactors (IntegerExpression factor)

Returns an expression that evaluates to the result of removing all occurrences of the specified factor from the source number. Provides a method to optionally save the number of factors that were removed:

ulong/uint numberRemoved; // 64/32-bit builds
a.Value = b.RemoveFactors(c);
d.Value = e.RemoveFactors(f).SavingCountRemovedTo(x => numberRemoved = x);

Next: , Previous: Building MPIR.Net, Up: .Net Interface   [Index]