D Programming Language
Report a bug If you spot a problem with this page, click here to create a Bugzilla issue. Improve this page Quickly fork, edit online, and submit a pull request for this page. Requires a signed-in GitHub account. This works well for small changes. If you'd like to make larger changes you may want to consider using local clone.

# 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 (>>>). 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;
      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 nothrow this(T)(T x) if (isIntegral!T);
    Construct a BigInt from a built-in integral type.
    Examples:

        ulong data = 1_000_000_000_000;
        auto bigData = BigInt(data);
        assert(data == BigInt("1_000_000_000_000"));

  pure nothrow this(T)(T x) if (is(Unqual!T == BigInt));
    Construct a BigInt from another BigInt.
    Examples:

        const(BigInt) b1 = BigInt("1_234_567_890");
        BigInt b2 = BigInt(b1);
        assert(b2 == BigInt("1_234_567_890"));

  pure nothrow BigInt opAssign(T)(T x) if (isIntegral!T);
    Assignment from built-in integer types.
    Examples:

        auto b = BigInt("123");
        b = 456;
        assert(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;
        assert(b2 == BigInt("123"));

  pure nothrow BigInt opOpAssign(string op, T)(T y) if ((op == "+" || op == "-" || op == "*" || op == "/" || op == "%" || op == ">>" || op == "<<" || op == "^^" || op == "|" || op == "&" || op == "^") && isIntegral!T);
    Implements assignment operators from built-in integers of the form BigInt op= integer.
    Examples:

        auto b = BigInt("1_000_000_000");

        b += 12345;
        assert(b == BigInt("1_000_012_345"));

        b /= 5;
        assert(b == BigInt("200_002_469"));

  pure nothrow BigInt opOpAssign(string op, T)(T y) if ((op == "+" || op == "-" || op == "*" || op == "|" || op == "&" || op == "^" || op == "/" || op == "%") && is(T : BigInt));
    Implements assignment operators of the form BigInt op= BigInt.
    Examples:

        auto x = BigInt("123");
        auto y = BigInt("321");
        x += y;
        assert(x == BigInt("444"));

  const pure nothrow BigInt opBinary(string op, T)(T y) 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;
        assert(z == BigInt("56088"));

  const pure nothrow BigInt opBinary(string op, T)(T y) if ((op == "+" || op == "*" || op == "-" || op == "/" || op == "|" || op == "&" || op == "^" || op == ">>" || op == "<<" || op == "^^") && isIntegral!T);
    Implements binary operators between BigInt's and built-in integers.
    Examples:

        auto x = BigInt("123");
        x *= 300;
        assert(x == BigInt("36900"));

  const pure nothrow auto opBinary(string op, T)(T y) 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) if ((op == "+" || op == "*" || op == "|" || op == "&" || op == "^") && isIntegral!T);
  const pure nothrow BigInt opBinaryRight(string op, T)(T y) if (op == "-" && isIntegral!T);
  const pure nothrow T opBinaryRight(string op, T)(T x) 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;
        assert(y == BigInt("223"));

        BigInt z = 123 - x;
        assert(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));
        assert(1000 / x == 10);

  const pure nothrow BigInt opUnary(string op)() if (op == "+" || op == "-" || op == "~");
  pure nothrow BigInt opUnary(string op)() if (op == "++" || op == "--");
    Implements BigInt unary operators.
    Examples:

        auto x = BigInt("1234");
        assert(-x == BigInt("-1234"));

        ++x;
        assert(x == BigInt("1235"));

  const pure @nogc bool opEquals()(auto ref const BigInt y);
  const pure nothrow @nogc bool opEquals(T)(T y) 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;

        assert(x == x);
        assert(x != y);
        assert(x == y + 5);
        assert(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 pure nothrow @nogc T opCast(T)() 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
        assert(y == x);

  const pure nothrow @nogc int opCmp(ref const BigInt y);
  const pure nothrow @nogc int opCmp(T)(T y) if (isIntegral!T);
  const pure nothrow @nogc int opCmp(T : BigInt)(const T y);
    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();
        assert(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();
        assert(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();
        assert(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.
    Available output formats:
    "d" | Decimal
    "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;

        assert(format("%d", x) == "12345000000");
        assert(format("%x", x) == "2_dfd1c040");
        assert(format("%X", x) == "2_DFD1C040");

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

        assert(aa[BigInt(123)] == "abc");
        assert(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();
      assert(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();
      assert(xstr == "1E240");

Unsigned!T absUnsign(T)(T x) 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.

Copyright © 1999-2015 by Digital Mars ®, All Rights Reserved | Page generated by Ddoc on Tue Nov 3 22:00:38 2015