Unofficial Dub Package Documentation 
1 /** Arbitrary-precision ('bignum') arithmetic.
2  *
3  * Performance is optimized for numbers below ~1000 decimal digits.
4  * For X86 machines, highly optimised assembly routines are used.
5  *
6  * The following algorithms are currently implemented:
7  * $(UL
8  * $(LI Karatsuba multiplication)
9  * $(LI Squaring is optimized independently of multiplication)
10  * $(LI Divide-and-conquer division)
11  * $(LI Binary exponentiation)
12  * )
13  *
14  * For very large numbers, consider using the $(HTTP gmplib.org, GMP library) instead.
15  *
16  * License:   $(HTTP www.boost.org/LICENSE_1_0.txt, Boost License 1.0).
17  * Authors:   Don Clugston
18  * Source: $(PHOBOSSRC std/bigint.d)
19  */
20 /*          Copyright Don Clugston 2008 - 2010.
21  * Distributed under the Boost Software License, Version 1.0.
22  *    (See accompanying file LICENSE_1_0.txt or copy at
23  *          http://www.boost.org/LICENSE_1_0.txt)
24  */
25 
26 module std.bigint;
27 
28 import std.conv : ConvException;
29 
30 import std.format.spec : FormatSpec;
31 import std.format : FormatException;
32 import std.internal.math.biguintcore;
33 import std.internal.math.biguintnoasm : BigDigit;
34 import std.range.primitives;
35 import std.traits;
36 
37 /** A struct representing an arbitrary precision integer.
38  *
39  * All arithmetic operations are supported, except unsigned shift right (`>>>`).
40  * Bitwise operations (`|`, `&`, `^`, `~`) are supported, and behave as if BigInt was
41  * an infinite length 2's complement number.
42  *
43  * BigInt implements value semantics using copy-on-write. This means that
44  * assignment is cheap, but operations such as x++ will cause heap
45  * allocation. (But note that for most bigint operations, heap allocation is
46  * inevitable anyway.)
47  */
48 struct BigInt
49 {
50 private:
51     BigUint data;     // BigInt adds signed arithmetic to BigUint.
52     bool sign = false;
53 public:
54     /**
55      * Construct a `BigInt` from a decimal or hexadecimal string. The number must
56      * be in the form of a decimal or hex literal. It may have a leading `+`
57      * or `-` sign, followed by `0x` or `0X` if hexadecimal. Underscores are
58      * permitted in any location after the `0x` and/or the sign of the number.
59      *
60      * Params:
61      *     s = a finite bidirectional range of any character type
62      *
63      * Throws:
64      *     $(REF ConvException, std,conv) if the string doesn't represent a valid number
65      */
66     this(Range)(Range s) if (
67         isBidirectionalRange!Range &&
68         isSomeChar!(ElementType!Range) &&
69         !isInfinite!Range &&
70         !isNarrowString!Range)
71     {
72         import std.algorithm.iteration : filterBidirectional;
73         import std.algorithm.searching : startsWith;
74         import std.conv : ConvException;
75         import std.exception : enforce;
76         import std.utf : byChar;
77 
78         enforce!ConvException(!s.empty, "Can't initialize BigInt with an empty range");
79 
80         bool neg = false;
81         bool ok;
82 
83         data = 0UL;
84 
85         // check for signs and if the string is a hex value
86         if (s.front == '+')
87         {
88             s.popFront(); // skip '+'
89         }
90         else if (s.front == '-')
91         {
92             neg = true;
93             s.popFront();
94         }
95 
96         if (s.save.startsWith("0x".byChar) ||
97             s.save.startsWith("0X".byChar))
98         {
99             s.popFront;
100             s.popFront;
101 
102             if (!s.empty)
103                 ok = data.fromHexString(s.filterBidirectional!(a => a != '_'));
104             else
105                 ok = false;
106         }
107         else
108         {
109             ok = data.fromDecimalString(s.filterBidirectional!(a => a != '_'));
110         }
111 
112         enforce!ConvException(ok, "Not a valid numerical string");
113 
114         if (isZero())
115             neg = false;
116 
117         sign = neg;
118     }
119 
120     /// ditto
121     this(Range)(Range s) pure
122     if (isNarrowString!Range)
123     {
124         import std.utf : byCodeUnit;
125         this(s.byCodeUnit);
126     }
127 
128     @safe unittest
129     {
130         // system because of the dummy ranges eventually call std.array!string
131         import std.exception : assertThrown;
132         import std.internal.test.dummyrange;
133 
134         auto r1 = new ReferenceBidirectionalRange!dchar("101");
135         auto big1 = BigInt(r1);
136         assert(big1 == BigInt(101));
137 
138         auto r2 = new ReferenceBidirectionalRange!dchar("1_000");
139         auto big2 = BigInt(r2);
140         assert(big2 == BigInt(1000));
141 
142         auto r3 = new ReferenceBidirectionalRange!dchar("0x0");
143         auto big3 = BigInt(r3);
144         assert(big3 == BigInt(0));
145 
146         auto r4 = new ReferenceBidirectionalRange!dchar("0x");
147         assertThrown!ConvException(BigInt(r4));
148     }
149 
150     /**
151      * Construct a `BigInt` from a sign and a magnitude.
152      *
153      * The magnitude is an $(REF_ALTTEXT input range, isInputRange, std,range,primitives)
154      * of unsigned integers that satisfies either $(REF hasLength, std,range,primitives)
155      * or $(REF isForwardRange, std,range,primitives). The first (leftmost)
156      * element of the magnitude is considered the most significant.
157      *
158      * Params:
159      *     isNegative = true for negative, false for non-negative
160      *          (ignored when magnitude is zero)
161      *     magnitude = a finite range of unsigned integers
162      */
163     this(Range)(bool isNegative, Range magnitude) if (
164         isInputRange!Range &&
165         isUnsigned!(ElementType!Range) &&
166         (hasLength!Range || isForwardRange!Range) &&
167         !isInfinite!Range)
168     {
169         data.fromMagnitude(magnitude);
170         sign = isNegative && !data.isZero;
171     }
172 
173     ///
174     pure @safe unittest
175     {
176         ubyte[] magnitude = [1, 2, 3, 4, 5, 6];
177         auto b1 = BigInt(false, magnitude);
178         assert(cast(long) b1 == 0x01_02_03_04_05_06L);
179         auto b2 = BigInt(true, magnitude);
180         assert(cast(long) b2 == -0x01_02_03_04_05_06L);
181     }
182 
183     /// Construct a `BigInt` from a built-in integral type.
184     this(T)(T x) pure nothrow @safe if (isIntegral!T)
185     {
186         data = data.init; // @@@: Workaround for compiler bug
187         opAssign(x);
188     }
189 
190     ///
191     @safe unittest
192     {
193         ulong data = 1_000_000_000_000;
194         auto bigData = BigInt(data);
195         assert(bigData == BigInt("1_000_000_000_000"));
196     }
197 
198     /// Construct a `BigInt` from another `BigInt`.
199     this(T)(T x) pure nothrow @safe if (is(immutable T == immutable BigInt))
200     {
201         opAssign(x);
202     }
203 
204     ///
205     @safe unittest
206     {
207         const(BigInt) b1 = BigInt("1_234_567_890");
208         BigInt b2 = BigInt(b1);
209         assert(b2 == BigInt("1_234_567_890"));
210     }
211 
212     /// Assignment from built-in integer types.
213     BigInt opAssign(T)(T x) pure nothrow @safe if (isIntegral!T)
214     {
215         data = cast(ulong) absUnsign(x);
216         sign = (x < 0);
217         return this;
218     }
219 
220     ///
221     @safe unittest
222     {
223         auto b = BigInt("123");
224         b = 456;
225         assert(b == BigInt("456"));
226     }
227 
228     /// Assignment from another BigInt.
229     BigInt opAssign(T:BigInt)(T x) pure @nogc @safe
230     {
231         data = x.data;
232         sign = x.sign;
233         return this;
234     }
235 
236     ///
237     @safe unittest
238     {
239         auto b1 = BigInt("123");
240         auto b2 = BigInt("456");
241         b2 = b1;
242         assert(b2 == BigInt("123"));
243     }
244 
245     /**
246      * Implements assignment operators from built-in integers of the form
247      * `BigInt op= integer`.
248      */
249     BigInt opOpAssign(string op, T)(T y) pure nothrow @safe return scope
250         if ((op=="+" || op=="-" || op=="*" || op=="/" || op=="%"
251           || op==">>" || op=="<<" || op=="^^" || op=="|" || op=="&" || op=="^") && isIntegral!T)
252     {
253         ulong u = absUnsign(y);
254 
255         static if (op=="+")
256         {
257             data = BigUint.addOrSubInt!ulong(data, u, wantSub: sign != (y<0), sign);
258         }
259         else static if (op=="-")
260         {
261             data = BigUint.addOrSubInt!ulong(data, u, wantSub: sign == (y<0), sign);
262         }
263         else static if (op=="*")
264         {
265             if (y == 0)
266             {
267                 sign = false;
268                 data = 0UL;
269             }
270             else
271             {
272                 sign = ( sign != (y<0) );
273                 data = BigUint.mulInt(data, u);
274             }
275         }
276         else static if (op=="/")
277         {
278             assert(y != 0, "Division by zero");
279             static if (T.sizeof <= uint.sizeof)
280             {
281                 data = BigUint.divInt(data, cast(uint) u);
282             }
283             else
284             {
285                 data = BigUint.divInt(data, u);
286             }
287             sign = data.isZero() ? false : sign ^ (y < 0);
288         }
289         else static if (op=="%")
290         {
291             assert(y != 0, "Division by zero");
292             static if (is(immutable(T) == immutable(long)) || is( immutable(T) == immutable(ulong) ))
293             {
294                 this %= BigInt(y);
295             }
296             else
297             {
298                 data = cast(ulong) BigUint.modInt(data, cast(uint) u);
299                 if (data.isZero())
300                     sign = false;
301             }
302             // x%y always has the same sign as x.
303             // This is not the same as mathematical mod.
304         }
305         else static if (op==">>" || op=="<<")
306         {
307             // Do a left shift if y>0 and <<, or
308             // if y<0 and >>; else do a right shift.
309             if (y == 0)
310                 return this;
311             else if ((y > 0) == (op=="<<"))
312             {
313                 // Sign never changes during left shift
314                 data = data.opBinary!(op)(u);
315             }
316             else
317             {
318                 data = data.opBinary!(op)(u);
319                 if (data.isZero())
320                     sign = false;
321             }
322         }
323         else static if (op=="^^")
324         {
325             sign = (y & 1) ? sign : false;
326             if (y < 0)
327             {
328                 checkDivByZero();
329                 data = cast(ulong) (data == 1);
330             }
331             else
332             {
333                 data = BigUint.pow(data, u);
334             }
335         }
336         else static if (op=="&")
337         {
338             if (y >= 0 && (y <= 1 || !sign)) // In these cases we can avoid some allocation.
339             {
340                 static if (T.sizeof <= uint.sizeof && BigDigit.sizeof <= uint.sizeof)
341                     data = cast(ulong) data.peekUint(0) & y;
342                 else
343                     data = data.peekUlong(0) & y;
344                 sign = false;
345             }
346             else
347             {
348                 BigInt b = y;
349                 opOpAssign!op(b);
350             }
351         }
352         else static if (op=="|" || op=="^")
353         {
354             BigInt b = y;
355             opOpAssign!op(b);
356         }
357         else static assert(0, "BigInt " ~ op[0..$-1] ~ "= " ~ T.stringof ~ " is not supported");
358         return this;
359     }
360 
361     ///
362     @safe unittest
363     {
364         auto b = BigInt("1_000_000_000");
365 
366         b += 12345;
367         assert(b == BigInt("1_000_012_345"));
368 
369         b /= 5;
370         assert(b == BigInt("200_002_469"));
371     }
372 
373     // https://issues.dlang.org/show_bug.cgi?id=16264
374     @safe unittest
375     {
376         auto a = BigInt(
377     `335690982744637013564796917901053301979460129353374296317539383938630086938` ~
378     `465898213033510992292836631752875403891802201862860531801760096359705447768` ~
379     `957432600293361240407059207520920532482429912948952142341440301429494694368` ~
380     `264560802292927144211230021750155988283029753927847924288850436812178022006` ~
381     `408597793414273953252832688620479083497367463977081627995406363446761896298` ~
382     `967177607401918269561385622811274398143647535024987050366350585544531063531` ~
383     `7118554808325723941557169427279911052268935775`);
384 
385         auto b = BigInt(
386     `207672245542926038535480439528441949928508406405023044025560363701392340829` ~
387     `852529131306106648201340460604257466180580583656068555417076345439694125326` ~
388     `843947164365500055567495554645796102453565953360564114634705366335703491527` ~
389     `429426780005741168078089657359833601261803592920462081364401456331489106355` ~
390     `199133982282631108670436696758342051198891939367812305559960349479160308314` ~
391     `068518200681530999860641597181672463704794566473241690395901768680673716414` ~
392     `243691584391572899147223065906633310537507956952626106509069491302359792769` ~
393     `378934570685117202046921464019396759638376362935855896435623442486036961070` ~
394     `534574698959398017332214518246531363445309522357827985468581166065335726996` ~
395     `711467464306784543112544076165391268106101754253962102479935962248302404638` ~
396     `21737237102628470475027851189594709504`);
397 
398         BigInt c = a * b;  // Crashes
399 
400         assert(c == BigInt(
401     `697137001950904057507249234183127244116872349433141878383548259425589716813` ~
402     `135440660252012378417669596912108637127036044977634382385990472429604619344` ~
403     `738746224291111527200379708978133071390303850450970292020176369525401803474` ~
404     `998613408923490273129022167907826017408385746675184651576154302536663744109` ~
405     `111018961065316024005076097634601030334948684412785487182572502394847587887` ~
406     `507385831062796361152176364659197432600147716058873232435238712648552844428` ~
407     `058885217631715287816333209463171932255049134340904981280717725999710525214` ~
408     `161541960645335744430049558161514565159449390036287489478108344584188898872` ~
409     `434914159748515512161981956372737022393466624249130107254611846175580584736` ~
410     `276213025837422102290580044755202968610542057651282410252208599309841499843` ~
411     `672251048622223867183370008181364966502137725166782667358559333222947265344` ~
412     `524195551978394625568228658697170315141077913403482061673401937141405425042` ~
413     `283546509102861986303306729882186190883772633960389974665467972016939172303` ~
414     `653623175801495207204880400522581834672918935651426160175413277309985678579` ~
415     `830872397214091472424064274864210953551447463312267310436493480881235642109` ~
416     `668498742629676513172286703948381906930297135997498416573231570483993847269` ~
417     `479552708416124555462530834668011570929850407031109157206202741051573633443` ~
418     `58105600`
419         ));
420     }
421 
422     // https://issues.dlang.org/show_bug.cgi?id=24028
423     @system unittest
424     {
425         import std.exception : assertThrown;
426         import core.exception : AssertError;
427 
428         assert(BigInt(100) ^^ -1 == BigInt(0));
429         assert(BigInt(1) ^^ -1 == BigInt(1));
430         assert(BigInt(-1) ^^ -1 == BigInt(-1));
431         assert(BigInt(-1) ^^ -2 == BigInt(1));
432         assertThrown!AssertError(BigInt(0) ^^ -1);
433     }
434 
435     /**
436      * Implements assignment operators of the form `BigInt op= BigInt`.
437      */
438     BigInt opOpAssign(string op, T)(T y) pure nothrow @safe return scope
439         if ((op=="+" || op== "-" || op=="*" || op=="|" || op=="&" || op=="^" || op=="/" || op=="%")
440             && is (T: BigInt))
441     {
442         static if (op == "+")
443         {
444             data = BigUint.addOrSub(data, y.data, sign != y.sign, sign);
445         }
446         else static if (op == "-")
447         {
448             data = BigUint.addOrSub(data, y.data, sign == y.sign, sign);
449         }
450         else static if (op == "*")
451         {
452             data = BigUint.mul(data, y.data);
453             sign = isZero() ? false : sign ^ y.sign;
454         }
455         else static if (op == "/")
456         {
457             y.checkDivByZero();
458             if (!isZero())
459             {
460                 data = BigUint.div(data, y.data);
461                 sign = isZero() ? false : sign ^ y.sign;
462             }
463         }
464         else static if (op == "%")
465         {
466             y.checkDivByZero();
467             if (!isZero())
468             {
469                 data = BigUint.mod(data, y.data);
470                 // x%y always has the same sign as x.
471                 if (isZero())
472                     sign = false;
473             }
474         }
475         else static if (op == "|" || op == "&" || op == "^")
476         {
477             data = BigUint.bitwiseOp!op(data, y.data, sign, y.sign, sign);
478         }
479         else static assert(0, "BigInt " ~ op[0..$-1] ~ "= " ~
480             T.stringof ~ " is not supported");
481         return this;
482     }
483 
484     ///
485     @safe unittest
486     {
487         auto x = BigInt("123");
488         auto y = BigInt("321");
489         x += y;
490         assert(x == BigInt("444"));
491     }
492 
493     /**
494      * Implements binary operators between `BigInt`s.
495      */
496     BigInt opBinary(string op, T)(T y) pure nothrow @safe const return scope
497         if ((op=="+" || op == "*" || op=="-" || op=="|" || op=="&" || op=="^" ||
498             op=="/" || op=="%")
499             && is (T: BigInt))
500     {
501         BigInt r = this;
502         return r.opOpAssign!(op)(y);
503     }
504 
505     ///
506     @safe unittest
507     {
508         auto x = BigInt("123");
509         auto y = BigInt("456");
510         BigInt z = x * y;
511         assert(z == BigInt("56088"));
512     }
513 
514     /**
515      * Implements binary operators between `BigInt`'s and built-in integers.
516      */
517     BigInt opBinary(string op, T)(T y) pure nothrow @safe const return scope
518         if ((op=="+" || op == "*" || op=="-" || op=="/" || op=="|" || op=="&" ||
519             op=="^"|| op==">>" || op=="<<" || op=="^^")
520             && isIntegral!T)
521     {
522         BigInt r = this;
523         r.opOpAssign!(op)(y);
524         return r;
525     }
526 
527     ///
528     @safe unittest
529     {
530         auto x = BigInt("123");
531         x *= 300;
532         assert(x == BigInt("36900"));
533     }
534 
535     /**
536         Implements a narrowing remainder operation with built-in integer types.
537 
538         This binary operator returns a narrower, built-in integer type
539         where applicable, according to the following table.
540 
541         $(TABLE ,
542         $(TR $(TD `BigInt`) $(TD $(CODE_PERCENT)) $(TD `uint`) $(TD $(RARR)) $(TD `long`))
543         $(TR $(TD `BigInt`) $(TD $(CODE_PERCENT)) $(TD `long`) $(TD $(RARR)) $(TD `long`))
544         $(TR $(TD `BigInt`) $(TD $(CODE_PERCENT)) $(TD `ulong`) $(TD $(RARR)) $(TD `BigInt`))
545         $(TR $(TD `BigInt`) $(TD $(CODE_PERCENT)) $(TD other type) $(TD $(RARR)) $(TD `int`))
546         )
547      */
548     auto opBinary(string op, T)(T y) pure nothrow @safe const
549         if (op == "%" && isIntegral!T)
550     {
551         assert(y != 0, "% 0 not allowed");
552 
553         // BigInt % uint => long
554         // BigInt % long => long
555         // BigInt % ulong => BigInt
556         // BigInt % other_type => int
557         static if (is(immutable T == immutable long) || is(immutable T == immutable ulong))
558         {
559             auto r = this % BigInt(y);
560 
561             static if (is(immutable T == immutable long))
562             {
563                 return r.toLong();
564             }
565             else
566             {
567                 // return as-is to avoid overflow
568                 return r;
569             }
570         }
571         else
572         {
573             immutable uint u = absUnsign(y);
574             static if (is(immutable T == immutable uint))
575                alias R = long;
576             else
577                alias R = int;
578             R rem = BigUint.modInt(data, u);
579             // x%y always has the same sign as x.
580             // This is not the same as mathematical mod.
581             return sign ? -rem : rem;
582         }
583     }
584 
585     ///
586     @safe unittest
587     {
588         auto  x  = BigInt("1_000_000_500");
589         long  l  = 1_000_000L;
590         ulong ul = 2_000_000UL;
591         int   i  = 500_000;
592         short s  = 30_000;
593 
594         assert(is(typeof(x % l)  == long)   && x % l  == 500L);
595         assert(is(typeof(x % ul) == BigInt) && x % ul == BigInt(500));
596         assert(is(typeof(x % i)  == int)    && x % i  == 500);
597         assert(is(typeof(x % s)  == int)    && x % s  == 10500);
598     }
599 
600     /**
601         Implements operators with built-in integers on the left-hand side and
602         `BigInt` on the right-hand side.
603      */
604     BigInt opBinaryRight(string op, T)(T y) pure nothrow @safe const
605         if ((op=="+" || op=="*" || op=="|" || op=="&" || op=="^") && isIntegral!T)
606     {
607         return opBinary!(op)(y);
608     }
609 
610     ///
611     @safe unittest
612     {
613         auto x = BigInt("100");
614         BigInt y = 123 + x;
615         assert(y == BigInt("223"));
616 
617         BigInt z = 123 - x;
618         assert(z == BigInt("23"));
619 
620         // Dividing a built-in integer type by BigInt always results in
621         // something that fits in a built-in type, so the built-in type is
622         // returned, not BigInt.
623         assert(is(typeof(1000 / x) == int));
624         assert(1000 / x == 10);
625     }
626 
627     //  BigInt = integer op BigInt
628     /// ditto
629     BigInt opBinaryRight(string op, T)(T y) pure nothrow @safe const
630         if (op == "-" && isIntegral!T)
631     {
632         ulong u = absUnsign(y);
633         BigInt r;
634         static if (op == "-")
635         {
636             r.sign = sign;
637             r.data = BigUint.addOrSubInt!ulong(data, u, wantSub: sign == (y<0), r.sign);
638             r.negate();
639         }
640         return r;
641     }
642 
643     //  integer = integer op BigInt
644     /// ditto
645     T opBinaryRight(string op, T)(T x) pure nothrow @safe const
646         if ((op=="%" || op=="/") && isIntegral!T)
647     {
648         checkDivByZero();
649 
650         static if (op == "%")
651         {
652             // x%y always has the same sign as x.
653             if (data.ulongLength > 1)
654                 return x;
655             immutable u = absUnsign(x);
656             immutable rem = u % data.peekUlong(0);
657             // x%y always has the same sign as x.
658             return cast(T)((x<0) ? -rem : rem);
659         }
660         else static if (op == "/")
661         {
662             if (data.ulongLength > 1)
663                 return 0;
664             return cast(T)(x / data.peekUlong(0));
665         }
666     }
667 
668     // const unary operations
669     /**
670         Implements `BigInt` unary operators.
671      */
672     BigInt opUnary(string op)() pure nothrow @safe const if (op=="+" || op=="-" || op=="~")
673     {
674        static if (op=="-")
675        {
676             BigInt r = this;
677             r.negate();
678             return r;
679         }
680         else static if (op=="~")
681         {
682             return -(this+1);
683         }
684         else static if (op=="+")
685            return this;
686     }
687 
688     // non-const unary operations
689     /// ditto
690     BigInt opUnary(string op)() pure nothrow @safe if (op=="++" || op=="--")
691     {
692         static if (op=="++")
693         {
694             data = BigUint.addOrSubInt!ulong(data, 1UL, wantSub: sign, sign);
695             return this;
696         }
697         else static if (op=="--")
698         {
699             data = BigUint.addOrSubInt!ulong(data, 1UL, wantSub: !sign, sign);
700             return this;
701         }
702     }
703 
704     ///
705     @safe unittest
706     {
707         auto x = BigInt("1234");
708         assert(-x == BigInt("-1234"));
709 
710         ++x;
711         assert(x == BigInt("1235"));
712     }
713 
714     /**
715         Implements `BigInt` equality test with other `BigInt`'s and built-in
716         numeric types.
717      */
718     bool opEquals()(auto ref const BigInt y) const pure @nogc @safe
719     {
720        return sign == y.sign && y.data == data;
721     }
722 
723     /// ditto
724     bool opEquals(T)(const T y) const pure nothrow @nogc @safe if (isIntegral!T)
725     {
726         if (sign != (y<0))
727             return 0;
728         return data.opEquals(cast(ulong) absUnsign(y));
729     }
730 
731     /// ditto
732     bool opEquals(T)(const T y) const pure nothrow @nogc if (isFloatingPoint!T)
733     {
734         return 0 == opCmp(y);
735     }
736 
737     ///
738     @safe unittest
739     {
740         // Note that when comparing a BigInt to a float or double the
741         // full precision of the BigInt is always considered, unlike
742         // when comparing an int to a float or a long to a double.
743         assert(BigInt(123456789) != cast(float) 123456789);
744     }
745 
746     @safe unittest
747     {
748         auto x = BigInt("12345");
749         auto y = BigInt("12340");
750         int z = 12345;
751         int w = 54321;
752 
753         assert(x == x);
754         assert(x != y);
755         assert(x == y + 5);
756         assert(x == z);
757         assert(x != w);
758     }
759 
760     @safe unittest
761     {
762         import std.math.operations : nextDown, nextUp;
763 
764         const x = BigInt("0x1abc_de80_0000_0000_0000_0000_0000_0000");
765         BigInt x1 = x + 1;
766         BigInt x2 = x - 1;
767 
768         const d = 0x1.abcde8p124;
769         assert(x == d);
770         assert(x1 != d);
771         assert(x2 != d);
772         assert(x != nextUp(d));
773         assert(x != nextDown(d));
774         assert(x != double.nan);
775 
776         const dL = 0x1.abcde8p124L;
777         assert(x == dL);
778         assert(x1 != dL);
779         assert(x2 != dL);
780         assert(x != nextUp(dL));
781         assert(x != nextDown(dL));
782         assert(x != real.nan);
783 
784         assert(BigInt(0) == 0.0f);
785         assert(BigInt(0) == 0.0);
786         assert(BigInt(0) == 0.0L);
787         assert(BigInt(0) == -0.0f);
788         assert(BigInt(0) == -0.0);
789         assert(BigInt(0) == -0.0L);
790         assert(BigInt("999_999_999_999_999_999_999_999_999_999_999_999_999") != float.infinity);
791     }
792 
793     /**
794         Implements casting to `bool`.
795      */
796     T opCast(T:bool)() pure nothrow @nogc @safe const
797     {
798         return !isZero();
799     }
800 
801     ///
802     @safe unittest
803     {
804         // Non-zero values are regarded as true
805         auto x = BigInt("1");
806         auto y = BigInt("10");
807         assert(x);
808         assert(y);
809 
810         // Zero value is regarded as false
811         auto z = BigInt("0");
812         assert(!z);
813     }
814 
815     /**
816         Implements casting to integer types.
817 
818         Throws: $(REF ConvOverflowException, std,conv) if the number exceeds
819         the target type's range.
820      */
821     T opCast(T:ulong)() pure @safe const
822     {
823         if (isUnsigned!T && sign)
824             { /* throw */ }
825         else
826         if (data.ulongLength == 1)
827         {
828             ulong l = data.peekUlong(0);
829             if (isUnsigned!T || !sign)
830             {
831                 if (l <= T.max)
832                     return cast(T) l;
833             }
834             else
835             {
836                 if (l <= ulong(T.max)+1)
837                     return cast(T)-long(l); // -long.min == long.min
838             }
839         }
840 
841         import std.conv : ConvOverflowException;
842         import std.string : format;
843         throw new ConvOverflowException(
844             "BigInt(%s) cannot be represented as a %s"
845             .format(this.toDecimalString, T.stringof));
846     }
847 
848     ///
849     @safe unittest
850     {
851         import std.conv : to, ConvOverflowException;
852         import std.exception : assertThrown;
853 
854         assert(BigInt("0").to!int == 0);
855 
856         assert(BigInt("0").to!ubyte == 0);
857         assert(BigInt("255").to!ubyte == 255);
858         assertThrown!ConvOverflowException(BigInt("256").to!ubyte);
859         assertThrown!ConvOverflowException(BigInt("-1").to!ubyte);
860     }
861 
862     @safe unittest
863     {
864         import std.conv : to, ConvOverflowException;
865         import std.exception : assertThrown;
866 
867         assert(BigInt("-1").to!byte == -1);
868         assert(BigInt("-128").to!byte == -128);
869         assert(BigInt("127").to!byte == 127);
870         assertThrown!ConvOverflowException(BigInt("-129").to!byte);
871         assertThrown!ConvOverflowException(BigInt("128").to!byte);
872 
873         assert(BigInt("0").to!uint == 0);
874         assert(BigInt("4294967295").to!uint == uint.max);
875         assertThrown!ConvOverflowException(BigInt("4294967296").to!uint);
876         assertThrown!ConvOverflowException(BigInt("-1").to!uint);
877 
878         assert(BigInt("-1").to!int == -1);
879         assert(BigInt("-2147483648").to!int == int.min);
880         assert(BigInt("2147483647").to!int == int.max);
881         assertThrown!ConvOverflowException(BigInt("-2147483649").to!int);
882         assertThrown!ConvOverflowException(BigInt("2147483648").to!int);
883 
884         assert(BigInt("0").to!ulong == 0);
885         assert(BigInt("18446744073709551615").to!ulong == ulong.max);
886         assertThrown!ConvOverflowException(BigInt("18446744073709551616").to!ulong);
887         assertThrown!ConvOverflowException(BigInt("-1").to!ulong);
888 
889         assert(BigInt("-1").to!long == -1);
890         assert(BigInt("-9223372036854775808").to!long == long.min);
891         assert(BigInt("9223372036854775807").to!long == long.max);
892         assertThrown!ConvOverflowException(BigInt("-9223372036854775809").to!long);
893         assertThrown!ConvOverflowException(BigInt("9223372036854775808").to!long);
894     }
895 
896     /**
897         Implements casting to floating point types.
898      */
899     T opCast(T)() @safe nothrow @nogc const if (isFloatingPoint!T)
900     {
901         return toFloat!(T, "nearest");
902     }
903 
904     ///
905     @system unittest
906     {
907         assert(cast(float)  BigInt("35540592535949172786332045140593475584")
908                 == 35540592535949172786332045140593475584.0f);
909         assert(cast(double) BigInt("35540601499647381470685035515422441472")
910                 == 35540601499647381470685035515422441472.0);
911         assert(cast(real)   BigInt("35540601499647381470685035515422441472")
912                 == 35540601499647381470685035515422441472.0L);
913 
914         assert(cast(float)  BigInt("-0x1345_6780_0000_0000_0000_0000_0000") == -0x1.3456_78p+108f       );
915         assert(cast(double) BigInt("-0x1345_678a_bcde_f000_0000_0000_0000") == -0x1.3456_78ab_cdefp+108 );
916         assert(cast(real)   BigInt("-0x1345_678a_bcde_f000_0000_0000_0000") == -0x1.3456_78ab_cdefp+108L);
917     }
918 
919     /// Rounding when casting to floating point
920     @system unittest
921     {
922         // BigInts whose values cannot be exactly represented as float/double/real
923         // are rounded when cast to float/double/real. When cast to float or
924         // double or 64-bit real the rounding is strictly defined. When cast
925         // to extended-precision real the rounding rules vary by environment.
926 
927         // BigInts that fall somewhere between two non-infinite floats/doubles
928         // are rounded to the closer value when cast to float/double.
929         assert(cast(float) BigInt(0x1aaa_aae7) == 0x1.aaa_aaep+28f);
930         assert(cast(float) BigInt(0x1aaa_aaff) == 0x1.aaa_ab0p+28f);
931         assert(cast(float) BigInt(-0x1aaa_aae7) == -0x1.aaaaaep+28f);
932         assert(cast(float) BigInt(-0x1aaa_aaff) == -0x1.aaaab0p+28f);
933 
934         assert(cast(double) BigInt(0x1aaa_aaaa_aaaa_aa77) == 0x1.aaa_aaaa_aaaa_aa00p+60);
935         assert(cast(double) BigInt(0x1aaa_aaaa_aaaa_aaff) == 0x1.aaa_aaaa_aaaa_ab00p+60);
936         assert(cast(double) BigInt(-0x1aaa_aaaa_aaaa_aa77) == -0x1.aaa_aaaa_aaaa_aa00p+60);
937         assert(cast(double) BigInt(-0x1aaa_aaaa_aaaa_aaff) == -0x1.aaa_aaaa_aaaa_ab00p+60);
938 
939         // BigInts that fall exactly between two non-infinite floats/doubles
940         // are rounded away from zero when cast to float/double. (Note that
941         // in most environments this is NOT the same rounding rule rule used
942         // when casting int/long to float/double.)
943         assert(cast(float) BigInt(0x1aaa_aaf0) == 0x1.aaa_ab0p+28f);
944         assert(cast(float) BigInt(-0x1aaa_aaf0) == -0x1.aaaab0p+28f);
945 
946         assert(cast(double) BigInt(0x1aaa_aaaa_aaaa_aa80) == 0x1.aaa_aaaa_aaaa_ab00p+60);
947         assert(cast(double) BigInt(-0x1aaa_aaaa_aaaa_aa80) == -0x1.aaa_aaaa_aaaa_ab00p+60);
948 
949         // BigInts that are bounded on one side by the largest positive or
950         // most negative finite float/double and on the other side by infinity
951         // or -infinity are rounded as if in place of infinity was the value
952         // `2^^(T.max_exp)` when cast to float/double.
953         assert(cast(float) BigInt("999_999_999_999_999_999_999_999_999_999_999_999_999") == float.infinity);
954         assert(cast(float) BigInt("-999_999_999_999_999_999_999_999_999_999_999_999_999") == -float.infinity);
955 
956         assert(cast(double) BigInt("999_999_999_999_999_999_999_999_999_999_999_999_999") < double.infinity);
957         assert(cast(real) BigInt("999_999_999_999_999_999_999_999_999_999_999_999_999") < real.infinity);
958     }
959 
960     @safe unittest
961     {
962         // Test exponent overflow is correct.
963         assert(cast(float) BigInt(0x1fffffff) == 0x1.000000p+29f);
964         assert(cast(double) BigInt(0x1fff_ffff_ffff_fff0) == 0x1.000000p+61);
965     }
966 
967     private T toFloat(T, string roundingMode)() @safe nothrow @nogc const
968     if (__traits(isFloating, T) && (roundingMode == "nearest" || roundingMode == "truncate"))
969     {
970         import core.bitop : bsr;
971         enum performRounding = (roundingMode == "nearest");
972         enum performTruncation = (roundingMode == "truncate");
973         static assert(performRounding || performTruncation, "unrecognized rounding mode");
974         enum int totalNeededBits = T.mant_dig + int(performRounding);
975         static if (totalNeededBits <= 64)
976         {
977             // We need to examine the top two 64-bit words, not just the top one,
978             // since the top word could have just a single significant bit.
979             const ulongLength = data.ulongLength;
980             const ulong w1 = data.peekUlong(ulongLength - 1);
981             if (w1 == 0)
982                 return T(0); // Special: exponent should be all zero bits, plus bsr(w1) is undefined.
983             const ulong w2 = ulongLength < 2 ? 0 : data.peekUlong(ulongLength - 2);
984             const uint w1BitCount = bsr(w1) + 1;
985             ulong sansExponent = (w1 << (64 - w1BitCount)) | (w2 >>> (w1BitCount));
986             size_t exponent = (ulongLength - 1) * 64 + w1BitCount + 1;
987             static if (performRounding)
988             {
989                 sansExponent += 1UL << (64 - totalNeededBits);
990                 if (0 <= cast(long) sansExponent) // Use high bit to detect overflow.
991                 {
992                     // Do not bother filling in the high bit of sansExponent
993                     // with 1. It will be discarded by float and double and 80
994                     // bit real cannot be on this path with rounding enabled.
995                     exponent += 1;
996                 }
997             }
998             static if (T.mant_dig == float.mant_dig)
999             {
1000                 if (exponent >= T.max_exp)
1001                     return isNegative ? -T.infinity : T.infinity;
1002                 uint resultBits = (uint(isNegative) << 31) | // sign bit
1003                     ((0xFF & (exponent - float.min_exp)) << 23) | // exponent
1004                     cast(uint) ((sansExponent << 1) >>> (64 - 23)); // mantissa.
1005                 // TODO: remove @trusted lambda after DIP 1000 is enabled by default.
1006                 return (() @trusted => *cast(float*) &resultBits)();
1007             }
1008             else static if (T.mant_dig == double.mant_dig)
1009             {
1010                 if (exponent >= T.max_exp)
1011                     return isNegative ? -T.infinity : T.infinity;
1012                 ulong resultBits = (ulong(isNegative) << 63) | // sign bit
1013                     ((0x7FFUL & (exponent - double.min_exp)) << 52) | // exponent
1014                     ((sansExponent << 1) >>> (64 - 52)); // mantissa.
1015                 // TODO: remove @trusted lambda after DIP 1000 is enabled by default.
1016                 return (() @trusted => *cast(double*) &resultBits)();
1017             }
1018             else
1019             {
1020                 import core.math : ldexp;
1021                 return ldexp(isNegative ? -cast(real) sansExponent : cast(real) sansExponent,
1022                     cast(int) exponent - 65);
1023             }
1024         }
1025         else
1026         {
1027             import core.math : ldexp;
1028             const ulongLength = data.ulongLength;
1029             if ((ulongLength - 1) * 64L > int.max)
1030                 return isNegative ? -T.infinity : T.infinity;
1031             int scale = cast(int) ((ulongLength - 1) * 64);
1032             const ulong w1 = data.peekUlong(ulongLength - 1);
1033             if (w1 == 0)
1034                 return T(0); // Special: bsr(w1) is undefined.
1035             int bitsStillNeeded = totalNeededBits - bsr(w1) - 1;
1036             T acc = ldexp(cast(T) w1, scale);
1037             for (ptrdiff_t i = ulongLength - 2; i >= 0 && bitsStillNeeded > 0; i--)
1038             {
1039                 ulong w = data.peekUlong(i);
1040                 // To round towards zero we must make sure not to use too many bits.
1041                 if (bitsStillNeeded >= 64)
1042                 {
1043                     acc += ldexp(cast(T) w, scale -= 64);
1044                     bitsStillNeeded -= 64;
1045                 }
1046                 else
1047                 {
1048                     w = (w >>> (64 - bitsStillNeeded)) << (64 - bitsStillNeeded);
1049                     acc += ldexp(cast(T) w, scale -= 64);
1050                     break;
1051                 }
1052             }
1053             if (isNegative)
1054                 acc = -acc;
1055             return cast(T) acc;
1056         }
1057     }
1058 
1059     /**
1060         Implements casting to/from qualified `BigInt`'s.
1061 
1062         Warning: Casting to/from `const` or `immutable` may break type
1063         system guarantees. Use with care.
1064      */
1065     T opCast(T)() pure nothrow @nogc const
1066     if (is(immutable T == immutable BigInt))
1067     {
1068         return this;
1069     }
1070 
1071     ///
1072     @safe unittest
1073     {
1074         const(BigInt) x = BigInt("123");
1075         BigInt y = cast() x;    // cast away const
1076         assert(y == x);
1077     }
1078 
1079     // Hack to make BigInt's typeinfo.compare work properly.
1080     // Note that this must appear before the other opCmp overloads, otherwise
1081     // DMD won't find it.
1082     /**
1083         Implements 3-way comparisons of `BigInt` with `BigInt` or `BigInt` with
1084         built-in numeric types.
1085      */
1086     int opCmp(ref const BigInt y) pure nothrow @nogc @safe const
1087     {
1088         // Simply redirect to the "real" opCmp implementation.
1089         return this.opCmp!BigInt(y);
1090     }
1091 
1092     /// ditto
1093     int opCmp(T)(const T y) pure nothrow @nogc @safe const if (isIntegral!T)
1094     {
1095         if (sign != (y<0) )
1096             return sign ? -1 : 1;
1097         int cmp = data.opCmp(cast(ulong) absUnsign(y));
1098         return sign? -cmp: cmp;
1099     }
1100     /// ditto
1101     int opCmp(T)(const T y) nothrow @nogc @safe const if (isFloatingPoint!T)
1102     {
1103         import core.bitop : bsr;
1104         import std.math.operations : cmp;
1105         import std.math.traits : isFinite;
1106 
1107         const asFloat = toFloat!(T, "truncate");
1108         if (asFloat != y)
1109             return cmp(asFloat, y); // handles +/- NaN.
1110         if (!isFinite(y))
1111             return isNegative ? 1 : -1;
1112         const ulongLength = data.ulongLength;
1113         const w1 = data.peekUlong(ulongLength - 1);
1114         if (w1 == 0)
1115             return 0; // Special: bsr(w1) is undefined.
1116         const numSignificantBits = (ulongLength - 1) * 64 + bsr(w1) + 1;
1117         for (ptrdiff_t bitsRemainingToCheck = numSignificantBits - T.mant_dig, i = 0;
1118             bitsRemainingToCheck > 0; i++, bitsRemainingToCheck -= 64)
1119         {
1120             auto word = data.peekUlong(i);
1121             if (word == 0)
1122                 continue;
1123             // Make sure we're only checking digits that are beyond
1124             // the precision of `y`.
1125             if (bitsRemainingToCheck < 64 && (word << (64 - bitsRemainingToCheck)) == 0)
1126                 break; // This can only happen on the last loop iteration.
1127             return isNegative ? -1 : 1;
1128         }
1129         return 0;
1130     }
1131     /// ditto
1132     int opCmp(T:BigInt)(const T y) pure nothrow @nogc @safe const
1133     {
1134         if (sign != y.sign)
1135             return sign ? -1 : 1;
1136         immutable cmp = data.opCmp(y.data);
1137         return sign? -cmp: cmp;
1138     }
1139 
1140     ///
1141     @safe unittest
1142     {
1143         auto x = BigInt("100");
1144         auto y = BigInt("10");
1145         int z = 50;
1146         const int w = 200;
1147 
1148         assert(y < x);
1149         assert(x > z);
1150         assert(z > y);
1151         assert(x < w);
1152     }
1153 
1154     ///
1155     @safe unittest
1156     {
1157         auto x = BigInt("0x1abc_de80_0000_0000_0000_0000_0000_0000");
1158         BigInt y = x - 1;
1159         BigInt z = x + 1;
1160 
1161         double d = 0x1.abcde8p124;
1162         assert(y < d);
1163         assert(z > d);
1164         assert(x >= d && x <= d);
1165 
1166         // Note that when comparing a BigInt to a float or double the
1167         // full precision of the BigInt is always considered, unlike
1168         // when comparing an int to a float or a long to a double.
1169         assert(BigInt(123456789) < cast(float) 123456789);
1170     }
1171 
1172     @safe unittest
1173     {
1174         assert(BigInt("999_999_999_999_999_999_999_999_999_999_999_999_999") < float.infinity);
1175 
1176         // Test `real` works.
1177         auto x = BigInt("0x1abc_de80_0000_0000_0000_0000_0000_0000");
1178         BigInt y = x - 1;
1179         BigInt z = x + 1;
1180 
1181         real d = 0x1.abcde8p124;
1182         assert(y < d);
1183         assert(z > d);
1184         assert(x >= d && x <= d);
1185 
1186         // Test comparison for numbers of 64 bits or fewer.
1187         auto w1 = BigInt(0x1abc_de80_0000_0000);
1188         auto w2 = w1 - 1;
1189         auto w3 = w1 + 1;
1190         assert(w1.ulongLength == 1);
1191         assert(w2.ulongLength == 1);
1192         assert(w3.ulongLength == 1);
1193 
1194         double e = 0x1.abcde8p+60;
1195         assert(w1 >= e && w1 <= e);
1196         assert(w2 < e);
1197         assert(w3 > e);
1198 
1199         real eL = 0x1.abcde8p+60;
1200         assert(w1 >= eL && w1 <= eL);
1201         assert(w2 < eL);
1202         assert(w3 > eL);
1203     }
1204 
1205     /**
1206         Returns: The value of this `BigInt` as a `long`, or `long.max`/`long.min`
1207         if outside the representable range.
1208      */
1209     long toLong() @safe pure nothrow const @nogc
1210     {
1211         return (sign ? -1 : 1) *
1212           (data.ulongLength == 1  && (data.peekUlong(0) <= sign+cast(ulong)(long.max)) // 1+long.max = |long.min|
1213           ? cast(long)(data.peekUlong(0))
1214           : long.max);
1215     }
1216 
1217     ///
1218     @safe unittest
1219     {
1220         auto b = BigInt("12345");
1221         long l = b.toLong();
1222         assert(l == 12345);
1223     }
1224 
1225     /**
1226         Returns: The value of this `BigInt` as an `int`, or `int.max`/`int.min` if outside
1227         the representable range.
1228      */
1229     int toInt() @safe pure nothrow @nogc const
1230     {
1231         return (sign ? -1 : 1) *
1232           (data.uintLength == 1  && (data.peekUint(0) <= sign+cast(uint)(int.max)) // 1+int.max = |int.min|
1233           ? cast(int)(data.peekUint(0))
1234           : int.max);
1235     }
1236 
1237     ///
1238     @safe unittest
1239     {
1240         auto big = BigInt("5_000_000");
1241         auto i = big.toInt();
1242         assert(i == 5_000_000);
1243 
1244         // Numbers that are too big to fit into an int will be clamped to int.max.
1245         auto tooBig = BigInt("5_000_000_000");
1246         i = tooBig.toInt();
1247         assert(i == int.max);
1248     }
1249 
1250     /// Number of significant `uint`s which are used in storing this number.
1251     /// The absolute value of this `BigInt` is always &lt; 2$(SUPERSCRIPT 32*uintLength)
1252     @property size_t uintLength() @safe pure nothrow @nogc const
1253     {
1254         return data.uintLength;
1255     }
1256 
1257     /// Number of significant `ulong`s which are used in storing this number.
1258     /// The absolute value of this `BigInt` is always &lt; 2$(SUPERSCRIPT 64*ulongLength)
1259     @property size_t ulongLength() @safe pure nothrow @nogc const
1260     {
1261         return data.ulongLength;
1262     }
1263 
1264     /** Convert the `BigInt` to `string`, passing it to the given sink.
1265      *
1266      * Params:
1267      *  sink = An OutputRange for accepting possibly piecewise segments of the
1268      *      formatted string.
1269      *  formatString = A format string specifying the output format.
1270      *
1271      * $(TABLE  Available output formats:,
1272      * $(TR $(TD "d") $(TD  Decimal))
1273      * $(TR $(TD "o") $(TD  Octal))
1274      * $(TR $(TD "x") $(TD  Hexadecimal, lower case))
1275      * $(TR $(TD "X") $(TD  Hexadecimal, upper case))
1276      * $(TR $(TD "s") $(TD  Default formatting (same as "d") ))
1277      * $(TR $(TD null) $(TD Default formatting (same as "d") ))
1278      * )
1279      */
1280     void toString(Writer)(scope ref Writer sink, string formatString) const
1281     {
1282         auto f = FormatSpec!char(formatString);
1283         f.writeUpToNextSpec(sink);
1284         toString!Writer(sink, f);
1285     }
1286 
1287     /// ditto
1288     void toString(Writer)(scope ref Writer sink, scope const ref FormatSpec!char f) const
1289     {
1290         import std.range.primitives : put;
1291         const spec = f.spec;
1292         immutable hex = (spec == 'x' || spec == 'X');
1293         if (!(spec == 's' || spec == 'd' || spec =='o' || hex))
1294             throw new FormatException("Format specifier not understood: %" ~ spec);
1295 
1296         char[] buff;
1297         if (spec == 'X')
1298         {
1299             buff = data.toHexString(0, '_', 0, f.flZero ? '0' : ' ', LetterCase.upper);
1300         }
1301         else if (spec == 'x')
1302         {
1303             buff = data.toHexString(0, '_', 0, f.flZero ? '0' : ' ', LetterCase.lower);
1304         }
1305         else if (spec == 'o')
1306         {
1307             buff = data.toOctalString();
1308         }
1309         else
1310         {
1311             buff = data.toDecimalString(0);
1312         }
1313         assert(buff.length > 0, "Invalid buffer length");
1314 
1315         char signChar = isNegative ? '-' : 0;
1316         auto minw = buff.length + (signChar ? 1 : 0);
1317 
1318         if (!hex && !signChar && (f.width == 0 || minw < f.width))
1319         {
1320             if (f.flPlus)
1321             {
1322                 signChar = '+';
1323                 ++minw;
1324             }
1325             else if (f.flSpace)
1326             {
1327                 signChar = ' ';
1328                 ++minw;
1329             }
1330         }
1331 
1332         immutable maxw = minw < f.width ? f.width : minw;
1333         immutable difw = maxw - minw;
1334 
1335         if (!f.flDash && !f.flZero)
1336             foreach (i; 0 .. difw)
1337                 put(sink, " ");
1338 
1339         if (signChar)
1340         {
1341             scope char[1] buf = signChar;
1342             put(sink, buf[]);
1343         }
1344 
1345         if (!f.flDash && f.flZero)
1346             foreach (i; 0 .. difw)
1347                 put(sink, "0");
1348 
1349         put(sink, buff);
1350 
1351         if (f.flDash)
1352             foreach (i; 0 .. difw)
1353                 put(sink, " ");
1354     }
1355 
1356     /**
1357         `toString` is rarely directly invoked; the usual way of using it is via
1358         $(REF format, std, format):
1359      */
1360     @safe unittest
1361     {
1362         import std.format : format;
1363 
1364         auto x = BigInt("1_000_000");
1365         x *= 12345;
1366 
1367         assert(format("%d", x) == "12345000000");
1368         assert(format("%x", x) == "2_dfd1c040");
1369         assert(format("%X", x) == "2_DFD1C040");
1370         assert(format("%o", x) == "133764340100");
1371     }
1372 
1373     // for backwards compatibility, see unittest below
1374     /// ditto
1375     void toString(scope void delegate(scope const(char)[]) sink, string formatString) const
1376     {
1377         toString!(void delegate(scope const(char)[]))(sink, formatString);
1378     }
1379 
1380     // for backwards compatibility, see unittest below
1381     /// ditto
1382     void toString(scope void delegate(scope const(char)[]) sink, scope const ref FormatSpec!char f) const
1383     {
1384         toString!(void delegate(scope const(char)[]))(sink, f);
1385     }
1386 
1387     // Backwards compatibility test
1388     // BigInt.toString used to only accept a delegate sink function, but this does not work
1389     // well with attributes such as @safe. A template function toString was added that
1390     // works on OutputRanges, but when a delegate was passed in the form of an untyped
1391     // lambda such as `str => dst.put(str)` the parameter type was inferred as `void` and
1392     // the function failed to instantiate.
1393     @system unittest
1394     {
1395         import std.format.spec : FormatSpec;
1396         import std.array : appender;
1397         BigInt num = 503;
1398         auto dst = appender!string();
1399         num.toString(str => dst.put(str), null);
1400         assert(dst[] == "503");
1401         num = 504;
1402         auto f = FormatSpec!char("");
1403         num.toString(str => dst.put(str), f);
1404         assert(dst[] == "503504");
1405     }
1406 
1407     // Implement toHash so that BigInt works properly as an AA key.
1408     /**
1409         Returns: A unique hash of the `BigInt`'s value suitable for use in a hash
1410         table.
1411      */
1412     size_t toHash() const @safe pure nothrow @nogc
1413     {
1414         return data.toHash() + sign;
1415     }
1416 
1417     /**
1418         `toHash` is rarely directly invoked; it is implicitly used when
1419         BigInt is used as the key of an associative array.
1420      */
1421     @safe pure unittest
1422     {
1423         string[BigInt] aa;
1424         aa[BigInt(123)] = "abc";
1425         aa[BigInt(456)] = "def";
1426 
1427         assert(aa[BigInt(123)] == "abc");
1428         assert(aa[BigInt(456)] == "def");
1429     }
1430 
1431     /**
1432      * Gets the nth number in the underlying representation that makes up the whole
1433      * `BigInt`.
1434      *
1435      * Params:
1436      *     T = the type to view the underlying representation as
1437      *     n = The nth number to retrieve. Must be less than $(LREF ulongLength) or
1438      *     $(LREF uintLength) with respect to `T`.
1439      * Returns:
1440      *     The nth `ulong` in the representation of this `BigInt`.
1441      */
1442     T getDigit(T = ulong)(size_t n) const
1443     if (is(T == ulong) || is(T == uint))
1444     {
1445         static if (is(T == ulong))
1446         {
1447             assert(n < ulongLength(), "getDigit index out of bounds");
1448             return data.peekUlong(n);
1449         }
1450         else
1451         {
1452             assert(n < uintLength(), "getDigit index out of bounds");
1453             return data.peekUint(n);
1454         }
1455     }
1456 
1457     ///
1458     @safe pure unittest
1459     {
1460         auto a = BigInt("1000");
1461         assert(a.ulongLength() == 1);
1462         assert(a.getDigit(0) == 1000);
1463 
1464         assert(a.uintLength() == 1);
1465         assert(a.getDigit!uint(0) == 1000);
1466 
1467         auto b = BigInt("2_000_000_000_000_000_000_000_000_000");
1468         assert(b.ulongLength() == 2);
1469         assert(b.getDigit(0) == 4584946418820579328);
1470         assert(b.getDigit(1) == 108420217);
1471 
1472         assert(b.uintLength() == 3);
1473         assert(b.getDigit!uint(0) == 3489660928);
1474         assert(b.getDigit!uint(1) == 1067516025);
1475         assert(b.getDigit!uint(2) == 108420217);
1476     }
1477 
1478 private:
1479     void negate() @safe pure nothrow @nogc scope
1480     {
1481         if (!data.isZero())
1482             sign = !sign;
1483     }
1484     bool isZero() pure const nothrow @nogc @safe scope
1485     {
1486         return data.isZero();
1487     }
1488     alias isNegative = sign;
1489 
1490     // Generate a runtime error if division by zero occurs
1491     void checkDivByZero() pure const nothrow @safe scope
1492     {
1493         assert(!isZero(), "BigInt division by zero");
1494     }
1495 }
1496 
1497 ///
1498 @safe unittest
1499 {
1500     BigInt a = "9588669891916142";
1501     BigInt b = "7452469135154800";
1502     auto c = a * b;
1503     assert(c == BigInt("71459266416693160362545788781600"));
1504     auto d = b * a;
1505     assert(d == BigInt("71459266416693160362545788781600"));
1506     assert(d == c);
1507     d = c * BigInt("794628672112");
1508     assert(d == BigInt("56783581982794522489042432639320434378739200"));
1509     auto e = c + d;
1510     assert(e == BigInt("56783581982865981755459125799682980167520800"));
1511     auto f = d + c;
1512     assert(f == e);
1513     auto g = f - c;
1514     assert(g == d);
1515     g = f - d;
1516     assert(g == c);
1517     e = 12345678;
1518     g = c + e;
1519     auto h = g / b;
1520     auto i = g % b;
1521     assert(h == a);
1522     assert(i == e);
1523     BigInt j = "-0x9A56_57f4_7B83_AB78";
1524     BigInt k = j;
1525     j ^^= 11;
1526     assert(k ^^ 11 == j);
1527 }
1528 
1529 /**
1530 Params:
1531     x = The `BigInt` to convert to a decimal `string`.
1532 
1533 Returns:
1534     A `string` that represents the `BigInt` as a decimal number.
1535 
1536 */
1537 string toDecimalString(const(BigInt) x) pure nothrow @safe
1538 {
1539     auto buff = x.data.toDecimalString(x.isNegative ? 1 : 0);
1540     if (x.isNegative)
1541         buff[0] = '-';
1542     return buff;
1543 }
1544 
1545 ///
1546 @safe pure unittest
1547 {
1548     auto x = BigInt("123");
1549     x *= 1000;
1550     x += 456;
1551 
1552     auto xstr = x.toDecimalString();
1553     assert(xstr == "123456");
1554 }
1555 
1556 /**
1557 Params:
1558     x = The `BigInt` to convert to a hexadecimal `string`.
1559 
1560 Returns:
1561     A `string` that represents the `BigInt` as a hexadecimal (base 16)
1562     number in upper case.
1563 
1564 */
1565 string toHex(const(BigInt) x) pure @safe
1566 {
1567     import std.array : appender;
1568     auto outbuff = appender!string();
1569     x.toString(outbuff, "%X");
1570     return outbuff[];
1571 }
1572 
1573 ///
1574 @safe unittest
1575 {
1576     auto x = BigInt("123");
1577     x *= 1000;
1578     x += 456;
1579 
1580     auto xstr = x.toHex();
1581     assert(xstr == "1E240");
1582 }
1583 
1584 /** Returns the absolute value of x converted to the corresponding unsigned
1585 type.
1586 
1587 Params:
1588     x = The integral value to return the absolute value of.
1589 
1590 Returns:
1591     The absolute value of x.
1592 
1593 */
1594 Unsigned!T absUnsign(T)(T x)
1595 if (isIntegral!T)
1596 {
1597     static if (isSigned!T)
1598     {
1599         import std.conv : unsigned;
1600         /* This returns the correct result even when x = T.min
1601          * on two's complement machines because unsigned(T.min) = |T.min|
1602          * even though -T.min = T.min.
1603          */
1604         return unsigned((x < 0) ? cast(T)(0-x) : x);
1605     }
1606     else
1607     {
1608         return x;
1609     }
1610 }
1611 
1612 ///
1613 nothrow pure @safe
1614 unittest
1615 {
1616     assert((-1).absUnsign == 1);
1617     assert(1.absUnsign == 1);
1618 }
1619 
1620 nothrow pure @safe
1621 unittest
1622 {
1623     BigInt a, b;
1624     a = 1;
1625     b = 2;
1626     auto c = a + b;
1627     assert(c == 3);
1628 }
1629 
1630 nothrow pure @safe
1631 unittest
1632 {
1633     long a;
1634     BigInt b;
1635     auto c = a + b;
1636     assert(c == 0);
1637     auto d = b + a;
1638     assert(d == 0);
1639 }
1640 
1641 nothrow pure @safe
1642 unittest
1643 {
1644     BigInt x = 1, y = 2;
1645     assert(x <  y);
1646     assert(x <= y);
1647     assert(y >= x);
1648     assert(y >  x);
1649     assert(x != y);
1650 
1651     long r1 = x.toLong;
1652     assert(r1 == 1);
1653 
1654     BigInt r2 = 10 % x;
1655     assert(r2 == 0);
1656 
1657     BigInt r3 = 10 / y;
1658     assert(r3 == 5);
1659 
1660     BigInt[] arr = [BigInt(1)];
1661     auto incr = arr[0]++;
1662     assert(arr == [BigInt(2)]);
1663     assert(incr == BigInt(1));
1664 }
1665 
1666 @safe unittest
1667 {
1668     // Radix conversion
1669     assert( toDecimalString(BigInt("-1_234_567_890_123_456_789"))
1670         == "-1234567890123456789");
1671     assert( toHex(BigInt("0x1234567890123456789")) == "123_45678901_23456789");
1672     assert( toHex(BigInt("0x00000000000000000000000000000000000A234567890123456789"))
1673         == "A23_45678901_23456789");
1674     assert( toHex(BigInt("0x000_00_000000_000_000_000000000000_000000_")) == "0");
1675 
1676     assert(BigInt(-0x12345678).toInt() == -0x12345678);
1677     assert(BigInt(-0x12345678).toLong() == -0x12345678);
1678     assert(BigInt(0x1234_5678_9ABC_5A5AL).ulongLength == 1);
1679     assert(BigInt(0x1234_5678_9ABC_5A5AL).toLong() == 0x1234_5678_9ABC_5A5AL);
1680     assert(BigInt(-0x1234_5678_9ABC_5A5AL).toLong() == -0x1234_5678_9ABC_5A5AL);
1681     assert(BigInt(0xF234_5678_9ABC_5A5AL).toLong() == long.max);
1682     assert(BigInt(-0x123456789ABCL).toInt() == -int.max);
1683     char[] s1 = "123".dup; // https://issues.dlang.org/show_bug.cgi?id=8164
1684     assert(BigInt(s1) == 123);
1685     char[] s2 = "0xABC".dup;
1686     assert(BigInt(s2) == 2748);
1687 
1688     assert((BigInt(-2) + BigInt(1)) == BigInt(-1));
1689     BigInt a = ulong.max - 5;
1690     auto b = -long.max % a;
1691     assert( b == -long.max % (ulong.max - 5));
1692     b = long.max / a;
1693     assert( b == long.max /(ulong.max - 5));
1694     assert(BigInt(1) - 1 == 0);
1695     assert((-4) % BigInt(5) == -4); // https://issues.dlang.org/show_bug.cgi?id=5928
1696     assert(BigInt(-4) % BigInt(5) == -4);
1697     assert(BigInt(2)/BigInt(-3) == BigInt(0)); // https://issues.dlang.org/show_bug.cgi?id=8022
1698     assert(BigInt("-1") > long.min); // https://issues.dlang.org/show_bug.cgi?id=9548
1699 
1700     assert(toDecimalString(BigInt("0000000000000000000000000000000000000000001234567"))
1701         == "1234567");
1702 }
1703 
1704 @safe unittest // Minimum signed value bug tests.
1705 {
1706     assert(BigInt("-0x8000000000000000") == BigInt(long.min));
1707     assert(BigInt("-0x8000000000000000")+1 > BigInt(long.min));
1708     assert(BigInt("-0x80000000") == BigInt(int.min));
1709     assert(BigInt("-0x80000000")+1 > BigInt(int.min));
1710     assert(BigInt(long.min).toLong() == long.min); // lossy toLong bug for long.min
1711     assert(BigInt(int.min).toInt() == int.min); // lossy toInt bug for int.min
1712     assert(BigInt(long.min).ulongLength == 1);
1713     assert(BigInt(int.min).uintLength == 1); // cast/sign extend bug in opAssign
1714     BigInt a;
1715     a += int.min;
1716     assert(a == BigInt(int.min));
1717     a = int.min - BigInt(int.min);
1718     assert(a == 0);
1719     a = int.min;
1720     assert(a == BigInt(int.min));
1721     assert(int.min % (BigInt(int.min)-1) == int.min);
1722     assert((BigInt(int.min)-1)%int.min == -1);
1723 }
1724 
1725  // Recursive division (https://issues.dlang.org/show_bug.cgi?id=5568)
1726 @safe unittest
1727 {
1728     enum Z = 4843;
1729     BigInt m = (BigInt(1) << (Z*8) ) - 1;
1730     m -= (BigInt(1) << (Z*6)) - 1;
1731     BigInt oldm = m;
1732 
1733     BigInt a = (BigInt(1) << (Z*4) )-1;
1734     BigInt b = m % a;
1735     m /= a;
1736     m *= a;
1737     assert( m + b == oldm);
1738 
1739     m = (BigInt(1) << (4846 + 4843) ) - 1;
1740     a = (BigInt(1) << 4846 ) - 1;
1741     b = (BigInt(1) << (4846*2 + 4843)) - 1;
1742     BigInt c = (BigInt(1) << (4846*2 + 4843*2)) - 1;
1743     BigInt w =  c - b + a;
1744     assert(w % m == 0);
1745 
1746     // https://issues.dlang.org/show_bug.cgi?id=6819
1747     BigInt z1 = BigInt(10)^^64;
1748     BigInt w1 = BigInt(10)^^128;
1749     assert(z1^^2 == w1);
1750     BigInt z2 = BigInt(1)<<64;
1751     BigInt w2 = BigInt(1)<<128;
1752     assert(z2^^2 == w2);
1753     // https://issues.dlang.org/show_bug.cgi?id=7993
1754     BigInt n7793 = 10;
1755     assert( n7793 / 1 == 10);
1756     // https://issues.dlang.org/show_bug.cgi?id=7973
1757     auto a7973 = 10_000_000_000_000_000;
1758     const c7973 = 10_000_000_000_000_000;
1759     immutable i7973 = 10_000_000_000_000_000;
1760     BigInt v7973 = 2551700137;
1761     v7973 %= a7973;
1762     assert(v7973 == 2551700137);
1763     v7973 %= c7973;
1764     assert(v7973 == 2551700137);
1765     v7973 %= i7973;
1766     assert(v7973 == 2551700137);
1767     // https://issues.dlang.org/show_bug.cgi?id=8165
1768     BigInt[2] a8165;
1769     a8165[0] = a8165[1] = 1;
1770 }
1771 
1772 @safe unittest
1773 {
1774     import std.array;
1775     import std.format.write : formattedWrite;
1776 
1777     immutable string[][] table = [
1778     /*  fmt,        +10     -10 */
1779         ["%d",      "10",   "-10"],
1780         ["%+d",     "+10",  "-10"],
1781         ["%-d",     "10",   "-10"],
1782         ["%+-d",    "+10",  "-10"],
1783 
1784         ["%4d",     "  10", " -10"],
1785         ["%+4d",    " +10", " -10"],
1786         ["%-4d",    "10  ", "-10 "],
1787         ["%+-4d",   "+10 ", "-10 "],
1788 
1789         ["%04d",    "0010", "-010"],
1790         ["%+04d",   "+010", "-010"],
1791         ["%-04d",   "10  ", "-10 "],
1792         ["%+-04d",  "+10 ", "-10 "],
1793 
1794         ["% 04d",   " 010", "-010"],
1795         ["%+ 04d",  "+010", "-010"],
1796         ["%- 04d",  " 10 ", "-10 "],
1797         ["%+- 04d", "+10 ", "-10 "],
1798     ];
1799 
1800     auto w1 = appender!(char[])();
1801     auto w2 = appender!(char[])();
1802 
1803     foreach (entry; table)
1804     {
1805         immutable fmt = entry[0];
1806 
1807         formattedWrite(w1, fmt, BigInt(10));
1808         formattedWrite(w2, fmt, 10);
1809         assert(w1.data == w2.data);
1810         assert(w1.data == entry[1]);
1811         w1.clear();
1812         w2.clear();
1813 
1814         formattedWrite(w1, fmt, BigInt(-10));
1815         formattedWrite(w2, fmt, -10);
1816         assert(w1.data == w2.data);
1817         assert(w1.data == entry[2]);
1818         w1.clear();
1819         w2.clear();
1820     }
1821 }
1822 
1823 @safe unittest
1824 {
1825     import std.array;
1826     import std.format.write : formattedWrite;
1827 
1828     immutable string[][] table = [
1829     /*  fmt,        +10     -10 */
1830         ["%x",      "a",    "-a"],
1831         ["%+x",     "a",    "-a"],
1832         ["%-x",     "a",    "-a"],
1833         ["%+-x",    "a",    "-a"],
1834 
1835         ["%4x",     "   a", "  -a"],
1836         ["%+4x",    "   a", "  -a"],
1837         ["%-4x",    "a   ", "-a  "],
1838         ["%+-4x",   "a   ", "-a  "],
1839 
1840         ["%04x",    "000a", "-00a"],
1841         ["%+04x",   "000a", "-00a"],
1842         ["%-04x",   "a   ", "-a  "],
1843         ["%+-04x",  "a   ", "-a  "],
1844 
1845         ["% 04x",   "000a", "-00a"],
1846         ["%+ 04x",  "000a", "-00a"],
1847         ["%- 04x",  "a   ", "-a  "],
1848         ["%+- 04x", "a   ", "-a  "],
1849     ];
1850 
1851     auto w1 = appender!(char[])();
1852     auto w2 = appender!(char[])();
1853 
1854     foreach (entry; table)
1855     {
1856         immutable fmt = entry[0];
1857 
1858         formattedWrite(w1, fmt, BigInt(10));
1859         formattedWrite(w2, fmt, 10);
1860         assert(w1.data == w2.data);     // Equal only positive BigInt
1861         assert(w1.data == entry[1]);
1862         w1.clear();
1863         w2.clear();
1864 
1865         formattedWrite(w1, fmt, BigInt(-10));
1866         //formattedWrite(w2, fmt, -10);
1867         //assert(w1.data == w2.data);
1868         assert(w1.data == entry[2]);
1869         w1.clear();
1870         //w2.clear();
1871     }
1872 }
1873 
1874 @safe unittest
1875 {
1876     import std.array;
1877     import std.format.write : formattedWrite;
1878 
1879     immutable string[][] table = [
1880     /*  fmt,        +10     -10 */
1881         ["%X",      "A",    "-A"],
1882         ["%+X",     "A",    "-A"],
1883         ["%-X",     "A",    "-A"],
1884         ["%+-X",    "A",    "-A"],
1885 
1886         ["%4X",     "   A", "  -A"],
1887         ["%+4X",    "   A", "  -A"],
1888         ["%-4X",    "A   ", "-A  "],
1889         ["%+-4X",   "A   ", "-A  "],
1890 
1891         ["%04X",    "000A", "-00A"],
1892         ["%+04X",   "000A", "-00A"],
1893         ["%-04X",   "A   ", "-A  "],
1894         ["%+-04X",  "A   ", "-A  "],
1895 
1896         ["% 04X",   "000A", "-00A"],
1897         ["%+ 04X",  "000A", "-00A"],
1898         ["%- 04X",  "A   ", "-A  "],
1899         ["%+- 04X", "A   ", "-A  "],
1900     ];
1901 
1902     auto w1 = appender!(char[])();
1903     auto w2 = appender!(char[])();
1904 
1905     foreach (entry; table)
1906     {
1907         immutable fmt = entry[0];
1908 
1909         formattedWrite(w1, fmt, BigInt(10));
1910         formattedWrite(w2, fmt, 10);
1911         assert(w1.data == w2.data);     // Equal only positive BigInt
1912         assert(w1.data == entry[1]);
1913         w1.clear();
1914         w2.clear();
1915 
1916         formattedWrite(w1, fmt, BigInt(-10));
1917         //formattedWrite(w2, fmt, -10);
1918         //assert(w1.data == w2.data);
1919         assert(w1.data == entry[2]);
1920         w1.clear();
1921         //w2.clear();
1922     }
1923 }
1924 
1925 // https://issues.dlang.org/show_bug.cgi?id=6448
1926 @safe unittest
1927 {
1928     import std.array;
1929     import std.format.write : formattedWrite;
1930 
1931     auto w1 = appender!string();
1932     auto w2 = appender!string();
1933 
1934     int x = 100;
1935     formattedWrite(w1, "%010d", x);
1936     BigInt bx = x;
1937     formattedWrite(w2, "%010d", bx);
1938     assert(w1.data == w2.data);
1939     // https://issues.dlang.org/show_bug.cgi?id=8011
1940     BigInt y = -3;
1941     ++y;
1942     assert(y.toLong() == -2);
1943     y = 1;
1944     --y;
1945     assert(y.toLong() == 0);
1946     --y;
1947     assert(y.toLong() == -1);
1948     --y;
1949     assert(y.toLong() == -2);
1950 }
1951 
1952 @safe unittest
1953 {
1954     import std.math.algebraic : abs;
1955     auto r = abs(BigInt(-1000)); // https://issues.dlang.org/show_bug.cgi?id=6486
1956     assert(r == 1000);
1957 
1958     auto r2 = abs(const(BigInt)(-500)); // https://issues.dlang.org/show_bug.cgi?id=11188
1959     assert(r2 == 500);
1960     auto r3 = abs(immutable(BigInt)(-733)); // https://issues.dlang.org/show_bug.cgi?id=11188
1961     assert(r3 == 733);
1962 
1963     // opCast!bool
1964     BigInt one = 1, zero;
1965     assert(one && !zero);
1966 }
1967 
1968 // https://issues.dlang.org/show_bug.cgi?id=6850
1969 @safe unittest
1970 {
1971     pure long pureTest() {
1972         BigInt a = 1;
1973         BigInt b = 1336;
1974         a += b;
1975         return a.toLong();
1976     }
1977 
1978     assert(pureTest() == 1337);
1979 }
1980 
1981 // https://issues.dlang.org/show_bug.cgi?id=8435
1982 // https://issues.dlang.org/show_bug.cgi?id=10118
1983 @safe unittest
1984 {
1985     auto i = BigInt(100);
1986     auto j = BigInt(100);
1987 
1988     // Two separate BigInt instances representing same value should have same
1989     // hash.
1990     assert(typeid(i).getHash(&i) == typeid(j).getHash(&j));
1991     assert(typeid(i).compare(&i, &j) == 0);
1992 
1993     // BigInt AA keys should behave consistently.
1994     int[BigInt] aa;
1995     aa[BigInt(123)] = 123;
1996     assert(BigInt(123) in aa);
1997 
1998     aa[BigInt(123)] = 321;
1999     assert(aa[BigInt(123)] == 321);
2000 
2001     auto keys = aa.byKey;
2002     assert(keys.front == BigInt(123));
2003     keys.popFront();
2004     assert(keys.empty);
2005 }
2006 
2007 // https://issues.dlang.org/show_bug.cgi?id=11148
2008 @safe unittest
2009 {
2010     void foo(BigInt) {}
2011     const BigInt cbi = 3;
2012     immutable BigInt ibi = 3;
2013 
2014     foo(cbi);
2015     foo(ibi);
2016 
2017     import std.conv : to;
2018     import std.meta : AliasSeq;
2019 
2020     static foreach (T1; AliasSeq!(BigInt, const(BigInt), immutable(BigInt)))
2021     {
2022         static foreach (T2; AliasSeq!(BigInt, const(BigInt), immutable(BigInt)))
2023         {{
2024             T1 t1 = 2;
2025             T2 t2 = t1;
2026 
2027             T2 t2_1 = to!T2(t1);
2028             T2 t2_2 = cast(T2) t1;
2029 
2030             assert(t2 == t1);
2031             assert(t2 == 2);
2032 
2033             assert(t2_1 == t1);
2034             assert(t2_1 == 2);
2035 
2036             assert(t2_2 == t1);
2037             assert(t2_2 == 2);
2038         }}
2039     }
2040 
2041     BigInt n = 2;
2042     n *= 2;
2043     assert(n == 4);
2044 }
2045 
2046 // https://issues.dlang.org/show_bug.cgi?id=8167
2047 @safe unittest
2048 {
2049     BigInt a = BigInt(3);
2050     BigInt b = BigInt(a);
2051     assert(b == 3);
2052 }
2053 
2054 // https://issues.dlang.org/show_bug.cgi?id=9061
2055 @safe unittest
2056 {
2057     long l1 = 0x12345678_90ABCDEF;
2058     long l2 = 0xFEDCBA09_87654321;
2059     long l3 = l1 | l2;
2060     long l4 = l1 & l2;
2061     long l5 = l1 ^ l2;
2062 
2063     BigInt b1 = l1;
2064     BigInt b2 = l2;
2065     BigInt b3 = b1 | b2;
2066     BigInt b4 = b1 & b2;
2067     BigInt b5 = b1 ^ b2;
2068 
2069     assert(l3 == b3);
2070     assert(l4 == b4);
2071     assert(l5 == b5);
2072 }
2073 
2074 // https://issues.dlang.org/show_bug.cgi?id=11600
2075 @safe unittest
2076 {
2077     import std.conv;
2078     import std.exception : assertThrown;
2079 
2080     // Original bug report
2081     assertThrown!ConvException(to!BigInt("avadakedavra"));
2082 
2083     // Digit string lookalikes that are actually invalid
2084     assertThrown!ConvException(to!BigInt("0123hellothere"));
2085     assertThrown!ConvException(to!BigInt("-hihomarylowe"));
2086     assertThrown!ConvException(to!BigInt("__reallynow__"));
2087     assertThrown!ConvException(to!BigInt("-123four"));
2088 }
2089 
2090 // https://issues.dlang.org/show_bug.cgi?id=11583
2091 @safe unittest
2092 {
2093     BigInt x = 0;
2094     assert((x > 0) == false);
2095 }
2096 
2097 // https://issues.dlang.org/show_bug.cgi?id=13391
2098 @safe unittest
2099 {
2100     BigInt x1 = "123456789";
2101     BigInt x2 = "123456789123456789";
2102     BigInt x3 = "123456789123456789123456789";
2103 
2104     import std.meta : AliasSeq;
2105     static foreach (T; AliasSeq!(byte, ubyte, short, ushort, int, uint, long, ulong))
2106     {
2107         assert((x1 * T.max) / T.max == x1);
2108         assert((x2 * T.max) / T.max == x2);
2109         assert((x3 * T.max) / T.max == x3);
2110     }
2111 
2112     assert(x1 / -123456789 == -1);
2113     assert(x1 / 123456789U == 1);
2114     assert(x1 / -123456789L == -1);
2115     assert(x1 / 123456789UL == 1);
2116     assert(x2 / -123456789123456789L == -1);
2117     assert(x2 / 123456789123456789UL == 1);
2118 
2119     assert(x1 / uint.max == 0);
2120     assert(x1 / ulong.max == 0);
2121     assert(x2 / ulong.max == 0);
2122 
2123     x1 /= 123456789UL;
2124     assert(x1 == 1);
2125     x2 /= 123456789123456789UL;
2126     assert(x2 == 1);
2127 }
2128 
2129 // https://issues.dlang.org/show_bug.cgi?id=13963
2130 @safe unittest
2131 {
2132     BigInt x = 1;
2133     import std.meta : AliasSeq;
2134     static foreach (Int; AliasSeq!(byte, ubyte, short, ushort, int))
2135     {
2136         assert(is(typeof(x % Int(1)) == int));
2137     }
2138     assert(is(typeof(x % 1U) == long));
2139     assert(is(typeof(x % 1L) == long));
2140     assert(is(typeof(x % 1UL) == BigInt));
2141 
2142     auto x0 = BigInt(uint.max - 1);
2143     auto x1 = BigInt(8);
2144     assert(x1 / x == x1);
2145     auto x2 = -BigInt(long.min) + 1;
2146 
2147     // uint
2148     assert( x0 % uint.max ==  x0 % BigInt(uint.max));
2149     assert(-x0 % uint.max == -x0 % BigInt(uint.max));
2150     assert( x0 % uint.max ==  long(uint.max - 1));
2151     assert(-x0 % uint.max == -long(uint.max - 1));
2152 
2153     // long
2154     assert(x1 % 2L == 0L);
2155     assert(-x1 % 2L == 0L);
2156 
2157     assert(x1 % 3L == 2L);
2158     assert(x1 % -3L == 2L);
2159     assert(-x1 % 3L == -2L);
2160     assert(-x1 % -3L == -2L);
2161 
2162     assert(x1 % 11L == 8L);
2163     assert(x1 % -11L == 8L);
2164     assert(-x1 % 11L == -8L);
2165     assert(-x1 % -11L == -8L);
2166 
2167     // ulong
2168     assert(x1 % 2UL == BigInt(0));
2169     assert(-x1 % 2UL == BigInt(0));
2170 
2171     assert(x1 % 3UL == BigInt(2));
2172     assert(-x1 % 3UL == -BigInt(2));
2173 
2174     assert(x1 % 11UL == BigInt(8));
2175     assert(-x1 % 11UL == -BigInt(8));
2176 
2177     assert(x2 % ulong.max == x2);
2178     assert(-x2 % ulong.max == -x2);
2179 }
2180 
2181 // https://issues.dlang.org/show_bug.cgi?id=14124
2182 @safe unittest
2183 {
2184     auto x = BigInt(-3);
2185     x %= 3;
2186     assert(!x.isNegative);
2187     assert(x.isZero);
2188 
2189     x = BigInt(-3);
2190     x %= cast(ushort) 3;
2191     assert(!x.isNegative);
2192     assert(x.isZero);
2193 
2194     x = BigInt(-3);
2195     x %= 3L;
2196     assert(!x.isNegative);
2197     assert(x.isZero);
2198 
2199     x = BigInt(3);
2200     x %= -3;
2201     assert(!x.isNegative);
2202     assert(x.isZero);
2203 }
2204 
2205 // https://issues.dlang.org/show_bug.cgi?id=15678
2206 @safe unittest
2207 {
2208     import std.exception : assertThrown;
2209     assertThrown!ConvException(BigInt(""));
2210     assertThrown!ConvException(BigInt("0x1234BARF"));
2211     assertThrown!ConvException(BigInt("1234PUKE"));
2212 }
2213 
2214 // https://issues.dlang.org/show_bug.cgi?id=6447
2215 @safe unittest
2216 {
2217     import std.algorithm.comparison : equal;
2218     import std.range : iota;
2219 
2220     auto s = BigInt(1_000_000_000_000);
2221     auto e = BigInt(1_000_000_000_003);
2222     auto r = iota(s, e);
2223     assert(r.equal([
2224         BigInt(1_000_000_000_000),
2225         BigInt(1_000_000_000_001),
2226         BigInt(1_000_000_000_002)
2227     ]));
2228 }
2229 
2230 // https://issues.dlang.org/show_bug.cgi?id=17330
2231 @safe unittest
2232 {
2233     auto b = immutable BigInt("123");
2234     assert(b == 123);
2235 }
2236 
2237 // https://issues.dlang.org/show_bug.cgi?id=14767
2238 @safe pure unittest
2239 {
2240     static immutable a = BigInt("340282366920938463463374607431768211455");
2241     assert(a == BigInt("340282366920938463463374607431768211455"));
2242 
2243     BigInt plusTwo(in BigInt n)
2244     {
2245         return n + 2;
2246     }
2247 
2248     enum BigInt test1 = BigInt(123);
2249     enum BigInt test2 = plusTwo(test1);
2250     assert(test2 == 125);
2251 }
2252 
2253 /**
2254  * Finds the quotient and remainder for the given dividend and divisor in one operation.
2255  *
2256  * Params:
2257  *     dividend = the $(LREF BigInt) to divide
2258  *     divisor = the $(LREF BigInt) to divide the dividend by
2259  *     quotient = is set to the result of the division
2260  *     remainder = is set to the remainder of the division
2261  */
2262 void divMod(const BigInt dividend, const BigInt divisor, out BigInt quotient, out BigInt remainder) pure nothrow @safe
2263 {
2264     BigUint q, r;
2265     BigUint.divMod(dividend.data, divisor.data, q, r);
2266     quotient.sign = dividend.sign != divisor.sign;
2267     quotient.data = q;
2268     remainder.sign = r.isZero() ? false : dividend.sign;
2269     remainder.data = r;
2270 }
2271 
2272 ///
2273 @safe pure nothrow unittest
2274 {
2275     auto a = BigInt(123);
2276     auto b = BigInt(25);
2277     BigInt q, r;
2278 
2279     divMod(a, b, q, r);
2280 
2281     assert(q == 4);
2282     assert(r == 23);
2283     assert(q * b + r == a);
2284 }
2285 
2286 // https://issues.dlang.org/show_bug.cgi?id=18086
2287 @safe pure nothrow unittest
2288 {
2289     BigInt q = 1;
2290     BigInt r = 1;
2291     BigInt c = 1024;
2292     BigInt d = 100;
2293 
2294     divMod(c, d, q, r);
2295     assert(q ==  10);
2296     assert(r ==  24);
2297     assert((q * d + r) == c);
2298 
2299     divMod(c, -d, q, r);
2300     assert(q == -10);
2301     assert(r ==  24);
2302     assert(q * -d + r == c);
2303 
2304     divMod(-c, -d, q, r);
2305     assert(q ==  10);
2306     assert(r == -24);
2307     assert(q * -d + r == -c);
2308 
2309     divMod(-c, d, q, r);
2310     assert(q == -10);
2311     assert(r == -24);
2312     assert(q * d + r == -c);
2313 }
2314 
2315 // https://issues.dlang.org/show_bug.cgi?id=22771
2316 @safe pure nothrow unittest
2317 {
2318     BigInt quotient, remainder;
2319     divMod(BigInt(-50), BigInt(1), quotient, remainder);
2320     assert(remainder == 0);
2321 }
2322 
2323 // https://issues.dlang.org/show_bug.cgi?id=19740
2324 @safe unittest
2325 {
2326     BigInt a = BigInt(
2327         "241127122100380210001001124020210001001100000200003101000062221012075223052000021042250111300200000000000" ~
2328         "000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000");
2329     BigInt b = BigInt(
2330         "700200000000500418321000401140010110000022007221432000000141020011323301104104060202100200457210001600142" ~
2331         "000001012245300100001110215200000000120000000000000000000000000000000000000000000000000000000000000000000" ~
2332         "00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000");
2333 
2334     BigInt c = a * b;
2335     assert(c == BigInt(
2336         "1688372108948068874722901180228375682334987075822938736581472847151834613694489486296103575639363261807341" ~
2337         "3910091006778604956808730652275328822700182498926542563654351871390166691461743896850906716336187966456064" ~
2338         "2702007176328110013356024000000000000000000000000000000000000000000000000000000000000000000000000000000000" ~
2339         "0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000" ~
2340         "0000000000000000000000000000000000000000000000000000000000000000000000000000000000000"));
2341 }
2342 
2343 @safe unittest
2344 {
2345     auto n = BigInt("1234"d);
2346 }
2347 
2348 /**
2349 Fast power modulus calculation for $(LREF BigInt) operands.
2350 Params:
2351      base = the $(LREF BigInt) is basic operands.
2352      exponent = the $(LREF BigInt) is power exponent of base.
2353      modulus = the $(LREF BigInt) is modules to be modular of base ^ exponent.
2354 Returns:
2355      The power modulus value of (base ^ exponent) % modulus.
2356 */
2357 BigInt powmod(BigInt base, BigInt exponent, BigInt modulus) pure nothrow @safe
2358 {
2359     BigInt result = 1;
2360 
2361     while (exponent)
2362     {
2363         if (exponent.data.peekUint(0) & 1)
2364         {
2365             result = (result * base) % modulus;
2366         }
2367 
2368         auto tmp = base % modulus;
2369         base = (tmp * tmp) % modulus;
2370         exponent >>= 1;
2371     }
2372 
2373     return result;
2374 }
2375 
2376 /// for powmod
2377 @safe unittest
2378 {
2379     BigInt base = BigInt("123456789012345678901234567890");
2380     BigInt exponent = BigInt("1234567890123456789012345678901234567");
2381     BigInt modulus = BigInt("1234567");
2382 
2383     BigInt result = powmod(base, exponent, modulus);
2384     assert(result == 359079);
2385 }

Page generated by adrdox