/D

# 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
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
pure nothrow this(T)(T x)
Constraints: if (isIntegral!T);

Construct a `BigInt` from a built-in integral type.

Examples:
```// @system due to failure in FreeBSD32
ulong data = 1_000_000_000_000;
auto bigData = BigInt(data);
writeln(bigData); // BigInt("1_000_000_000_000")
```
pure nothrow this(T)(T x)
Constraints: if (is(Unqual!T == 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 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 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 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:
```//@system because opOpAssign is @system
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 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:
```// @system because opOpAssign is @system
auto x = BigInt("123");
auto y = BigInt("321");
x += y;
writeln(x); // BigInt("444")
```
const pure nothrow BigInt opBinary(string op, T)(T y)
Constraints: if ((op == "+" || op == "*" || op == "-" || op == "|" || op == "&" || op == "^" || op == "/" || op == "%") && is(T : BigInt));

Implements binary operators between `BigInt`s.

Examples:
```auto x = BigInt("123");
auto y = BigInt("456");
BigInt z = x * y;
writeln(z); // BigInt("56088")
```
const pure nothrow 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 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 BigInt opBinaryRight(string op, T)(T y)
Constraints: if ((op == "+" || op == "*" || op == "|" || op == "&" || op == "^") && isIntegral!T);

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

const pure nothrow 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 BigInt opUnary(string op)()
Constraints: if (op == "+" || op == "-" || op == "~");

pure nothrow 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 bool opEquals()(auto ref const BigInt y);

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

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

Examples:
```auto x = BigInt("12345");
auto y = BigInt("12340");
int z = 12345;
int w = 54321;

writeln(x); // x
assert(x != y);
writeln(x); // y + 5
writeln(x); // z
assert(x != w);
```
const pure nothrow @nogc 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 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 pure nothrow @nogc T opCast(T)()
Constraints: if (is(Unqual!T == 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 int opCmp(ref const BigInt y);

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

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

Implements 3-way comparisons of `BigInt` with `BigInt` or `BigInt` with built-in integers.

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);
```
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 `uint`s 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 `ulong`s which are used in storing this number. The absolute value of this `BigInt` is always < 264*ulongLength

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:
void delegate(const(char)[]) `sink` A delegate 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 nothrow @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 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"
```
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 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 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
```

© 1999–2019 The D Language Foundation