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

BigUint data

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`.

void negate() @safe pure nothrow @nogc scope

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

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...