std.bigint

Arbitrary-precision ('bignum') arithmetic.

Performance is optimized for numbers below ~1000 decimal digits. For X86 machines, highly optimised assembly routines are used.

The following algorithms are currently implemented:

Karatsuba multiplication
Squaring is optimized independently of multiplication
Divide-and-conquer division
Binary exponentiation

For very large numbers, consider using the GMP library instead.

License

Boost License 1.0.

Authors

Don Clugston

Source: std/bigint.d

struct BigInt

fn absUnsign divMod powmod toDecimalString toHex

Types 1

structBigInt

A struct representing an arbitrary precision integer.

All arithmetic operations are supported, except unsigned shift right (`>>>`). Bitwise operations (`|`, `&`, `^`, `~`) are supported, and behave as if BigInt was an infinite length 2's complement number.

BigInt implements value semantics using copy-on-write. This means that assignment is cheap, but operations such as x++ will cause heap allocation. (But note that for most bigint operations, heap allocation is inevitable anyway.)

Fields

private BigUint data

private bool sign

Methods

BigInt opAssign(T)(T x) if (isIntegral!T) pure nothrow @safeAssignment from built-in integer types.

BigInt opAssign(T: BigInt)(T x) pure @nogc @safeAssignment from another BigInt.

BigInt opOpAssign(string op,  T)(T y) if ((op == "+" ||  op == "-" ||  op == "*" ||  op == "/" ||  op == "%"
        ||  op == ">>" ||  op == "<<" ||  op == "^^" ||  op == "|" ||  op == "&" ||  op == "^")  &&  isIntegral!T)

pure nothrow @safe return scopeImplements assignment operators from built-in integers of the form `BigInt op= integer`.

BigInt opOpAssign(string op,  T)(T y) if ((op == "+" ||  op ==  "-" ||  op == "*" ||  op == "|" ||  op == "&" ||  op == "^" ||  op == "/" ||  op == "%")  &&  is (T:  BigInt))

pure nothrow @safe return scopeImplements assignment operators of the form `BigInt op= BigInt`.

BigInt opBinary(string op,  T)(T y) if ((op == "+" ||  op ==  "*" ||  op == "-" ||  op == "|" ||  op == "&" ||  op == "^" ||
         op == "/" ||  op == "%")  &&  is (T:  BigInt))

pure nothrow @safe const return scopeImplements binary operators between `BigInt`s.

BigInt opBinary(string op,  T)(T y) if ((op == "+" ||  op ==  "*" ||  op == "-" ||  op == "/" ||  op == "|" ||  op == "&" ||
         op == "^" ||  op == ">>" ||  op == "<<" ||  op == "^^")
         &&  isIntegral!T)

pure nothrow @safe const return scopeImplements binary operators between `BigInt`'s and built-in integers.

auto opBinary(string op, T)(T y) if (op == "%" && isIntegral!T) pure nothrow @safe constImplements a narrowing remainder operation with built-in integer types.

BigInt opBinaryRight(string op,  T)(T y) if ((op == "+" ||  op == "*" ||  op == "|" ||  op == "&" ||  op == "^")  &&  isIntegral!T)

pure nothrow @safe constImplements operators with built-in integers on the left-hand side and `BigInt` on the right-hand side.

BigInt opBinaryRight(string op, T)(T y) if (op == "-" && isIntegral!T) pure nothrow @safe constditto

T opBinaryRight(string op, T)(T x) if ((op == "%" || op == "/") && isIntegral!T) pure nothrow @safe constditto

BigInt opUnary(string op)() if (op == "+" || op == "-" || op == "~") pure nothrow @safe constImplements `BigInt` unary operators.

BigInt opUnary(string op)() if (op == "++" || op == "--") pure nothrow @safeditto

bool opEquals()(auto ref const BigInt y) const pure @nogc @safeImplements `BigInt` equality test with other `BigInt`'s and built-in numeric types.

bool opEquals(T)(const T y) if (isIntegral!T) const pure nothrow @nogc @safeditto

bool opEquals(T)(const T y) if (isFloatingPoint!T) const pure nothrow @nogcditto

T opCast(T: bool)() pure nothrow @nogc @safe constImplements casting to `bool`.

T opCast(T: ulong)() pure @safe constImplements casting to integer types.

T opCast(T)() if (isFloatingPoint!T) @safe nothrow @nogc constImplements casting to floating point types.

private

T toFloat(T,  string roundingMode)() if (__traits(isFloating,  T)  && (roundingMode ==  "nearest" ||  roundingMode ==  "truncate"))

@safe nothrow @nogc const

T opCast(T)() if (is(immutable T == immutable BigInt)) pure nothrow @nogc constImplements casting to/from qualified `BigInt`'s.

int opCmp(ref const BigInt y) pure nothrow @nogc @safe constImplements 3-way comparisons of `BigInt` with `BigInt` or `BigInt` with built-in numeric types.

int opCmp(T)(const T y) if (isIntegral!T) pure nothrow @nogc @safe constditto

int opCmp(T)(const T y) if (isFloatingPoint!T) nothrow @nogc @safe constditto

int opCmp(T: BigInt)(const T y) pure nothrow @nogc @safe constditto

long toLong() @safe pure nothrow const @nogcReturns: The value of this `BigInt` as a `long`, or `long.max`/`long.min` if outside the representable range.

int toInt() @safe pure nothrow @nogc constReturns: The value of this `BigInt` as an `int`, or `int.max`/`int.min` if outside the representable range.

size_t uintLength() @property @safe pure nothrow @nogc constNumber of significant `uint`s which are used in storing this number. The absolute value of this `BigInt` is always < 232*uintLength

size_t ulongLength() @property @safe pure nothrow @nogc constNumber of significant `ulong`s which are used in storing this number. The absolute value of this `BigInt` is always < 264*ulongLength

void toString(Writer)(scope ref Writer sink, string formatString) constConvert the `BigInt` to `string`, passing it to the given sink.

void toString(Writer)(scope ref Writer sink, scope const ref FormatSpec!char f) constditto

void toString(scope void delegate(scope const(char)[]) sink, string formatString) constditto

void toString(scope void delegate(scope const(char)[]) sink, scope const ref FormatSpec!char f) constditto

size_t toHash() const @safe pure nothrow @nogcReturns: A unique hash of the `BigInt`'s value suitable for use in a hash table.

T getDigit(T = ulong)(size_t n) if (is(T == ulong) || is(T == uint)) constGets the nth number in the underlying representation that makes up the whole `BigInt`.

private void negate() @safe pure nothrow @nogc scope

private bool isZero() pure const nothrow @nogc @safe scope

private void checkDivByZero() pure const nothrow @safe scope

Constructors

this(Range s)Construct a `BigInt` from a decimal or hexadecimal string. The number must be in the form of a decimal or hex literal. It may have a leading `+` or `-` sign, followed by `0x` or `0X` if hexadecimal...

this(Range s)ditto

this(bool isNegative, Range magnitude)Construct a `BigInt` from a sign and a magnitude.

this(T x)Construct a `BigInt` from a built-in integral type.

this(T x)Construct a `BigInt` from another `BigInt`.

Functions 5

fnstring toDecimalString(const(BigInt) x) pure nothrow @safeParams: x = The `BigInt` to convert to a decimal `string`.

fnstring toHex(const(BigInt) x) pure @safeParams: x = The `BigInt` to convert to a hexadecimal `string`.

fnUnsigned!T absUnsign(T)(T x) if (isIntegral!T)Returns the absolute value of x converted to the corresponding unsigned type.

fnvoid divMod(const BigInt dividend, const BigInt divisor, out BigInt quotient, out BigInt remainder) pure nothrow @safeFinds the quotient and remainder for the given dividend and divisor in one operation.

fnBigInt powmod(BigInt base, BigInt exponent, BigInt modulus) pure nothrow @safeFast power modulus calculation for BigInt operands. Params: base = the BigInt is basic operands. exponent = the BigInt is power exponent of base. modulus = the BigInt is modules to be modular of ba...