Report a bug
Quickly fork, edit online, and submit a pull request for this page. Requires a signed-in GitHub account. This works well for small changes. If you'd like to make larger changes you may want to consider using a local clone.

# 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.
Authors:
Don Clugston
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`)
if (isBidirectionalRange!Range && isSomeChar!(ElementType!Range) && !isInfinite!Range && !isNarrowString!Range);

pure this(Range)(Range `s`)
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`)
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`)
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`)
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`)
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 scope @safe BigInt `opOpAssign`(string op, T)(T `y`) return
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 scope @safe BigInt `opOpAssign`(string op, T)(T `y`) return
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 scope @safe BigInt `opBinary`(string op, T)(T `y`) return
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 scope @safe BigInt `opBinary`(string op, T)(T `y`) return
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`)
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`)
if ((op == "+" || op == "*" || op == "|" || op == "&" || op == "^") && isIntegral!T);

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

const pure nothrow @safe T `opBinaryRight`(string op, T)(T `x`)
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)()
if (op == "+" || op == "-" || op == "~");

pure nothrow @safe BigInt `opUnary`(string op)()
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 const ref BigInt `y`);

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

const pure nothrow @nogc bool `opEquals`(T)(const T `y`)
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)()
if (isFloatingPoint!T);
Implements casting to floating point types.
Examples:
```assert(cast(float)  BigInt("35540592535949172786332045140593475584")
== 35540592535949172786332045140593475584.0f);
assert(cast(double) BigInt("35540601499647381470685035515422441472")
== 35540601499647381470685035515422441472.0);
assert(cast(real)   BigInt("35540601499647381470685035515422441472")
== 35540601499647381470685035515422441472.0L);

writeln(cast(float)BigInt("-0x1345_6780_0000_0000_0000_0000_0000")); // -0x1.3456_78p+108f
// -0x1.3456_78ab_cdefp+108
writeln(cast(double)BigInt("-0x1345_678a_bcde_f000_0000_0000_0000"));
// -0x1.3456_78ab_cdefp+108L
writeln(cast(real)BigInt("-0x1345_678a_bcde_f000_0000_0000_0000"));
```
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(cast(float)BigInt(0x1aaa_aae7)); // 0x1.aaa_aaep+28f
writeln(cast(float)BigInt(0x1aaa_aaff)); // 0x1.aaa_ab0p+28f
writeln(cast(float)BigInt(-0x1aaa_aae7)); // -0x1.aaaaaep+28f
writeln(cast(float)BigInt(-0x1aaa_aaff)); // -0x1.aaaab0p+28f

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

// 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(cast(float)BigInt(0x1aaa_aaf0)); // 0x1.aaa_ab0p+28f
writeln(cast(float)BigInt(-0x1aaa_aaf0)); // -0x1.aaaab0p+28f

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

// 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.
// float.infinity
writeln(cast(float)BigInt("999_999_999_999_999_999_999_999_999_999_999_999_999"));
// -float.infinity
writeln(cast(float)BigInt("-999_999_999_999_999_999_999_999_999_999_999_999_999"));

assert(cast(double) BigInt("999_999_999_999_999_999_999_999_999_999_999_999_999") < double.infinity);
assert(cast(real) BigInt("999_999_999_999_999_999_999_999_999_999_999_999_999") < real.infinity);
```
const pure nothrow @nogc T `opCast`(T)()
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`(const ref BigInt `y`);

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

const nothrow @nogc @safe int `opCmp`(T)(const T `y`)
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 < 232*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 < 264*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(scope const(char)[]) `sink`, string `formatString`);

const void `toString`(scope void delegate(scope 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.
 "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`)
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"
```
pure @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`)
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
```