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;

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

Examples:

BigInt a = "9588669891916142";
BigInt b = "7452469135154800";
auto c = a * b;
writeln(c); // BigInt("71459266416693160362545788781600")
auto d = b * a;
writeln(d); // BigInt("71459266416693160362545788781600")
writeln(d); // c
d = c * BigInt("794628672112");
writeln(d); // BigInt("56783581982794522489042432639320434378739200")
auto e = c + d;
writeln(e); // BigInt("56783581982865981755459125799682980167520800")
auto f = d + c;
writeln(f); // e
auto g = f - c;
writeln(g); // d
g = f - d;
writeln(g); // c
e = 12345678;
g = c + e;
auto h = g / b;
auto i = g % b;
writeln(h); // a
writeln(i); // e
BigInt j = "-0x9A56_57f4_7B83_AB78";
BigInt k = j;
j ^^= 11;
writeln(k^^11); // j

this(Range)(Range s) Constraints: if (isBidirectionalRange!Range && isSomeChar!(ElementType!Range) && !isInfinite!Range && !isNarrowString!Range); pure this(Range)(Range s) Constraints: if (isNarrowString!Range);

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. Underscores are permitted in any location after the 0x and/or the sign of the number.

Parameters:

Range s a finite bidirectional range of any character type

Throws:: std.conv.ConvException if the string doesn't represent a valid number

this(Range)(bool isNegative, Range magnitude) Constraints: if (isInputRange!Range && isUnsigned!(ElementType!Range) && (hasLength!Range || isForwardRange!Range) && !isInfinite!Range);

Construct a BigInt from a sign and a magnitude.

The magnitude is an input range of unsigned integers that satisfies either std.range.primitives.hasLength or std.range.primitives.isForwardRange. The first (leftmost) element of the magnitude is considered the most significant.

Parameters:

bool `isNegative`	true for negative, false for non-negative (ignored when magnitude is zero)
Range `magnitude`	a finite range of unsigned integers

Examples:

ubyte[] magnitude = [1, 2, 3, 4, 5, 6];
auto b1 = BigInt(false, magnitude);
writeln(cast(long)b1); // 0x01_02_03_04_05_06L
auto b2 = BigInt(true, magnitude);
writeln(cast(long)b2); // -0x01_02_03_04_05_06L

pure nothrow @safe this(T)(T x) Constraints: if (isIntegral!T);

Construct a BigInt from a built-in integral type.

Examples:

ulong data = 1_000_000_000_000;
auto bigData = BigInt(data);
writeln(bigData); // BigInt("1_000_000_000_000")

pure nothrow @safe this(T)(T x) Constraints: if (is(immutable(T) == immutable(BigInt)));

Construct a BigInt from another BigInt.

Examples:

const(BigInt) b1 = BigInt("1_234_567_890");
BigInt b2 = BigInt(b1);
writeln(b2); // BigInt("1_234_567_890")

pure nothrow @safe BigInt opAssign(T)(T x)
Constraints: if (isIntegral!T);

Assignment from built-in integer types.

Examples:

auto b = BigInt("123");
b = 456;
writeln(b); // BigInt("456")

pure @nogc @safe BigInt opAssign(T : BigInt)(T x);

Assignment from another BigInt.

Examples:

auto b1 = BigInt("123");
auto b2 = BigInt("456");
b2 = b1;
writeln(b2); // BigInt("123")

pure nothrow @safe BigInt opOpAssign(string op, T)(T y)
Constraints: if ((op == "+" || op == "-" || op == "*" || op == "/" || op == "%" || op == ">>" || op == "<<" || op == "^^" || op == "|" || op == "&" || op == "^") && isIntegral!T);

Implements assignment operators from built-in integers of the form BigInt op= integer.

Examples:

auto b = BigInt("1_000_000_000");

b += 12345;
writeln(b); // BigInt("1_000_012_345")

b /= 5;
writeln(b); // BigInt("200_002_469")

pure nothrow @safe BigInt opOpAssign(string op, T)(T y)
Constraints: if ((op == "+" || op == "-" || op == "*" || op == "|" || op == "&" || op == "^" || op == "/" || op == "%") && is(T : BigInt));

Implements assignment operators of the form BigInt op= BigInt.

Examples:

auto x = BigInt("123");
auto y = BigInt("321");
x += y;
writeln(x); // BigInt("444")

const pure nothrow @safe BigInt opBinary(string op, T)(T y)
Constraints: if ((op == "+" || op == "*" || op == "-" || op == "|" || op == "&" || op == "^" || op == "/" || op == "%") && is(T : BigInt));

Implements binary operators between BigInts.

Examples:

auto x = BigInt("123");
auto y = BigInt("456");
BigInt z = x * y;
writeln(z); // BigInt("56088")

const pure nothrow @safe BigInt opBinary(string op, T)(T y)
Constraints: if ((op == "+" || op == "*" || op == "-" || op == "/" || op == "|" || op == "&" || op == "^" || op == ">>" || op == "<<" || op == "^^") && isIntegral!T);

Implements binary operators between BigInt's and built-in integers.

Examples:

auto x = BigInt("123");
x *= 300;
writeln(x); // BigInt("36900")

const pure nothrow @safe auto opBinary(string op, T)(T y)
Constraints: if (op == "%" && isIntegral!T);

Implements a narrowing remainder operation with built-in integer types.

This binary operator returns a narrower, built-in integer type where applicable, according to the following table.

`BigInt`	`%`	`uint`	→	`long`
`BigInt`	`%`	`long`	→	`long`
`BigInt`	`%`	`ulong`	→	`BigInt`
`BigInt`	`%`	other type	→	`int`

Examples:

auto  x  = BigInt("1_000_000_500");
long  l  = 1_000_000L;
ulong ul = 2_000_000UL;
int   i  = 500_000;
short s  = 30_000;

assert(is(typeof(x % l)  == long)   && x % l  == 500L);
assert(is(typeof(x % ul) == BigInt) && x % ul == BigInt(500));
assert(is(typeof(x % i)  == int)    && x % i  == 500);
assert(is(typeof(x % s)  == int)    && x % s  == 10500);

const pure nothrow @safe BigInt opBinaryRight(string op, T)(T y)
Constraints: if ((op == "+" || op == "*" || op == "|" || op == "&" || op == "^") && isIntegral!T);

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

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

Implements operators with built-in integers on the left-hand side and BigInt on the right-hand side.

Examples:

auto x = BigInt("100");
BigInt y = 123 + x;
writeln(y); // BigInt("223")

BigInt z = 123 - x;
writeln(z); // BigInt("23")

// Dividing a built-in integer type by BigInt always results in
// something that fits in a built-in type, so the built-in type is
// returned, not BigInt.
assert(is(typeof(1000 / x) == int));
writeln(1000 / x); // 10

const pure nothrow @safe BigInt opUnary(string op)()
Constraints: if (op == "+" || op == "-" || op == "~");

pure nothrow @safe BigInt opUnary(string op)()
Constraints: if (op == "++" || op == "--");

Implements BigInt unary operators.

Examples:

auto x = BigInt("1234");
writeln(-x); // BigInt("-1234")

++x;
writeln(x); // BigInt("1235")

const pure @nogc @safe bool opEquals()(auto ref const BigInt y);

const pure nothrow @nogc @safe bool opEquals(T)(const T y)
Constraints: if (isIntegral!T);

const nothrow @nogc bool opEquals(T)(const T y)
Constraints: if (isFloatingPoint!T);

Implements BigInt equality test with other BigInt's and built-in numeric types.

Examples:

// Note that when comparing a BigInt to a float or double the
// full precision of the BigInt is always considered, unlike
// when comparing an int to a float or a long to a double.
assert(BigInt(123456789) != cast(float) 123456789);

const pure nothrow @nogc @safe T opCast(T : bool)();

Implements casting to bool.

Examples:

// Non-zero values are regarded as true
auto x = BigInt("1");
auto y = BigInt("10");
assert(x);
assert(y);

// Zero value is regarded as false
auto z = BigInt("0");
assert(!z);

const pure @safe T opCast(T : ulong)();

Implements casting to integer types.

Throws:: std.conv.ConvOverflowException if the number exceeds the target type's range.

Examples:

import std.conv : to, ConvOverflowException;
import std.exception : assertThrown;

writeln(BigInt("0").to!int); // 0

writeln(BigInt("0").to!ubyte); // 0
writeln(BigInt("255").to!ubyte); // 255
assertThrown!ConvOverflowException(BigInt("256").to!ubyte);
assertThrown!ConvOverflowException(BigInt("-1").to!ubyte);

const nothrow @nogc @safe T opCast(T)()
Constraints: if (isFloatingPoint!T);

Implements casting to floating point types.

Examples:

writeln(0x1.abcd_e8p+124f); // cast(float)BigInt("0x1abc_de80_0000_0000_0000_0000_0000_0000")
// cast(double)BigInt("0x1abc_def1_2345_6000_0000_0000_0000_0000")
writeln(0x1.abcd_ef12_3456p+124);
// cast(real)BigInt("0x1abc_def1_2345_6000_0000_0000_0000_0000")
writeln(0x1.abcd_ef12_3456p+124L);

writeln(-0x1.3456_78p+108f); // cast(float)BigInt("-0x1345_6780_0000_0000_0000_0000_0000")
// cast(double)BigInt("-0x1345_678a_bcde_f000_0000_0000_0000")
writeln(-0x1.3456_78ab_cdefp+108);
// cast(real)BigInt("-0x1345_678a_bcde_f000_0000_0000_0000")
writeln(-0x1.3456_78ab_cdefp+108L);

Examples:

Rounding when casting to floating point

// BigInts whose values cannot be exactly represented as float/double/real
// are rounded when cast to float/double/real. When cast to float or
// double or 64-bit real the rounding is strictly defined. When cast
// to extended-precision real the rounding rules vary by environment.

// BigInts that fall somewhere between two non-infinite floats/doubles
// are rounded to the closer value when cast to float/double.
writeln(0x1.aaa_aaep+28f); // cast(float)BigInt(0x1aaa_aae7)
writeln(0x1.aaa_ab0p+28f); // cast(float)BigInt(0x1aaa_aaff)
writeln(-0x1.aaaaaep+28f); // cast(float)BigInt(-0x1aaa_aae7)
writeln(-0x1.aaaab0p+28f); // cast(float)BigInt(-0x1aaa_aaff)

writeln(0x1.aaa_aaaa_aaaa_aa00p+60); // cast(double)BigInt(0x1aaa_aaaa_aaaa_aa77)
writeln(0x1.aaa_aaaa_aaaa_ab00p+60); // cast(double)BigInt(0x1aaa_aaaa_aaaa_aaff)
writeln(-0x1.aaa_aaaa_aaaa_aa00p+60); // cast(double)BigInt(-0x1aaa_aaaa_aaaa_aa77)
writeln(-0x1.aaa_aaaa_aaaa_ab00p+60); // cast(double)BigInt(-0x1aaa_aaaa_aaaa_aaff)

// BigInts that fall exactly between two non-infinite floats/doubles
// are rounded away from zero when cast to float/double. (Note that
// in most environments this is NOT the same rounding rule rule used
// when casting int/long to float/double.)
writeln(0x1.aaa_ab0p+28f); // cast(float)BigInt(0x1aaa_aaf0)
writeln(-0x1.aaaab0p+28f); // cast(float)BigInt(-0x1aaa_aaf0)

writeln(0x1.aaa_aaaa_aaaa_ab00p+60); // cast(double)BigInt(0x1aaa_aaaa_aaaa_aa80)
writeln(-0x1.aaa_aaaa_aaaa_ab00p+60); // cast(double)BigInt(-0x1aaa_aaaa_aaaa_aa80)

// BigInts that are bounded on one side by the largest positive or
// most negative finite float/double and on the other side by infinity
// or -infinity are rounded as if in place of infinity was the value
// `2^^(T.max_exp)` when cast to float/double.
// cast(float)BigInt("999_999_999_999_999_999_999_999_999_999_999_999_999")
writeln(float.infinity);
// cast(float)BigInt("-999_999_999_999_999_999_999_999_999_999_999_999_999")
writeln(-float.infinity);

assert(double.infinity > cast(double) BigInt("999_999_999_999_999_999_999_999_999_999_999_999_999"));
assert(real.infinity > cast(real) BigInt("999_999_999_999_999_999_999_999_999_999_999_999_999"));

const pure nothrow @nogc T opCast(T)()
Constraints: if (is(immutable(T) == immutable(BigInt)));

Implements casting to/from qualified BigInt's.

Warning: Casting to/from const or immutable may break type system guarantees. Use with care.

Examples:

const(BigInt) x = BigInt("123");
BigInt y = cast() x;    // cast away const
writeln(y); // x

const pure nothrow @nogc @safe int opCmp(ref const BigInt y);

const pure nothrow @nogc @safe int opCmp(T)(const T y)
Constraints: if (isIntegral!T);

const nothrow @nogc @safe int opCmp(T)(const T y)
Constraints: if (isFloatingPoint!T);

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

Implements 3-way comparisons of BigInt with BigInt or BigInt with built-in numeric types.

Examples:

auto x = BigInt("100");
auto y = BigInt("10");
int z = 50;
const int w = 200;

assert(y < x);
assert(x > z);
assert(z > y);
assert(x < w);

Examples:

auto x = BigInt("0x1abc_de80_0000_0000_0000_0000_0000_0000");
BigInt y = x - 1;
BigInt z = x + 1;

double d = 0x1.abcde8p124;
assert(y < d);
assert(z > d);
assert(x >= d && x <= d);

// Note that when comparing a BigInt to a float or double the
// full precision of the BigInt is always considered, unlike
// when comparing an int to a float or a long to a double.
assert(BigInt(123456789) < cast(float) 123456789);

const pure nothrow @nogc @safe long toLong();

Returns:: The value of this BigInt as a long, or long.max/long.min if outside the representable range.

Examples:

auto b = BigInt("12345");
long l = b.toLong();
writeln(l); // 12345

const pure nothrow @nogc @safe int toInt();

Returns:: The value of this BigInt as an int, or int.max/int.min if outside the representable range.

Examples:

auto big = BigInt("5_000_000");
auto i = big.toInt();
writeln(i); // 5_000_000

// Numbers that are too big to fit into an int will be clamped to int.max.
auto tooBig = BigInt("5_000_000_000");
i = tooBig.toInt();
writeln(i); // int.max

const pure nothrow @nogc @property @safe size_t uintLength();

Number of significant uints which are used in storing this number. The absolute value of this BigInt is always < 2^{32*uintLength}

const pure nothrow @nogc @property @safe size_t ulongLength();

Number of significant ulongs which are used in storing this number. The absolute value of this BigInt is always < 2^{64*ulongLength}

const void toString(Writer)(ref scope Writer sink, string formatString);

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

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

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

Convert the BigInt to string, passing it to the given sink.

Parameters:

Writer sink An OutputRange for accepting possibly piecewise segments of the formatted string.

string formatString

A format string specifying the output format.

Available output formats:
"d"	Decimal
"o"	Octal
"x"	Hexadecimal, lower case
"X"	Hexadecimal, upper case
"s"	Default formatting (same as "d")
null	Default formatting (same as "d")

Examples:

toString is rarely directly invoked; the usual way of using it is via std.format.format:

import std.format : format;

auto x = BigInt("1_000_000");
x *= 12345;

writeln(format("%d", x)); // "12345000000"
writeln(format("%x", x)); // "2_dfd1c040"
writeln(format("%X", x)); // "2_DFD1C040"
writeln(format("%o", x)); // "133764340100"

const pure nothrow @nogc @safe size_t toHash();

Returns:: A unique hash of the BigInt's value suitable for use in a hash table.

Examples:

toHash is rarely directly invoked; it is implicitly used when BigInt is used as the key of an associative array.

string[BigInt] aa;
aa[BigInt(123)] = "abc";
aa[BigInt(456)] = "def";

writeln(aa[BigInt(123)]); // "abc"
writeln(aa[BigInt(456)]); // "def"

const T getDigit(T = ulong)(size_t n)
Constraints: if (is(T == ulong) || is(T == uint));

Gets the nth number in the underlying representation that makes up the whole BigInt.

Parameters:

T	the type to view the underlying representation as
size_t `n`	The nth number to retrieve. Must be less than `ulongLength` or `uintLength` with respect to `T`.

Returns:: The nth ulong in the representation of this BigInt.

Examples:

auto a = BigInt("1000");
writeln(a.ulongLength()); // 1
writeln(a.getDigit(0)); // 1000

writeln(a.uintLength()); // 1
writeln(a.getDigit!uint(0)); // 1000

auto b = BigInt("2_000_000_000_000_000_000_000_000_000");
writeln(b.ulongLength()); // 2
writeln(b.getDigit(0)); // 4584946418820579328
writeln(b.getDigit(1)); // 108420217

writeln(b.uintLength()); // 3
writeln(b.getDigit!uint(0)); // 3489660928
writeln(b.getDigit!uint(1)); // 1067516025
writeln(b.getDigit!uint(2)); // 108420217

pure nothrow @safe string toDecimalString(const(BigInt) x);

Parameters:

const(BigInt) x The BigInt to convert to a decimal string.

Returns:: A string that represents the BigInt as a decimal number.

Examples:

auto x = BigInt("123");
x *= 1000;
x += 456;

auto xstr = x.toDecimalString();
writeln(xstr); // "123456"

@safe string toHex(const(BigInt) x);

Parameters:

const(BigInt) x The BigInt to convert to a hexadecimal string.

Returns:: A string that represents the BigInt as a hexadecimal (base 16) number in upper case.

Examples:

auto x = BigInt("123");
x *= 1000;
x += 456;

auto xstr = x.toHex();
writeln(xstr); // "1E240"

Unsigned!T absUnsign(T)(T x)
Constraints: if (isIntegral!T);

Returns the absolute value of x converted to the corresponding unsigned type.

Parameters:

T x The integral value to return the absolute value of.

Returns:: The absolute value of x.

Examples:

writeln((-1).absUnsign); // 1
writeln(1.absUnsign); // 1

pure nothrow @safe void divMod(const BigInt dividend, const BigInt divisor, out BigInt quotient, out BigInt remainder);

Finds the quotient and remainder for the given dividend and divisor in one operation.

Parameters:

BigInt `dividend`	the `BigInt` to divide
BigInt `divisor`	the `BigInt` to divide the dividend by
BigInt `quotient`	is set to the result of the division
BigInt `remainder`	is set to the remainder of the division

Examples:

auto a = BigInt(123);
auto b = BigInt(25);
BigInt q, r;

divMod(a, b, q, r);

writeln(q); // 4
writeln(r); // 23
writeln(q * b + r); // a

pure nothrow @safe BigInt powmod(BigInt base, BigInt exponent, BigInt modulus);

Fast power modulus calculation for BigInt operands.

Parameters:

BigInt `base`	the `BigInt` is basic operands.
BigInt `exponent`	the `BigInt` is power exponent of base.
BigInt `modulus`	the `BigInt` is modules to be modular of base ^ exponent.

Returns:: The power modulus value of (base ^ exponent) % modulus.

Examples:

for powmod

BigInt base = BigInt("123456789012345678901234567890");
BigInt exponent = BigInt("1234567890123456789012345678901234567");
BigInt modulus = BigInt("1234567");

BigInt result = powmod(base, exponent, modulus);
writeln(result); // 359079