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