/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";
j ^^= 11;
```
this(Range)(Range s)
pure this(Range)(Range s)

Constraints:
if (isBidirectionalRange!Range && isSomeChar!(ElementType!Range) && !isInfinite!Range && !isSomeString!Range)
if (isSomeString!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(data); // 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 == "<

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

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 == "<

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` `%` `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)
const pure nothrow BigInt opBinaryRight(string op, T)(T y)
const pure nothrow T opBinaryRight(string op, T)(T x)

Constraints:
if ((op == "+" || op == "*" || op == "|" || op == "&" || op == "^") && isIntegral!T)
if (op == "-" && isIntegral!T)
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)()
pure nothrow BigInt opUnary(string op)()

Constraints:
if (op == "+" || op == "-" || 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 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 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)
const pure nothrow @nogc int opCmp(T : BigInt)(const T y)

Constraints:
if (isIntegral!T)

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 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 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(scope void delegate(const(char)[]) sink, string formatString)
const void toString(scope void delegate(const(char)[]) sink, ref 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"
```
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
```

© 1999–2017 The D Language Foundation