/** 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!ulong(data, u, wantSub: sign != (y<0), sign);        }        else static if (op=="-")        {            data = BigUint.addOrSubInt!ulong(data, u, wantSub: sign == (y<0), sign);        }        else static if (op=="*")        {            if (y == 0 || data.isZero())            {                sign = false;                data = 0UL;                return this;            }            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;            if (y < 0)            {                checkDivByZero();                data = cast(ulong) (data == 1);            }            else            {                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;    }     // https://issues.dlang.org/show_bug.cgi?id=10565@safe unittest{    // Test cases from the issue    BigInt a = BigInt("0");    BigInt b = BigInt("-0");    BigInt c = BigInt("0") * -1;    BigInt d = BigInt("0") * -42;    BigInt e = BigInt("0"); e *= -1;    BigInt f = BigInt(c);    BigInt g = BigInt("0") * cast(byte) -1;    BigInt h = BigInt("0"); h *= BigInt("-1");    BigInt i = BigInt("0"); i -= 2 * i;    BigInt j = BigInt("0"); j = -j;    // All of these should be zero and not negative    auto values = [a, b, c, d, e, f, g, h, i, j];    foreach (val; values)    {        assert(val == 0, "BigInt value should be equal to zero");        assert(!(val < 0), "BigInt zero should not be negative");    }}     ///    @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`        ));    }     // https://issues.dlang.org/show_bug.cgi?id=24028    @system unittest    {        import std.exception : assertThrown;        import core.exception : AssertError;         assert(BigInt(100) ^^ -1 == BigInt(0));        assert(BigInt(1) ^^ -1 == BigInt(1));        assert(BigInt(-1) ^^ -1 == BigInt(-1));        assert(BigInt(-1) ^^ -2 == BigInt(1));        assertThrown!AssertError(BigInt(0) ^^ -1);    }     /**     * Implements assignment operators of the form `BigInt op= BigInt`.     */    BigInt opOpAssign(string op, T)(T y) pure nothrow @safe return scope    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;            }        }

Lines 1–500 of 2417. Load more