path: root/libphobos/src/std/bigint.d

/** 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:
 * $(UL
 * $(LI Karatsuba multiplication)
 * $(LI Squaring is optimized independently of multiplication)
 * $(LI Divide-and-conquer division)
 * $(LI Binary exponentiation)
 * )
 *
 * For very large numbers, consider using the $(HTTP gmplib.org, GMP library) instead.
 *
 * License:   $(HTTP www.boost.org/LICENSE_1_0.txt, Boost License 1.0).
 * Authors:   Don Clugston
 * Source: $(PHOBOSSRC std/bigint.d)
 */
/*          Copyright Don Clugston 2008 - 2010.
 * Distributed under the Boost Software License, Version 1.0.
 *    (See accompanying file LICENSE_1_0.txt or copy at
 *          http://www.boost.org/LICENSE_1_0.txt)
 */

module std.bigint;

import std.conv : ConvException;

import std.format.spec : FormatSpec;
import std.format : FormatException;
import std.internal.math.biguintcore;
import std.internal.math.biguintnoasm : BigDigit;
import std.range.primitives;
import std.traits;

/** 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.)
 */
struct BigInt
{
private:
    BigUint data;     // BigInt adds signed arithmetic to BigUint.
    bool sign = false;
public:
    /**
     * 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.
     *
     * Params:
     *     s = a finite bidirectional range of any character type
     *
     * Throws:
     *     $(REF ConvException, std,conv) if the string doesn't represent a valid number
     */
    this(Range)(Range s) if (
        isBidirectionalRange!Range &&
        isSomeChar!(ElementType!Range) &&
        !isInfinite!Range &&
        !isNarrowString!Range)
    {
        import std.algorithm.iteration : filterBidirectional;
        import std.algorithm.searching : startsWith;
        import std.conv : ConvException;
        import std.exception : enforce;
        import std.utf : byChar;

        enforce!ConvException(!s.empty, "Can't initialize BigInt with an empty range");

        bool neg = false;
        bool ok;

        data = 0UL;

        // check for signs and if the string is a hex value
        if (s.front == '+')
        {
            s.popFront(); // skip '+'
        }
        else if (s.front == '-')
        {
            neg = true;
            s.popFront();
        }

        if (s.save.startsWith("0x".byChar) ||
            s.save.startsWith("0X".byChar))
        {
            s.popFront;
            s.popFront;

            if (!s.empty)
                ok = data.fromHexString(s.filterBidirectional!(a => a != '_'));
            else
                ok = false;
        }
        else
        {
            ok = data.fromDecimalString(s.filterBidirectional!(a => a != '_'));
        }

        enforce!ConvException(ok, "Not a valid numerical string");

        if (isZero())
            neg = false;

        sign = neg;
    }

    /// ditto
    this(Range)(Range s) pure
    if (isNarrowString!Range)
    {
        import std.utf : byCodeUnit;
        this(s.byCodeUnit);
    }

    @safe unittest
    {
        // system because of the dummy ranges eventually call std.array!string
        import std.exception : assertThrown;
        import std.internal.test.dummyrange;

        auto r1 = new ReferenceBidirectionalRange!dchar("101");
        auto big1 = BigInt(r1);
        assert(big1 == BigInt(101));

        auto r2 = new ReferenceBidirectionalRange!dchar("1_000");
        auto big2 = BigInt(r2);
        assert(big2 == BigInt(1000));

        auto r3 = new ReferenceBidirectionalRange!dchar("0x0");
        auto big3 = BigInt(r3);
        assert(big3 == BigInt(0));

        auto r4 = new ReferenceBidirectionalRange!dchar("0x");
        assertThrown!ConvException(BigInt(r4));
    }

    /**
     * Construct a `BigInt` from a sign and a magnitude.
     *
     * The magnitude is an $(REF_ALTTEXT input range, isInputRange, std,range,primitives)
     * of unsigned integers that satisfies either $(REF hasLength, std,range,primitives)
     * or $(REF isForwardRange, std,range,primitives). The first (leftmost)
     * element of the magnitude is considered the most significant.
     *
     * Params:
     *     isNegative = true for negative, false for non-negative
     *          (ignored when magnitude is zero)
     *     magnitude = a finite range of unsigned integers
     */
    this(Range)(bool isNegative, Range magnitude) if (
        isInputRange!Range &&
        isUnsigned!(ElementType!Range) &&
        (hasLength!Range || isForwardRange!Range) &&
        !isInfinite!Range)
    {
        data.fromMagnitude(magnitude);
        sign = isNegative && !data.isZero;
    }

    ///
    pure @safe unittest
    {
        ubyte[] magnitude = [1, 2, 3, 4, 5, 6];
        auto b1 = BigInt(false, magnitude);
        assert(cast(long) b1 == 0x01_02_03_04_05_06L);
        auto b2 = BigInt(true, magnitude);
        assert(cast(long) b2 == -0x01_02_03_04_05_06L);
    }

    /// Construct a `BigInt` from a built-in integral type.
    this(T)(T x) pure nothrow @safe if (isIntegral!T)
    {
        data = data.init; // @@@: Workaround for compiler bug
        opAssign(x);
    }

    ///
    @safe unittest
    {
        ulong data = 1_000_000_000_000;
        auto bigData = BigInt(data);
        assert(bigData == BigInt("1_000_000_000_000"));
    }

    /// Construct a `BigInt` from another `BigInt`.
    this(T)(T x) pure nothrow @safe if (is(immutable T == immutable BigInt))
    {
        opAssign(x);
    }

    ///
    @safe unittest
    {
        const(BigInt) b1 = BigInt("1_234_567_890");
        BigInt b2 = BigInt(b1);
        assert(b2 == BigInt("1_234_567_890"));
    }

    /// Assignment from built-in integer types.
    BigInt opAssign(T)(T x) pure nothrow @safe if (isIntegral!T)
    {
        data = cast(ulong) absUnsign(x);
        sign = (x < 0);
        return this;
    }

    ///
    @safe unittest
    {
        auto b = BigInt("123");
        b = 456;
        assert(b == BigInt("456"));
    }

    /// Assignment from another BigInt.
    BigInt opAssign(T:BigInt)(T x) pure @nogc @safe
    {
        data = x.data;
        sign = x.sign;
        return this;
    }

    ///
    @safe unittest
    {
        auto b1 = BigInt("123");
        auto b2 = BigInt("456");
        b2 = b1;
        assert(b2 == BigInt("123"));
    }

    /**
     * Implements assignment operators from built-in integers of the form
     * `BigInt op= integer`.
     */
    BigInt opOpAssign(string op, T)(T y) pure nothrow @safe return scope
        if ((op=="+" || op=="-" || op=="*" || op=="/" || op=="%"
          || op==">>" || op=="<<" || op=="^^" || op=="|" || op=="&" || op=="^") && isIntegral!T)
    {
        ulong u = absUnsign(y);

        static if (op=="+")
        {
            data = BigUint.addOrSubInt(data, u, sign != (y<0), sign);
        }
        else static if (op=="-")
        {
            data = BigUint.addOrSubInt(data, u, sign == (y<0), sign);
        }
        else static if (op=="*")
        {
            if (y == 0)
            {
                sign = false;
                data = 0UL;
            }
            else
            {
                sign = ( sign != (y<0) );
                data = BigUint.mulInt(data, u);
            }
        }
        else static if (op=="/")
        {
            assert(y != 0, "Division by zero");
            static if (T.sizeof <= uint.sizeof)
            {
                data = BigUint.divInt(data, cast(uint) u);
            }
            else
            {
                data = BigUint.divInt(data, u);
            }
            sign = data.isZero() ? false : sign ^ (y < 0);
        }
        else static if (op=="%")
        {
            assert(y != 0, "Division by zero");
            static if (is(immutable(T) == immutable(long)) || is( immutable(T) == immutable(ulong) ))
            {
                this %= BigInt(y);
            }
            else
            {
                data = cast(ulong) BigUint.modInt(data, cast(uint) u);
                if (data.isZero())
                    sign = false;
            }
            // x%y always has the same sign as x.
            // This is not the same as mathematical mod.
        }
        else static if (op==">>" || op=="<<")
        {
            // Do a left shift if y>0 and <<, or
            // if y<0 and >>; else do a right shift.
            if (y == 0)
                return this;
            else if ((y > 0) == (op=="<<"))
            {
                // Sign never changes during left shift
                data = data.opBinary!(op)(u);
            }
            else
            {
                data = data.opBinary!(op)(u);
                if (data.isZero())
                    sign = false;
            }
        }
        else static if (op=="^^")
        {
            sign = (y & 1) ? sign : false;
            data = BigUint.pow(data, u);
        }
        else static if (op=="&")
        {
            if (y >= 0 && (y <= 1 || !sign)) // In these cases we can avoid some allocation.
            {
                static if (T.sizeof <= uint.sizeof && BigDigit.sizeof <= uint.sizeof)
                    data = cast(ulong) data.peekUint(0) & y;
                else
                    data = data.peekUlong(0) & y;
                sign = false;
            }
            else
            {
                BigInt b = y;
                opOpAssign!op(b);
            }
        }
        else static if (op=="|" || op=="^")
        {
            BigInt b = y;
            opOpAssign!op(b);
        }
        else static assert(0, "BigInt " ~ op[0..$-1] ~ "= " ~ T.stringof ~ " is not supported");
        return this;
    }

    ///
    @safe unittest
    {
        auto b = BigInt("1_000_000_000");

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

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

    // https://issues.dlang.org/show_bug.cgi?id=16264
    @safe unittest
    {
        auto a = BigInt(
    `335690982744637013564796917901053301979460129353374296317539383938630086938` ~
    `465898213033510992292836631752875403891802201862860531801760096359705447768` ~
    `957432600293361240407059207520920532482429912948952142341440301429494694368` ~
    `264560802292927144211230021750155988283029753927847924288850436812178022006` ~
    `408597793414273953252832688620479083497367463977081627995406363446761896298` ~
    `967177607401918269561385622811274398143647535024987050366350585544531063531` ~
    `7118554808325723941557169427279911052268935775`);

        auto b = BigInt(
    `207672245542926038535480439528441949928508406405023044025560363701392340829` ~
    `852529131306106648201340460604257466180580583656068555417076345439694125326` ~
    `843947164365500055567495554645796102453565953360564114634705366335703491527` ~
    `429426780005741168078089657359833601261803592920462081364401456331489106355` ~
    `199133982282631108670436696758342051198891939367812305559960349479160308314` ~
    `068518200681530999860641597181672463704794566473241690395901768680673716414` ~
    `243691584391572899147223065906633310537507956952626106509069491302359792769` ~
    `378934570685117202046921464019396759638376362935855896435623442486036961070` ~
    `534574698959398017332214518246531363445309522357827985468581166065335726996` ~
    `711467464306784543112544076165391268106101754253962102479935962248302404638` ~
    `21737237102628470475027851189594709504`);

        BigInt c = a * b;  // Crashes

        assert(c == BigInt(
    `697137001950904057507249234183127244116872349433141878383548259425589716813` ~
    `135440660252012378417669596912108637127036044977634382385990472429604619344` ~
    `738746224291111527200379708978133071390303850450970292020176369525401803474` ~
    `998613408923490273129022167907826017408385746675184651576154302536663744109` ~
    `111018961065316024005076097634601030334948684412785487182572502394847587887` ~
    `507385831062796361152176364659197432600147716058873232435238712648552844428` ~
    `058885217631715287816333209463171932255049134340904981280717725999710525214` ~
    `161541960645335744430049558161514565159449390036287489478108344584188898872` ~
    `434914159748515512161981956372737022393466624249130107254611846175580584736` ~
    `276213025837422102290580044755202968610542057651282410252208599309841499843` ~
    `672251048622223867183370008181364966502137725166782667358559333222947265344` ~
    `524195551978394625568228658697170315141077913403482061673401937141405425042` ~
    `283546509102861986303306729882186190883772633960389974665467972016939172303` ~
    `653623175801495207204880400522581834672918935651426160175413277309985678579` ~
    `830872397214091472424064274864210953551447463312267310436493480881235642109` ~
    `668498742629676513172286703948381906930297135997498416573231570483993847269` ~
    `479552708416124555462530834668011570929850407031109157206202741051573633443` ~
    `58105600`
        ));
    }

    /**
     * Implements assignment operators of the form `BigInt op= BigInt`.
     */
    BigInt opOpAssign(string op, T)(T y) pure nothrow @safe scope return
        if ((op=="+" || op== "-" || op=="*" || op=="|" || op=="&" || op=="^" || op=="/" || op=="%")
            && is (T: BigInt))
    {
        static if (op == "+")
        {
            data = BigUint.addOrSub(data, y.data, sign != y.sign, &sign);
        }
        else static if (op == "-")
        {
            data = BigUint.addOrSub(data, y.data, sign == y.sign, &sign);
        }
        else static if (op == "*")
        {
            data = BigUint.mul(data, y.data);
            sign = isZero() ? false : sign ^ y.sign;
        }
        else static if (op == "/")
        {
            y.checkDivByZero();
            if (!isZero())
            {
                data = BigUint.div(data, y.data);
                sign = isZero() ? false : sign ^ y.sign;
            }
        }
        else static if (op == "%")
        {
            y.checkDivByZero();
            if (!isZero())
            {
                data = BigUint.mod(data, y.data);
                // x%y always has the same sign as x.
                if (isZero())
                    sign = false;
            }
        }
        else static if (op == "|" || op == "&" || op == "^")
        {
            data = BigUint.bitwiseOp!op(data, y.data, sign, y.sign, sign);
        }
        else static assert(0, "BigInt " ~ op[0..$-1] ~ "= " ~
            T.stringof ~ " is not supported");
        return this;
    }

    ///
    @safe unittest
    {
        auto x = BigInt("123");
        auto y = BigInt("321");
        x += y;
        assert(x == BigInt("444"));
    }

    /**
     * Implements binary operators between `BigInt`s.
     */
    BigInt opBinary(string op, T)(T y) pure nothrow @safe const return scope
        if ((op=="+" || op == "*" || op=="-" || op=="|" || op=="&" || op=="^" ||
            op=="/" || op=="%")
            && is (T: BigInt))
    {
        BigInt r = this;
        return r.opOpAssign!(op)(y);
    }

    ///
    @safe unittest
    {
        auto x = BigInt("123");
        auto y = BigInt("456");
        BigInt z = x * y;
        assert(z == BigInt("56088"));
    }

    /**
     * Implements binary operators between `BigInt`'s and built-in integers.
     */
    BigInt opBinary(string op, T)(T y) pure nothrow @safe const return scope
        if ((op=="+" || op == "*" || op=="-" || op=="/" || op=="|" || op=="&" ||
            op=="^"|| op==">>" || op=="<<" || op=="^^")
            && isIntegral!T)
    {
        BigInt r = this;
        r.opOpAssign!(op)(y);
        return r;
    }

    ///
    @safe unittest
    {
        auto x = BigInt("123");
        x *= 300;
        assert(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.

        $(TABLE ,
        $(TR $(TD `BigInt`) $(TD $(CODE_PERCENT)) $(TD `uint`) $(TD $(RARR)) $(TD `long`))
        $(TR $(TD `BigInt`) $(TD $(CODE_PERCENT)) $(TD `long`) $(TD $(RARR)) $(TD `long`))
        $(TR $(TD `BigInt`) $(TD $(CODE_PERCENT)) $(TD `ulong`) $(TD $(RARR)) $(TD `BigInt`))
        $(TR $(TD `BigInt`) $(TD $(CODE_PERCENT)) $(TD other type) $(TD $(RARR)) $(TD `int`))
        )
     */
    auto opBinary(string op, T)(T y) pure nothrow @safe const
        if (op == "%" && isIntegral!T)
    {
        assert(y != 0, "% 0 not allowed");

        // BigInt % uint => long
        // BigInt % long => long
        // BigInt % ulong => BigInt
        // BigInt % other_type => int
        static if (is(immutable T == immutable long) || is(immutable T == immutable ulong))
        {
            auto r = this % BigInt(y);

            static if (is(immutable T == immutable long))
            {
                return r.toLong();
            }
            else
            {
                // return as-is to avoid overflow
                return r;
            }
        }
        else
        {
            immutable uint u = absUnsign(y);
            static if (is(immutable T == immutable uint))
               alias R = long;
            else
               alias R = int;
            R rem = BigUint.modInt(data, u);
            // x%y always has the same sign as x.
            // This is not the same as mathematical mod.
            return sign ? -rem : rem;
        }
    }

    ///
    @safe unittest
    {
        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.
     */
    BigInt opBinaryRight(string op, T)(T y) pure nothrow @safe const
        if ((op=="+" || op=="*" || op=="|" || op=="&" || op=="^") && isIntegral!T)
    {
        return opBinary!(op)(y);
    }

    ///
    @safe unittest
    {
        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);
    }

    //  BigInt = integer op BigInt
    /// ditto
    BigInt opBinaryRight(string op, T)(T y) pure nothrow @safe const
        if (op == "-" && isIntegral!T)
    {
        ulong u = absUnsign(y);
        BigInt r;
        static if (op == "-")
        {
            r.sign = sign;
            r.data = BigUint.addOrSubInt(data, u, sign == (y<0), r.sign);
            r.negate();
        }
        return r;
    }

    //  integer = integer op BigInt
    /// ditto
    T opBinaryRight(string op, T)(T x) pure nothrow @safe const
        if ((op=="%" || op=="/") && isIntegral!T)
    {
        checkDivByZero();

        static if (op == "%")
        {
            // x%y always has the same sign as x.
            if (data.ulongLength > 1)
                return x;
            immutable u = absUnsign(x);
            immutable rem = u % data.peekUlong(0);
            // x%y always has the same sign as x.
            return cast(T)((x<0) ? -rem : rem);
        }
        else static if (op == "/")
        {
            if (data.ulongLength > 1)
                return 0;
            return cast(T)(x / data.peekUlong(0));
        }
    }

    // const unary operations
    /**
        Implements `BigInt` unary operators.
     */
    BigInt opUnary(string op)() pure nothrow @safe const if (op=="+" || op=="-" || op=="~")
    {
       static if (op=="-")
       {
            BigInt r = this;
            r.negate();
            return r;
        }
        else static if (op=="~")
        {
            return -(this+1);
        }
        else static if (op=="+")
           return this;
    }

    // non-const unary operations
    /// ditto
    BigInt opUnary(string op)() pure nothrow @safe if (op=="++" || op=="--")
    {
        static if (op=="++")
        {
            data = BigUint.addOrSubInt(data, 1UL, sign, sign);
            return this;
        }
        else static if (op=="--")
        {
            data = BigUint.addOrSubInt(data, 1UL, !sign, sign);
            return this;
        }
    }

    ///
    @safe unittest
    {
        auto x = BigInt("1234");
        assert(-x == BigInt("-1234"));

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

    /**
        Implements `BigInt` equality test with other `BigInt`'s and built-in
        numeric types.
     */
    bool opEquals()(auto ref const BigInt y) const pure @nogc @safe
    {
       return sign == y.sign && y.data == data;
    }

    /// ditto
    bool opEquals(T)(const T y) const pure nothrow @nogc @safe if (isIntegral!T)
    {
        if (sign != (y<0))
            return 0;
        return data.opEquals(cast(ulong) absUnsign(y));
    }

    /// ditto
    bool opEquals(T)(const T y) const pure nothrow @nogc if (isFloatingPoint!T)
    {
        return 0 == opCmp(y);
    }

    ///
    @safe unittest
    {
        // Note that when comparing a BigInt to a float or double the
        // full precision of the BigInt is always considered, unlike
        // when comparing an int to a float or a long to a double.
        assert(BigInt(123456789) != cast(float) 123456789);
    }

    @safe unittest
    {
        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);
    }

    @safe unittest
    {
        import std.math.operations : nextDown, nextUp;

        const x = BigInt("0x1abc_de80_0000_0000_0000_0000_0000_0000");
        BigInt x1 = x + 1;
        BigInt x2 = x - 1;

        const d = 0x1.abcde8p124;
        assert(x == d);
        assert(x1 != d);
        assert(x2 != d);
        assert(x != nextUp(d));
        assert(x != nextDown(d));
        assert(x != double.nan);

        const dL = 0x1.abcde8p124L;
        assert(x == dL);
        assert(x1 != dL);
        assert(x2 != dL);
        assert(x != nextUp(dL));
        assert(x != nextDown(dL));
        assert(x != real.nan);

        assert(BigInt(0) == 0.0f);
        assert(BigInt(0) == 0.0);
        assert(BigInt(0) == 0.0L);
        assert(BigInt(0) == -0.0f);
        assert(BigInt(0) == -0.0);
        assert(BigInt(0) == -0.0L);
        assert(BigInt("999_999_999_999_999_999_999_999_999_999_999_999_999") != float.infinity);
    }

    /**
        Implements casting to `bool`.
     */
    T opCast(T:bool)() pure nothrow @nogc @safe const
    {
        return !isZero();
    }

    ///
    @safe unittest
    {
        // 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.

        Throws: $(REF ConvOverflowException, std,conv) if the number exceeds
        the target type's range.
     */
    T opCast(T:ulong)() pure @safe const
    {
        if (isUnsigned!T && sign)
            { /* throw */ }
        else
        if (data.ulongLength == 1)
        {
            ulong l = data.peekUlong(0);
            if (isUnsigned!T || !sign)
            {
                if (l <= T.max)
                    return cast(T) l;
            }
            else
            {
                if (l <= ulong(T.max)+1)
                    return cast(T)-long(l); // -long.min == long.min
            }
        }

        import std.conv : ConvOverflowException;
        import std.string : format;
        throw new ConvOverflowException(
            "BigInt(%s) cannot be represented as a %s"
            .format(this.toDecimalString, T.stringof));
    }

    ///
    @safe unittest
    {
        import std.conv : to, ConvOverflowException;
        import std.exception : assertThrown;

        assert(BigInt("0").to!int == 0);

        assert(BigInt("0").to!ubyte == 0);
        assert(BigInt("255").to!ubyte == 255);
        assertThrown!ConvOverflowException(BigInt("256").to!ubyte);
        assertThrown!ConvOverflowException(BigInt("-1").to!ubyte);
    }

    @safe unittest
    {
        import std.conv : to, ConvOverflowException;
        import std.exception : assertThrown;

        assert(BigInt("-1").to!byte == -1);
        assert(BigInt("-128").to!byte == -128);
        assert(BigInt("127").to!byte == 127);
        assertThrown!ConvOverflowException(BigInt("-129").to!byte);
        assertThrown!ConvOverflowException(BigInt("128").to!byte);

        assert(BigInt("0").to!uint == 0);
        assert(BigInt("4294967295").to!uint == uint.max);
        assertThrown!ConvOverflowException(BigInt("4294967296").to!uint);
        assertThrown!ConvOverflowException(BigInt("-1").to!uint);

        assert(BigInt("-1").to!int == -1);
        assert(BigInt("-2147483648").to!int == int.min);
        assert(BigInt("2147483647").to!int == int.max);
        assertThrown!ConvOverflowException(BigInt("-2147483649").to!int);
        assertThrown!ConvOverflowException(BigInt("2147483648").to!int);

        assert(BigInt("0").to!ulong == 0);
        assert(BigInt("18446744073709551615").to!ulong == ulong.max);
        assertThrown!ConvOverflowException(BigInt("18446744073709551616").to!ulong);
        assertThrown!ConvOverflowException(BigInt("-1").to!ulong);

        assert(BigInt("-1").to!long == -1);
        assert(BigInt("-9223372036854775808").to!long == long.min);
        assert(BigInt("9223372036854775807").to!long == long.max);
        assertThrown!ConvOverflowException(BigInt("-9223372036854775809").to!long);
        assertThrown!ConvOverflowException(BigInt("9223372036854775808").to!long);
    }

    /**
        Implements casting to floating point types.
     */
    T opCast(T)() @safe nothrow @nogc const if (isFloatingPoint!T)
    {
        return toFloat!(T, "nearest");
    }

    ///
    @system unittest
    {
        assert(cast(float)  BigInt("35540592535949172786332045140593475584")
                == 35540592535949172786332045140593475584.0f);
        assert(cast(double) BigInt("35540601499647381470685035515422441472")
                == 35540601499647381470685035515422441472.0);
        assert(cast(real)   BigInt("35540601499647381470685035515422441472")
                == 35540601499647381470685035515422441472.0L);

        assert(cast(float)  BigInt("-0x1345_6780_0000_0000_0000_0000_0000") == -0x1.3456_78p+108f       );
        assert(cast(double) BigInt("-0x1345_678a_bcde_f000_0000_0000_0000") == -0x1.3456_78ab_cdefp+108 );
        assert(cast(real)   BigInt("-0x1345_678a_bcde_f000_0000_0000_0000") == -0x1.3456_78ab_cdefp+108L);
    }

    /// Rounding when casting to floating point
    @system unittest
    {
        // BigInts whose values cannot be exactly represented as float/double/real
        // are rounded when cast to float/double/real. When cast to float or
        // double or 64-bit real the rounding is strictly defined. When cast
        // to extended-precision real the rounding rules vary by environment.

        // BigInts that fall somewhere between two non-infinite floats/doubles
        // are rounded to the closer value when cast to float/double.
        assert(cast(float) BigInt(0x1aaa_aae7) == 0x1.aaa_aaep+28f);
        assert(cast(float) BigInt(0x1aaa_aaff) == 0x1.aaa_ab0p+28f);
        assert(cast(float) BigInt(-0x1aaa_aae7) == -0x1.aaaaaep+28f);
        assert(cast(float) BigInt(-0x1aaa_aaff) == -0x1.aaaab0p+28f);

        assert(cast(double) BigInt(0x1aaa_aaaa_aaaa_aa77) == 0x1.aaa_aaaa_aaaa_aa00p+60);
        assert(cast(double) BigInt(0x1aaa_aaaa_aaaa_aaff) == 0x1.aaa_aaaa_aaaa_ab00p+60);
        assert(cast(double) BigInt(-0x1aaa_aaaa_aaaa_aa77) == -0x1.aaa_aaaa_aaaa_aa00p+60);
        assert(cast(double) BigInt(-0x1aaa_aaaa_aaaa_aaff) == -0x1.aaa_aaaa_aaaa_ab00p+60);

        // BigInts that fall exactly between two non-infinite floats/doubles
        // are rounded away from zero when cast to float/double. (Note that
        // in most environments this is NOT the same rounding rule rule used
        // when casting int/long to float/double.)
        assert(cast(float) BigInt(0x1aaa_aaf0) == 0x1.aaa_ab0p+28f);
        assert(cast(float) BigInt(-0x1aaa_aaf0) == -0x1.aaaab0p+28f);

        assert(cast(double) BigInt(0x1aaa_aaaa_aaaa_aa80) == 0x1.aaa_aaaa_aaaa_ab00p+60);
        assert(cast(double) BigInt(-0x1aaa_aaaa_aaaa_aa80) == -0x1.aaa_aaaa_aaaa_ab00p+60);

        // BigInts that are bounded on one side by the largest positive or
        // most negative finite float/double and on the other side by infinity
        // or -infinity are rounded as if in place of infinity was the value
        // `2^^(T.max_exp)` when cast to float/double.
        assert(cast(float) BigInt("999_999_999_999_999_999_999_999_999_999_999_999_999") == float.infinity);
        assert(cast(float) BigInt("-999_999_999_999_999_999_999_999_999_999_999_999_999") == -float.infinity);

        assert(cast(double) BigInt("999_999_999_999_999_999_999_999_999_999_999_999_999") < double.infinity);
        assert(cast(real) BigInt("999_999_999_999_999_999_999_999_999_999_999_999_999") < real.infinity);
    }

    @safe unittest
    {
        // Test exponent overflow is correct.
        assert(cast(float) BigInt(0x1fffffff) == 0x1.000000p+29f);
        assert(cast(double) BigInt(0x1fff_ffff_ffff_fff0) == 0x1.000000p+61);
    }

    private T toFloat(T, string roundingMode)() @safe nothrow @nogc const
    if (__traits(isFloating, T) && (roundingMode == "nearest" || roundingMode == "truncate"))
    {
        import core.bitop : bsr;
        enum performRounding = (roundingMode == "nearest");
        enum performTruncation = (roundingMode == "truncate");
        static assert(performRounding || performTruncation, "unrecognized rounding mode");
        enum int totalNeededBits = T.mant_dig + int(performRounding);
        static if (totalNeededBits <= 64)
        {
            // We need to examine the top two 64-bit words, not just the top one,
            // since the top word could have just a single significant bit.
            const ulongLength = data.ulongLength;
            const ulong w1 = data.peekUlong(ulongLength - 1);
            if (w1 == 0)
                return T(0); // Special: exponent should be all zero bits, plus bsr(w1) is undefined.
            const ulong w2 = ulongLength < 2 ? 0 : data.peekUlong(ulongLength - 2);
            const uint w1BitCount = bsr(w1) + 1;
            ulong sansExponent = (w1 << (64 - w1BitCount)) | (w2 >>> (w1BitCount));
            size_t exponent = (ulongLength - 1) * 64 + w1BitCount + 1;
            static if (performRounding)
            {
                sansExponent += 1UL << (64 - totalNeededBits);
                if (0 <= cast(long) sansExponent) // Use high bit to detect overflow.
                {
                    // Do not bother filling in the high bit of sansExponent
                    // with 1. It will be discarded by float and double and 80
                    // bit real cannot be on this path with rounding enabled.
                    exponent += 1;
                }
            }
            static if (T.mant_dig == float.mant_dig)
            {
                if (exponent >= T.max_exp)
                    return isNegative ? -T.infinity : T.infinity;
                uint resultBits = (uint(isNegative) << 31) | // sign bit
                    ((0xFF & (exponent - float.min_exp)) << 23) | // exponent
                    cast(uint) ((sansExponent << 1) >>> (64 - 23)); // mantissa.
                // TODO: remove @trusted lambda after DIP 1000 is enabled by default.
                return (() @trusted => *cast(float*) &resultBits)();
            }
            else static if (T.mant_dig == double.mant_dig)
            {
                if (exponent >= T.max_exp)
                    return isNegative ? -T.infinity : T.infinity;
                ulong resultBits = (ulong(isNegative) << 63) | // sign bit
                    ((0x7FFUL & (exponent - double.min_exp)) << 52) | // exponent
                    ((sansExponent << 1) >>> (64 - 52)); // mantissa.
                // TODO: remove @trusted lambda after DIP 1000 is enabled by default.
                return (() @trusted => *cast(double*) &resultBits)();
            }
            else
            {
                import core.math : ldexp;
                return ldexp(isNegative ? -cast(real) sansExponent : cast(real) sansExponent,
                    cast(int) exponent - 65);
            }
        }
        else
        {
            import core.math : ldexp;
            const ulongLength = data.ulongLength;
            if ((ulongLength - 1) * 64L > int.max)
                return isNegative ? -T.infinity : T.infinity;
            int scale = cast(int) ((ulongLength - 1) * 64);
            const ulong w1 = data.peekUlong(ulongLength - 1);
            if (w1 == 0)
                return T(0); // Special: bsr(w1) is undefined.
            int bitsStillNeeded = totalNeededBits - bsr(w1) - 1;
            T acc = ldexp(cast(T) w1, scale);
            for (ptrdiff_t i = ulongLength - 2; i >= 0 && bitsStillNeeded > 0; i--)
            {
                ulong w = data.peekUlong(i);
                // To round towards zero we must make sure not to use too many bits.
                if (bitsStillNeeded >= 64)
                {
                    acc += ldexp(cast(T) w, scale -= 64);
                    bitsStillNeeded -= 64;
                }
                else
                {
                    w = (w >>> (64 - bitsStillNeeded)) << (64 - bitsStillNeeded);
                    acc += ldexp(cast(T) w, scale -= 64);
                    break;
                }
            }
            if (isNegative)
                acc = -acc;
            return cast(T) acc;
        }
    }

    /**
        Implements casting to/from qualified `BigInt`'s.

        Warning: Casting to/from `const` or `immutable` may break type
        system guarantees. Use with care.
     */
    T opCast(T)() pure nothrow @nogc const
    if (is(immutable T == immutable BigInt))
    {
        return this;
    }

    ///
    @safe unittest
    {
        const(BigInt) x = BigInt("123");
        BigInt y = cast() x;    // cast away const
        assert(y == x);
    }

    // Hack to make BigInt's typeinfo.compare work properly.
    // Note that this must appear before the other opCmp overloads, otherwise
    // DMD won't find it.
    /**
        Implements 3-way comparisons of `BigInt` with `BigInt` or `BigInt` with
        built-in numeric types.
     */
    int opCmp(ref const BigInt y) pure nothrow @nogc @safe const
    {
        // Simply redirect to the "real" opCmp implementation.
        return this.opCmp!BigInt(y);
    }

    /// ditto
    int opCmp(T)(const T y) pure nothrow @nogc @safe const if (isIntegral!T)
    {
        if (sign != (y<0) )
            return sign ? -1 : 1;
        int cmp = data.opCmp(cast(ulong) absUnsign(y));
        return sign? -cmp: cmp;
    }
    /// ditto
    int opCmp(T)(const T y) nothrow @nogc @safe const if (isFloatingPoint!T)
    {
        import core.bitop : bsr;
        import std.math.operations : cmp;
        import std.math.traits : isFinite;

        const asFloat = toFloat!(T, "truncate");
        if (asFloat != y)
            return cmp(asFloat, y); // handles +/- NaN.
        if (!isFinite(y))
            return isNegative ? 1 : -1;
        const ulongLength = data.ulongLength;
        const w1 = data.peekUlong(ulongLength - 1);
        if (w1 == 0)
            return 0; // Special: bsr(w1) is undefined.
        const numSignificantBits = (ulongLength - 1) * 64 + bsr(w1) + 1;
        for (ptrdiff_t bitsRemainingToCheck = numSignificantBits - T.mant_dig, i = 0;
            bitsRemainingToCheck > 0; i++, bitsRemainingToCheck -= 64)
        {
            auto word = data.peekUlong(i);
            if (word == 0)
                continue;
            // Make sure we're only checking digits that are beyond
            // the precision of `y`.
            if (bitsRemainingToCheck < 64 && (word << (64 - bitsRemainingToCheck)) == 0)
                break; // This can only happen on the last loop iteration.
            return isNegative ? -1 : 1;
        }
        return 0;
    }
    /// ditto
    int opCmp(T:BigInt)(const T y) pure nothrow @nogc @safe const
    {
        if (sign != y.sign)
            return sign ? -1 : 1;
        immutable cmp = data.opCmp(y.data);
        return sign? -cmp: cmp;
    }

    ///
    @safe unittest
    {
        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);
    }

    ///
    @safe unittest
    {
        auto x = BigInt("0x1abc_de80_0000_0000_0000_0000_0000_0000");
        BigInt y = x - 1;
        BigInt z = x + 1;

        double d = 0x1.abcde8p124;
        assert(y < d);
        assert(z > d);
        assert(x >= d && x <= d);

        // Note that when comparing a BigInt to a float or double the
        // full precision of the BigInt is always considered, unlike
        // when comparing an int to a float or a long to a double.
        assert(BigInt(123456789) < cast(float) 123456789);
    }

    @safe unittest
    {
        assert(BigInt("999_999_999_999_999_999_999_999_999_999_999_999_999") < float.infinity);

        // Test `real` works.
        auto x = BigInt("0x1abc_de80_0000_0000_0000_0000_0000_0000");
        BigInt y = x - 1;
        BigInt z = x + 1;

        real d = 0x1.abcde8p124;
        assert(y < d);
        assert(z > d);
        assert(x >= d && x <= d);

        // Test comparison for numbers of 64 bits or fewer.
        auto w1 = BigInt(0x1abc_de80_0000_0000);
        auto w2 = w1 - 1;
        auto w3 = w1 + 1;
        assert(w1.ulongLength == 1);
        assert(w2.ulongLength == 1);
        assert(w3.ulongLength == 1);

        double e = 0x1.abcde8p+60;
        assert(w1 >= e && w1 <= e);
        assert(w2 < e);
        assert(w3 > e);

        real eL = 0x1.abcde8p+60;
        assert(w1 >= eL && w1 <= eL);
        assert(w2 < eL);
        assert(w3 > eL);
    }

    /**
        Returns: The value of this `BigInt` as a `long`, or `long.max`/`long.min`
        if outside the representable range.
     */
    long toLong() @safe pure nothrow const @nogc
    {
        return (sign ? -1 : 1) *
          (data.ulongLength == 1  && (data.peekUlong(0) <= sign+cast(ulong)(long.max)) // 1+long.max = |long.min|
          ? cast(long)(data.peekUlong(0))
          : long.max);
    }

    ///
    @safe unittest
    {
        auto b = BigInt("12345");
        long l = b.toLong();
        assert(l == 12345);
    }

    /**
        Returns: The value of this `BigInt` as an `int`, or `int.max`/`int.min` if outside
        the representable range.
     */
    int toInt() @safe pure nothrow @nogc const
    {
        return (sign ? -1 : 1) *
          (data.uintLength == 1  && (data.peekUint(0) <= sign+cast(uint)(int.max)) // 1+int.max = |int.min|
          ? cast(int)(data.peekUint(0))
          : int.max);
    }

    ///
    @safe unittest
    {
        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);
    }

    /// Number of significant `uint`s which are used in storing this number.
    /// The absolute value of this `BigInt` is always &lt; 2$(SUPERSCRIPT 32*uintLength)
    @property size_t uintLength() @safe pure nothrow @nogc const
    {
        return data.uintLength;
    }

    /// Number of significant `ulong`s which are used in storing this number.
    /// The absolute value of this `BigInt` is always &lt; 2$(SUPERSCRIPT 64*ulongLength)
    @property size_t ulongLength() @safe pure nothrow @nogc const
    {
        return data.ulongLength;
    }

    /** Convert the `BigInt` to `string`, passing it to the given sink.
     *
     * Params:
     *  sink = An OutputRange for accepting possibly piecewise segments of the
     *      formatted string.
     *  formatString = A format string specifying the output format.
     *
     * $(TABLE  Available output formats:,
     * $(TR $(TD "d") $(TD  Decimal))
     * $(TR $(TD "o") $(TD  Octal))
     * $(TR $(TD "x") $(TD  Hexadecimal, lower case))
     * $(TR $(TD "X") $(TD  Hexadecimal, upper case))
     * $(TR $(TD "s") $(TD  Default formatting (same as "d") ))
     * $(TR $(TD null) $(TD Default formatting (same as "d") ))
     * )
     */
    void toString(Writer)(scope ref Writer sink, string formatString) const
    {
        auto f = FormatSpec!char(formatString);
        f.writeUpToNextSpec(sink);
        toString!Writer(sink, f);
    }

    /// ditto
    void toString(Writer)(scope ref Writer sink, scope const ref FormatSpec!char f) const
    {
        import std.range.primitives : put;
        const spec = f.spec;
        immutable hex = (spec == 'x' || spec == 'X');
        if (!(spec == 's' || spec == 'd' || spec =='o' || hex))
            throw new FormatException("Format specifier not understood: %" ~ spec);

        char[] buff;
        if (spec == 'X')
        {
            buff = data.toHexString(0, '_', 0, f.flZero ? '0' : ' ', LetterCase.upper);
        }
        else if (spec == 'x')
        {
            buff = data.toHexString(0, '_', 0, f.flZero ? '0' : ' ', LetterCase.lower);
        }
        else if (spec == 'o')
        {
            buff = data.toOctalString();
        }
        else
        {
            buff = data.toDecimalString(0);
        }
        assert(buff.length > 0, "Invalid buffer length");

        char signChar = isNegative ? '-' : 0;
        auto minw = buff.length + (signChar ? 1 : 0);

        if (!hex && !signChar && (f.width == 0 || minw < f.width))
        {
            if (f.flPlus)
            {
                signChar = '+';
                ++minw;
            }
            else if (f.flSpace)
            {
                signChar = ' ';
                ++minw;
            }
        }

        immutable maxw = minw < f.width ? f.width : minw;
        immutable difw = maxw - minw;

        if (!f.flDash && !f.flZero)
            foreach (i; 0 .. difw)
                put(sink, " ");

        if (signChar)
        {
            scope char[1] buf = signChar;
            put(sink, buf[]);
        }

        if (!f.flDash && f.flZero)
            foreach (i; 0 .. difw)
                put(sink, "0");

        put(sink, buff);

        if (f.flDash)
            foreach (i; 0 .. difw)
                put(sink, " ");
    }

    /**
        `toString` is rarely directly invoked; the usual way of using it is via
        $(REF format, std, format):
     */
    @safe unittest
    {
        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");
        assert(format("%o", x) == "133764340100");
    }

    // for backwards compatibility, see unittest below
    /// ditto
    void toString(scope void delegate(scope const(char)[]) sink, string formatString) const
    {
        toString!(void delegate(scope const(char)[]))(sink, formatString);
    }

    // for backwards compatibility, see unittest below
    /// ditto
    void toString(scope void delegate(scope const(char)[]) sink, scope const ref FormatSpec!char f) const
    {
        toString!(void delegate(scope const(char)[]))(sink, f);
    }

    // Backwards compatibility test
    // BigInt.toString used to only accept a delegate sink function, but this does not work
    // well with attributes such as @safe. A template function toString was added that
    // works on OutputRanges, but when a delegate was passed in the form of an untyped
    // lambda such as `str => dst.put(str)` the parameter type was inferred as `void` and
    // the function failed to instantiate.
    @system unittest
    {
        import std.format.spec : FormatSpec;
        import std.array : appender;
        BigInt num = 503;
        auto dst = appender!string();
        num.toString(str => dst.put(str), null);
        assert(dst[] == "503");
        num = 504;
        auto f = FormatSpec!char("");
        num.toString(str => dst.put(str), f);
        assert(dst[] == "503504");
    }

    // Implement toHash so that BigInt works properly as an AA key.
    /**
        Returns: A unique hash of the `BigInt`'s value suitable for use in a hash
        table.
     */
    size_t toHash() const @safe pure nothrow @nogc
    {
        return data.toHash() + sign;
    }

    /**
        `toHash` is rarely directly invoked; it is implicitly used when
        BigInt is used as the key of an associative array.
     */
    @safe pure unittest
    {
        string[BigInt] aa;
        aa[BigInt(123)] = "abc";
        aa[BigInt(456)] = "def";

        assert(aa[BigInt(123)] == "abc");
        assert(aa[BigInt(456)] == "def");
    }

    /**
     * Gets the nth number in the underlying representation that makes up the whole
     * `BigInt`.
     *
     * Params:
     *     T = the type to view the underlying representation as
     *     n = The nth number to retrieve. Must be less than $(LREF ulongLength) or
     *     $(LREF uintLength) with respect to `T`.
     * Returns:
     *     The nth `ulong` in the representation of this `BigInt`.
     */
    T getDigit(T = ulong)(size_t n) const
    if (is(T == ulong) || is(T == uint))
    {
        static if (is(T == ulong))
        {
            assert(n < ulongLength(), "getDigit index out of bounds");
            return data.peekUlong(n);
        }
        else
        {
            assert(n < uintLength(), "getDigit index out of bounds");
            return data.peekUint(n);
        }
    }

    ///
    @safe pure unittest
    {
        auto a = BigInt("1000");
        assert(a.ulongLength() == 1);
        assert(a.getDigit(0) == 1000);

        assert(a.uintLength() == 1);
        assert(a.getDigit!uint(0) == 1000);

        auto b = BigInt("2_000_000_000_000_000_000_000_000_000");
        assert(b.ulongLength() == 2);
        assert(b.getDigit(0) == 4584946418820579328);
        assert(b.getDigit(1) == 108420217);

        assert(b.uintLength() == 3);
        assert(b.getDigit!uint(0) == 3489660928);
        assert(b.getDigit!uint(1) == 1067516025);
        assert(b.getDigit!uint(2) == 108420217);
    }

private:
    void negate() @safe pure nothrow @nogc scope
    {
        if (!data.isZero())
            sign = !sign;
    }
    bool isZero() pure const nothrow @nogc @safe scope
    {
        return data.isZero();
    }
    alias isNegative = sign;

    // Generate a runtime error if division by zero occurs
    void checkDivByZero() pure const nothrow @safe scope
    {
        assert(!isZero(), "BigInt division by zero");
    }
}

///
@safe unittest
{
    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";
    BigInt k = j;
    j ^^= 11;
    assert(k ^^ 11 == j);
}

/**
Params:
    x = The `BigInt` to convert to a decimal `string`.

Returns:
    A `string` that represents the `BigInt` as a decimal number.

*/
string toDecimalString(const(BigInt) x) pure nothrow @safe
{
    auto buff = x.data.toDecimalString(x.isNegative ? 1 : 0);
    if (x.isNegative)
        buff[0] = '-';
    return buff;
}

///
@safe pure unittest
{
    auto x = BigInt("123");
    x *= 1000;
    x += 456;

    auto xstr = x.toDecimalString();
    assert(xstr == "123456");
}

/**
Params:
    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.

*/
string toHex(const(BigInt) x) @safe
{
    import std.array : appender;
    auto outbuff = appender!string();
    x.toString(outbuff, "%X");
    return outbuff[];
}

///
@safe unittest
{
    auto x = BigInt("123");
    x *= 1000;
    x += 456;

    auto xstr = x.toHex();
    assert(xstr == "1E240");
}

/** Returns the absolute value of x converted to the corresponding unsigned
type.

Params:
    x = The integral value to return the absolute value of.

Returns:
    The absolute value of x.

*/
Unsigned!T absUnsign(T)(T x)
if (isIntegral!T)
{
    static if (isSigned!T)
    {
        import std.conv : unsigned;
        /* This returns the correct result even when x = T.min
         * on two's complement machines because unsigned(T.min) = |T.min|
         * even though -T.min = T.min.
         */
        return unsigned((x < 0) ? cast(T)(0-x) : x);
    }
    else
    {
        return x;
    }
}

///
nothrow pure @safe
unittest
{
    assert((-1).absUnsign == 1);
    assert(1.absUnsign == 1);
}

nothrow pure @safe
unittest
{
    BigInt a, b;
    a = 1;
    b = 2;
    auto c = a + b;
    assert(c == 3);
}

nothrow pure @safe
unittest
{
    long a;
    BigInt b;
    auto c = a + b;
    assert(c == 0);
    auto d = b + a;
    assert(d == 0);
}

nothrow pure @safe
unittest
{
    BigInt x = 1, y = 2;
    assert(x <  y);
    assert(x <= y);
    assert(y >= x);
    assert(y >  x);
    assert(x != y);

    long r1 = x.toLong;
    assert(r1 == 1);

    BigInt r2 = 10 % x;
    assert(r2 == 0);

    BigInt r3 = 10 / y;
    assert(r3 == 5);

    BigInt[] arr = [BigInt(1)];
    auto incr = arr[0]++;
    assert(arr == [BigInt(2)]);
    assert(incr == BigInt(1));
}

@safe unittest
{
    // Radix conversion
    assert( toDecimalString(BigInt("-1_234_567_890_123_456_789"))
        == "-1234567890123456789");
    assert( toHex(BigInt("0x1234567890123456789")) == "123_45678901_23456789");
    assert( toHex(BigInt("0x00000000000000000000000000000000000A234567890123456789"))
        == "A23_45678901_23456789");
    assert( toHex(BigInt("0x000_00_000000_000_000_000000000000_000000_")) == "0");

    assert(BigInt(-0x12345678).toInt() == -0x12345678);
    assert(BigInt(-0x12345678).toLong() == -0x12345678);
    assert(BigInt(0x1234_5678_9ABC_5A5AL).ulongLength == 1);
    assert(BigInt(0x1234_5678_9ABC_5A5AL).toLong() == 0x1234_5678_9ABC_5A5AL);
    assert(BigInt(-0x1234_5678_9ABC_5A5AL).toLong() == -0x1234_5678_9ABC_5A5AL);
    assert(BigInt(0xF234_5678_9ABC_5A5AL).toLong() == long.max);
    assert(BigInt(-0x123456789ABCL).toInt() == -int.max);
    char[] s1 = "123".dup; // https://issues.dlang.org/show_bug.cgi?id=8164
    assert(BigInt(s1) == 123);
    char[] s2 = "0xABC".dup;
    assert(BigInt(s2) == 2748);

    assert((BigInt(-2) + BigInt(1)) == BigInt(-1));
    BigInt a = ulong.max - 5;
    auto b = -long.max % a;
    assert( b == -long.max % (ulong.max - 5));
    b = long.max / a;
    assert( b == long.max /(ulong.max - 5));
    assert(BigInt(1) - 1 == 0);
    assert((-4) % BigInt(5) == -4); // https://issues.dlang.org/show_bug.cgi?id=5928
    assert(BigInt(-4) % BigInt(5) == -4);
    assert(BigInt(2)/BigInt(-3) == BigInt(0)); // https://issues.dlang.org/show_bug.cgi?id=8022
    assert(BigInt("-1") > long.min); // https://issues.dlang.org/show_bug.cgi?id=9548

    assert(toDecimalString(BigInt("0000000000000000000000000000000000000000001234567"))
        == "1234567");
}

@safe unittest // Minimum signed value bug tests.
{
    assert(BigInt("-0x8000000000000000") == BigInt(long.min));
    assert(BigInt("-0x8000000000000000")+1 > BigInt(long.min));
    assert(BigInt("-0x80000000") == BigInt(int.min));
    assert(BigInt("-0x80000000")+1 > BigInt(int.min));
    assert(BigInt(long.min).toLong() == long.min); // lossy toLong bug for long.min
    assert(BigInt(int.min).toInt() == int.min); // lossy toInt bug for int.min
    assert(BigInt(long.min).ulongLength == 1);
    assert(BigInt(int.min).uintLength == 1); // cast/sign extend bug in opAssign
    BigInt a;
    a += int.min;
    assert(a == BigInt(int.min));
    a = int.min - BigInt(int.min);
    assert(a == 0);
    a = int.min;
    assert(a == BigInt(int.min));
    assert(int.min % (BigInt(int.min)-1) == int.min);
    assert((BigInt(int.min)-1)%int.min == -1);
}

 // Recursive division (https://issues.dlang.org/show_bug.cgi?id=5568)
@safe unittest
{
    enum Z = 4843;
    BigInt m = (BigInt(1) << (Z*8) ) - 1;
    m -= (BigInt(1) << (Z*6)) - 1;
    BigInt oldm = m;

    BigInt a = (BigInt(1) << (Z*4) )-1;
    BigInt b = m % a;
    m /= a;
    m *= a;
    assert( m + b == oldm);

    m = (BigInt(1) << (4846 + 4843) ) - 1;
    a = (BigInt(1) << 4846 ) - 1;
    b = (BigInt(1) << (4846*2 + 4843)) - 1;
    BigInt c = (BigInt(1) << (4846*2 + 4843*2)) - 1;
    BigInt w =  c - b + a;
    assert(w % m == 0);

    // https://issues.dlang.org/show_bug.cgi?id=6819
    BigInt z1 = BigInt(10)^^64;
    BigInt w1 = BigInt(10)^^128;
    assert(z1^^2 == w1);
    BigInt z2 = BigInt(1)<<64;
    BigInt w2 = BigInt(1)<<128;
    assert(z2^^2 == w2);
    // https://issues.dlang.org/show_bug.cgi?id=7993
    BigInt n7793 = 10;
    assert( n7793 / 1 == 10);
    // https://issues.dlang.org/show_bug.cgi?id=7973
    auto a7973 = 10_000_000_000_000_000;
    const c7973 = 10_000_000_000_000_000;
    immutable i7973 = 10_000_000_000_000_000;
    BigInt v7973 = 2551700137;
    v7973 %= a7973;
    assert(v7973 == 2551700137);
    v7973 %= c7973;
    assert(v7973 == 2551700137);
    v7973 %= i7973;
    assert(v7973 == 2551700137);
    // https://issues.dlang.org/show_bug.cgi?id=8165
    BigInt[2] a8165;
    a8165[0] = a8165[1] = 1;
}

@safe unittest
{
    import std.array;
    import std.format.write : formattedWrite;

    immutable string[][] table = [
    /*  fmt,        +10     -10 */
        ["%d",      "10",   "-10"],
        ["%+d",     "+10",  "-10"],
        ["%-d",     "10",   "-10"],
        ["%+-d",    "+10",  "-10"],

        ["%4d",     "  10", " -10"],
        ["%+4d",    " +10", " -10"],
        ["%-4d",    "10  ", "-10 "],
        ["%+-4d",   "+10 ", "-10 "],

        ["%04d",    "0010", "-010"],
        ["%+04d",   "+010", "-010"],
        ["%-04d",   "10  ", "-10 "],
        ["%+-04d",  "+10 ", "-10 "],

        ["% 04d",   " 010", "-010"],
        ["%+ 04d",  "+010", "-010"],
        ["%- 04d",  " 10 ", "-10 "],
        ["%+- 04d", "+10 ", "-10 "],
    ];

    auto w1 = appender!(char[])();
    auto w2 = appender!(char[])();

    foreach (entry; table)
    {
        immutable fmt = entry[0];

        formattedWrite(w1, fmt, BigInt(10));
        formattedWrite(w2, fmt, 10);
        assert(w1.data == w2.data);
        assert(w1.data == entry[1]);
        w1.clear();
        w2.clear();

        formattedWrite(w1, fmt, BigInt(-10));
        formattedWrite(w2, fmt, -10);
        assert(w1.data == w2.data);
        assert(w1.data == entry[2]);
        w1.clear();
        w2.clear();
    }
}

@safe unittest
{
    import std.array;
    import std.format.write : formattedWrite;

    immutable string[][] table = [
    /*  fmt,        +10     -10 */
        ["%x",      "a",    "-a"],
        ["%+x",     "a",    "-a"],
        ["%-x",     "a",    "-a"],
        ["%+-x",    "a",    "-a"],

        ["%4x",     "   a", "  -a"],
        ["%+4x",    "   a", "  -a"],
        ["%-4x",    "a   ", "-a  "],
        ["%+-4x",   "a   ", "-a  "],

        ["%04x",    "000a", "-00a"],
        ["%+04x",   "000a", "-00a"],
        ["%-04x",   "a   ", "-a  "],
        ["%+-04x",  "a   ", "-a  "],

        ["% 04x",   "000a", "-00a"],
        ["%+ 04x",  "000a", "-00a"],
        ["%- 04x",  "a   ", "-a  "],
        ["%+- 04x", "a   ", "-a  "],
    ];

    auto w1 = appender!(char[])();
    auto w2 = appender!(char[])();

    foreach (entry; table)
    {
        immutable fmt = entry[0];

        formattedWrite(w1, fmt, BigInt(10));
        formattedWrite(w2, fmt, 10);
        assert(w1.data == w2.data);     // Equal only positive BigInt
        assert(w1.data == entry[1]);
        w1.clear();
        w2.clear();

        formattedWrite(w1, fmt, BigInt(-10));
        //formattedWrite(w2, fmt, -10);
        //assert(w1.data == w2.data);
        assert(w1.data == entry[2]);
        w1.clear();
        //w2.clear();
    }
}

@safe unittest
{
    import std.array;
    import std.format.write : formattedWrite;

    immutable string[][] table = [
    /*  fmt,        +10     -10 */
        ["%X",      "A",    "-A"],
        ["%+X",     "A",    "-A"],
        ["%-X",     "A",    "-A"],
        ["%+-X",    "A",    "-A"],

        ["%4X",     "   A", "  -A"],
        ["%+4X",    "   A", "  -A"],
        ["%-4X",    "A   ", "-A  "],
        ["%+-4X",   "A   ", "-A  "],

        ["%04X",    "000A", "-00A"],
        ["%+04X",   "000A", "-00A"],
        ["%-04X",   "A   ", "-A  "],
        ["%+-04X",  "A   ", "-A  "],

        ["% 04X",   "000A", "-00A"],
        ["%+ 04X",  "000A", "-00A"],
        ["%- 04X",  "A   ", "-A  "],
        ["%+- 04X", "A   ", "-A  "],
    ];

    auto w1 = appender!(char[])();
    auto w2 = appender!(char[])();

    foreach (entry; table)
    {
        immutable fmt = entry[0];

        formattedWrite(w1, fmt, BigInt(10));
        formattedWrite(w2, fmt, 10);
        assert(w1.data == w2.data);     // Equal only positive BigInt
        assert(w1.data == entry[1]);
        w1.clear();
        w2.clear();

        formattedWrite(w1, fmt, BigInt(-10));
        //formattedWrite(w2, fmt, -10);
        //assert(w1.data == w2.data);
        assert(w1.data == entry[2]);
        w1.clear();
        //w2.clear();
    }
}

// https://issues.dlang.org/show_bug.cgi?id=6448
@safe unittest
{
    import std.array;
    import std.format.write : formattedWrite;

    auto w1 = appender!string();
    auto w2 = appender!string();

    int x = 100;
    formattedWrite(w1, "%010d", x);
    BigInt bx = x;
    formattedWrite(w2, "%010d", bx);
    assert(w1.data == w2.data);
    // https://issues.dlang.org/show_bug.cgi?id=8011
    BigInt y = -3;
    ++y;
    assert(y.toLong() == -2);
    y = 1;
    --y;
    assert(y.toLong() == 0);
    --y;
    assert(y.toLong() == -1);
    --y;
    assert(y.toLong() == -2);
}

@safe unittest
{
    import std.math.algebraic : abs;
    auto r = abs(BigInt(-1000)); // https://issues.dlang.org/show_bug.cgi?id=6486
    assert(r == 1000);

    auto r2 = abs(const(BigInt)(-500)); // https://issues.dlang.org/show_bug.cgi?id=11188
    assert(r2 == 500);
    auto r3 = abs(immutable(BigInt)(-733)); // https://issues.dlang.org/show_bug.cgi?id=11188
    assert(r3 == 733);

    // opCast!bool
    BigInt one = 1, zero;
    assert(one && !zero);
}

// https://issues.dlang.org/show_bug.cgi?id=6850
@safe unittest
{
    pure long pureTest() {
        BigInt a = 1;
        BigInt b = 1336;
        a += b;
        return a.toLong();
    }

    assert(pureTest() == 1337);
}

// https://issues.dlang.org/show_bug.cgi?id=8435
// https://issues.dlang.org/show_bug.cgi?id=10118
@safe unittest
{
    auto i = BigInt(100);
    auto j = BigInt(100);

    // Two separate BigInt instances representing same value should have same
    // hash.
    assert(typeid(i).getHash(&i) == typeid(j).getHash(&j));
    assert(typeid(i).compare(&i, &j) == 0);

    // BigInt AA keys should behave consistently.
    int[BigInt] aa;
    aa[BigInt(123)] = 123;
    assert(BigInt(123) in aa);

    aa[BigInt(123)] = 321;
    assert(aa[BigInt(123)] == 321);

    auto keys = aa.byKey;
    assert(keys.front == BigInt(123));
    keys.popFront();
    assert(keys.empty);
}

// https://issues.dlang.org/show_bug.cgi?id=11148
@safe unittest
{
    void foo(BigInt) {}
    const BigInt cbi = 3;
    immutable BigInt ibi = 3;

    foo(cbi);
    foo(ibi);

    import std.conv : to;
    import std.meta : AliasSeq;

    static foreach (T1; AliasSeq!(BigInt, const(BigInt), immutable(BigInt)))
    {
        static foreach (T2; AliasSeq!(BigInt, const(BigInt), immutable(BigInt)))
        {{
            T1 t1 = 2;
            T2 t2 = t1;

            T2 t2_1 = to!T2(t1);
            T2 t2_2 = cast(T2) t1;

            assert(t2 == t1);
            assert(t2 == 2);

            assert(t2_1 == t1);
            assert(t2_1 == 2);

            assert(t2_2 == t1);
            assert(t2_2 == 2);
        }}
    }

    BigInt n = 2;
    n *= 2;
    assert(n == 4);
}

// https://issues.dlang.org/show_bug.cgi?id=8167
@safe unittest
{
    BigInt a = BigInt(3);
    BigInt b = BigInt(a);
    assert(b == 3);
}

// https://issues.dlang.org/show_bug.cgi?id=9061
@safe unittest
{
    long l1 = 0x12345678_90ABCDEF;
    long l2 = 0xFEDCBA09_87654321;
    long l3 = l1 | l2;
    long l4 = l1 & l2;
    long l5 = l1 ^ l2;

    BigInt b1 = l1;
    BigInt b2 = l2;
    BigInt b3 = b1 | b2;
    BigInt b4 = b1 & b2;
    BigInt b5 = b1 ^ b2;

    assert(l3 == b3);
    assert(l4 == b4);
    assert(l5 == b5);
}

// https://issues.dlang.org/show_bug.cgi?id=11600
@safe unittest
{
    import std.conv;
    import std.exception : assertThrown;

    // Original bug report
    assertThrown!ConvException(to!BigInt("avadakedavra"));

    // Digit string lookalikes that are actually invalid
    assertThrown!ConvException(to!BigInt("0123hellothere"));
    assertThrown!ConvException(to!BigInt("-hihomarylowe"));
    assertThrown!ConvException(to!BigInt("__reallynow__"));
    assertThrown!ConvException(to!BigInt("-123four"));
}

// https://issues.dlang.org/show_bug.cgi?id=11583
@safe unittest
{
    BigInt x = 0;
    assert((x > 0) == false);
}

// https://issues.dlang.org/show_bug.cgi?id=13391
@safe unittest
{
    BigInt x1 = "123456789";
    BigInt x2 = "123456789123456789";
    BigInt x3 = "123456789123456789123456789";

    import std.meta : AliasSeq;
    static foreach (T; AliasSeq!(byte, ubyte, short, ushort, int, uint, long, ulong))
    {
        assert((x1 * T.max) / T.max == x1);
        assert((x2 * T.max) / T.max == x2);
        assert((x3 * T.max) / T.max == x3);
    }

    assert(x1 / -123456789 == -1);
    assert(x1 / 123456789U == 1);
    assert(x1 / -123456789L == -1);
    assert(x1 / 123456789UL == 1);
    assert(x2 / -123456789123456789L == -1);
    assert(x2 / 123456789123456789UL == 1);

    assert(x1 / uint.max == 0);
    assert(x1 / ulong.max == 0);
    assert(x2 / ulong.max == 0);

    x1 /= 123456789UL;
    assert(x1 == 1);
    x2 /= 123456789123456789UL;
    assert(x2 == 1);
}

// https://issues.dlang.org/show_bug.cgi?id=13963
@safe unittest
{
    BigInt x = 1;
    import std.meta : AliasSeq;
    static foreach (Int; AliasSeq!(byte, ubyte, short, ushort, int))
    {
        assert(is(typeof(x % Int(1)) == int));
    }
    assert(is(typeof(x % 1U) == long));
    assert(is(typeof(x % 1L) == long));
    assert(is(typeof(x % 1UL) == BigInt));

    auto x0 = BigInt(uint.max - 1);
    auto x1 = BigInt(8);
    assert(x1 / x == x1);
    auto x2 = -BigInt(long.min) + 1;

    // uint
    assert( x0 % uint.max ==  x0 % BigInt(uint.max));
    assert(-x0 % uint.max == -x0 % BigInt(uint.max));
    assert( x0 % uint.max ==  long(uint.max - 1));
    assert(-x0 % uint.max == -long(uint.max - 1));

    // long
    assert(x1 % 2L == 0L);
    assert(-x1 % 2L == 0L);

    assert(x1 % 3L == 2L);
    assert(x1 % -3L == 2L);
    assert(-x1 % 3L == -2L);
    assert(-x1 % -3L == -2L);

    assert(x1 % 11L == 8L);
    assert(x1 % -11L == 8L);
    assert(-x1 % 11L == -8L);
    assert(-x1 % -11L == -8L);

    // ulong
    assert(x1 % 2UL == BigInt(0));
    assert(-x1 % 2UL == BigInt(0));

    assert(x1 % 3UL == BigInt(2));
    assert(-x1 % 3UL == -BigInt(2));

    assert(x1 % 11UL == BigInt(8));
    assert(-x1 % 11UL == -BigInt(8));

    assert(x2 % ulong.max == x2);
    assert(-x2 % ulong.max == -x2);
}

// https://issues.dlang.org/show_bug.cgi?id=14124
@safe unittest
{
    auto x = BigInt(-3);
    x %= 3;
    assert(!x.isNegative);
    assert(x.isZero);

    x = BigInt(-3);
    x %= cast(ushort) 3;
    assert(!x.isNegative);
    assert(x.isZero);

    x = BigInt(-3);
    x %= 3L;
    assert(!x.isNegative);
    assert(x.isZero);

    x = BigInt(3);
    x %= -3;
    assert(!x.isNegative);
    assert(x.isZero);
}

// https://issues.dlang.org/show_bug.cgi?id=15678
@safe unittest
{
    import std.exception : assertThrown;
    assertThrown!ConvException(BigInt(""));
    assertThrown!ConvException(BigInt("0x1234BARF"));
    assertThrown!ConvException(BigInt("1234PUKE"));
}

// https://issues.dlang.org/show_bug.cgi?id=6447
@safe unittest
{
    import std.algorithm.comparison : equal;
    import std.range : iota;

    auto s = BigInt(1_000_000_000_000);
    auto e = BigInt(1_000_000_000_003);
    auto r = iota(s, e);
    assert(r.equal([
        BigInt(1_000_000_000_000),
        BigInt(1_000_000_000_001),
        BigInt(1_000_000_000_002)
    ]));
}

// https://issues.dlang.org/show_bug.cgi?id=17330
@safe unittest
{
    auto b = immutable BigInt("123");
    assert(b == 123);
}

// https://issues.dlang.org/show_bug.cgi?id=14767
@safe pure unittest
{
    static immutable a = BigInt("340282366920938463463374607431768211455");
    assert(a == BigInt("340282366920938463463374607431768211455"));

    BigInt plusTwo(in BigInt n)
    {
        return n + 2;
    }

    enum BigInt test1 = BigInt(123);
    enum BigInt test2 = plusTwo(test1);
    assert(test2 == 125);
}

/**
 * Finds the quotient and remainder for the given dividend and divisor in one operation.
 *
 * Params:
 *     dividend = the $(LREF BigInt) to divide
 *     divisor = the $(LREF BigInt) to divide the dividend by
 *     quotient = is set to the result of the division
 *     remainder = is set to the remainder of the division
 */
void divMod(const BigInt dividend, const BigInt divisor, out BigInt quotient, out BigInt remainder) pure nothrow @safe
{
    BigUint q, r;
    BigUint.divMod(dividend.data, divisor.data, q, r);
    quotient.sign = dividend.sign != divisor.sign;
    quotient.data = q;
    remainder.sign = dividend.sign;
    remainder.data = r;
}

///
@safe pure nothrow unittest
{
    auto a = BigInt(123);
    auto b = BigInt(25);
    BigInt q, r;

    divMod(a, b, q, r);

    assert(q == 4);
    assert(r == 23);
    assert(q * b + r == a);
}

// https://issues.dlang.org/show_bug.cgi?id=18086
@safe pure nothrow unittest
{
    BigInt q = 1;
    BigInt r = 1;
    BigInt c = 1024;
    BigInt d = 100;

    divMod(c, d, q, r);
    assert(q ==  10);
    assert(r ==  24);
    assert((q * d + r) == c);

    divMod(c, -d, q, r);
    assert(q == -10);
    assert(r ==  24);
    assert(q * -d + r == c);

    divMod(-c, -d, q, r);
    assert(q ==  10);
    assert(r == -24);
    assert(q * -d + r == -c);

    divMod(-c, d, q, r);
    assert(q == -10);
    assert(r == -24);
    assert(q * d + r == -c);
}

// https://issues.dlang.org/show_bug.cgi?id=19740
@safe unittest
{
    BigInt a = BigInt(
        "241127122100380210001001124020210001001100000200003101000062221012075223052000021042250111300200000000000" ~
        "000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000");
    BigInt b = BigInt(
        "700200000000500418321000401140010110000022007221432000000141020011323301104104060202100200457210001600142" ~
        "000001012245300100001110215200000000120000000000000000000000000000000000000000000000000000000000000000000" ~
        "00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000");

    BigInt c = a * b;
    assert(c == BigInt(
        "1688372108948068874722901180228375682334987075822938736581472847151834613694489486296103575639363261807341" ~
        "3910091006778604956808730652275328822700182498926542563654351871390166691461743896850906716336187966456064" ~
        "2702007176328110013356024000000000000000000000000000000000000000000000000000000000000000000000000000000000" ~
        "0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000" ~
        "0000000000000000000000000000000000000000000000000000000000000000000000000000000000000"));
}

@safe unittest
{
    auto n = BigInt("1234"d);
}

/**
Fast power modulus calculation for $(LREF BigInt) operands.
Params:
     base = the $(LREF BigInt) is basic operands.
     exponent = the $(LREF BigInt) is power exponent of base.
     modulus = the $(LREF BigInt) is modules to be modular of base ^ exponent.
Returns:
     The power modulus value of (base ^ exponent) % modulus.
*/
BigInt powmod(BigInt base, BigInt exponent, BigInt modulus) pure nothrow @safe
{
    BigInt result = 1;

    while (exponent)
    {
        if (exponent.data.peekUint(0) & 1)
        {
            result = (result * base) % modulus;
        }

        auto tmp = base % modulus;
        base = (tmp * tmp) % modulus;
        exponent >>= 1;
    }

    return result;
}

/// for powmod
@safe unittest
{
    BigInt base = BigInt("123456789012345678901234567890");
    BigInt exponent = BigInt("1234567890123456789012345678901234567");
    BigInt modulus = BigInt("1234567");

    BigInt result = powmod(base, exponent, modulus);
    assert(result == 359079);
}