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:
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.)
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
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.
Range s
| a finite bidirectional range of any character type |
std.conv.ConvException if the string doesn't represent a valid numberConstruct a BigInt from a built-in integral type.
// @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")
Construct a BigInt from another BigInt.
const(BigInt) b1 = BigInt("1_234_567_890");
BigInt b2 = BigInt(b1);
writeln(b2); // BigInt("1_234_567_890")
Assignment from built-in integer types.
auto b = BigInt("123");
b = 456;
writeln(b); // BigInt("456")
Assignment from another BigInt.
auto b1 = BigInt("123");
auto b2 = BigInt("456");
b2 = b1;
writeln(b2); // BigInt("123")
Implements assignment operators from built-in integers of the form BigInt op= integer.
//@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")
Implements assignment operators of the form BigInt op= BigInt.
// @system because opOpAssign is @system
auto x = BigInt("123");
auto y = BigInt("321");
x += y;
writeln(x); // BigInt("444")
Implements binary operators between BigInts.
auto x = BigInt("123");
auto y = BigInt("456");
BigInt z = x * y;
writeln(z); // BigInt("56088")
Implements binary operators between BigInt's and built-in integers.
auto x = BigInt("123");
x *= 300;
writeln(x); // BigInt("36900")
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 |
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);
Implements operators with built-in integers on the left-hand side and BigInt on the right-hand side.
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
Implements BigInt unary operators.
auto x = BigInt("1234");
writeln(-x); // BigInt("-1234")
++x;
writeln(x); // BigInt("1235")
Implements BigInt equality test with other BigInt's and built-in integer types.
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);
Implements casting to bool.
// 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);
Implements casting to integer types.
std.conv.ConvOverflowException if the number exceeds the target type's range.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);
Implements casting to/from qualified BigInt's.
const or immutable may break type system guarantees. Use with care.const(BigInt) x = BigInt("123");
BigInt y = cast() x; // cast away const
writeln(y); // x
Implements 3-way comparisons of BigInt with BigInt or BigInt with built-in integers.
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);
BigInt as a long, or long.max/long.min if outside the representable range.auto b = BigInt("12345");
long l = b.toLong();
writeln(l); // 12345
BigInt as an int, or int.max/int.min if outside the representable range.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
Number of significant uints which are used in storing this number. The absolute value of this BigInt is always < 232*uintLength
Number of significant ulongs which are used in storing this number. The absolute value of this BigInt is always < 264*ulongLength
Convert the BigInt to string, passing it to the given sink.
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.
|
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"
BigInt's value suitable for use in a hash table.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"
Gets the nth number in the underlying representation that makes up the whole BigInt.
| 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. |
ulong in the representation of this BigInt.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
const(BigInt) x
| The BigInt to convert to a decimal string. |
string that represents the BigInt as a decimal number.auto x = BigInt("123");
x *= 1000;
x += 456;
auto xstr = x.toDecimalString();
writeln(xstr); // "123456"
const(BigInt) x
| The BigInt to convert to a hexadecimal string. |
string that represents the BigInt as a hexadecimal (base 16) number in upper case.auto x = BigInt("123");
x *= 1000;
x += 456;
auto xstr = x.toHex();
writeln(xstr); // "1E240"
Returns the absolute value of x converted to the corresponding unsigned type.
T x
| The integral value to return the absolute value of. |
writeln((-1).absUnsign); // 1 writeln(1.absUnsign); // 1
Finds the quotient and remainder for the given dividend and divisor in one operation.
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 |
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
Fast power modulus calculation for BigInt operands.
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. |
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
Licensed under the Boost License 1.0.
https://dlang.org/phobos/std_bigint.html