Phobos

Github Page

The D Programming Language

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;

pure 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

pure this(T)(T x) if (isIntegral!T);



pure BigInt  opAssign(T)(T x) if (isIntegral!T);



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



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



const pure bool  opEquals(T)(T y) if (isIntegral!T);



pure T  opCast(T : bool)();



pure int  opCmp(T)(T y) if (isIntegral!T);



const pure int  opCmp(T : BigInt)(const 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")