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.

License:
Boost License 1.0.

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 (>>>). 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 == BigInt("71459266416693160362545788781600"));
        auto d = b * a;
        assert(d == BigInt("71459266416693160362545788781600"));
        assert(d == c);
        d = c * BigInt("794628672112");
        assert(d == BigInt("56783581982794522489042432639320434378739200"));
        auto e = c + d;
        assert(e == BigInt("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 : const(char)[])(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 : long)(T x);

BigInt opAssign(T : long)(T x);

BigInt opAssign(T : BigInt)(T x);

const bool opEquals()(auto ref const BigInt y);

const bool opEquals(T : long)(T y);

int opCmp(T : long)(T y);

int opCmp(T : BigInt)(T y);

const pure long toLong();

Returns the value of this BigInt as a long, or +- long.max if outside the representable range.

const pure int toInt();

Returns the value of this BigInt as an int, or +- int.max if outside the representable range.

const pure @property size_t uintLength();

Number of significant uints which are used in storing this number. The absolute value of this BigInt is always < 2^^(32*uintLength)

const pure @property size_t ulongLength();

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

Convert the BigInt to string, passing it to 'sink'.

The output format is controlled via formatString:

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")
"d"	Decimal
"x"	Hexadecimal, lower case
"X"	Hexadecimal, upper case
"s"	Default formatting (same as "d")
null	Default formatting (same as "d")

std

etc

core

std.bigint