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

Page generated by adrdox