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.
- A struct representing an arbitrary precision integer
All arithmetic operations are supported, except
unsigned shift right (>>>). Logical operations are not currently supported.
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).
Example:
BigInt a = "9588669891916142";
BigInt b = "7452469135154800";
auto c = a * b;
assert(c == "71459266416693160362545788781600");
auto d = b * a;
assert(d == "71459266416693160362545788781600");
assert(d == c);
d = c * "794628672112";
assert(d == "56783581982794522489042432639320434378739200");
auto e = c + d;
assert(e == "56783581982865981755459125799682980167520800");
auto f = d + c;
assert(f == e);
auto g = f - c;
assert(g == d);
g = f - d;
assert(g == c);
e = 12345678;
g = c + e;
auto h = g / b;
auto i = g % b;
assert(h == a);
assert(i == e);
BigInt j = "-0x9A56_57f4_7B83_AB78";
j ^^= 11;
this(T s);
- Construct a BigInt from a decimal or hexadecimal string.
The number must be in the form of a D decimal or hex literal:
It may have a leading + or - sign; followed by "0x" if hexadecimal.
Underscores are permitted.
BUG:
Should throw a IllegalArgumentException/ConvError if invalid character found
this(T x);
-
void
opAssign(T : long)(T
x);
-
void
opAssign(T : BigInt)(T
x);
-
bool
opEquals(Tdummy = void)(ref const BigInt
y);
-
bool
opEquals(T : int)(T
y);
-
int
opCmp(T : long)(T
y);
-
int
opCmp(T : BigInt)(T
y);
-
- Returns the value of this BigInt as a long,
or +- long.max if outside the representable range.
- Returns the value of this BigInt as an int,
or +- long.max if outside the representable range.
- Number of significant uints which are used in storing this number.
The absolute value of this BigInt is always < 2^(32*uintLength)
- 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(void delegate(const(char)[])
sink, string
formatString);
- Convert the BigInt to string, passing it to 'sink'.
The output format is controlled via formatString:
"d" | Decimal |
"x" | Hexadecimal, lower case |
"X" | Hexadecimal, upper case |
"s" | Default formatting (same as "d") |
null | Default formatting (same as "d") |