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 : FormatSpec, FormatException;
31 import std.internal.math.biguintcore;
32 import std.range.primitives;
33 import std.traits;
34
35 /** A struct representing an arbitrary precision integer.
36 *
37 * All arithmetic operations are supported, except unsigned shift right (>>>).
38 * Bitwise operations (|, &, ^, ~) are supported, and behave as if BigInt was
39 * an infinite length 2's complement number.
40 *
41 * BigInt implements value semantics using copy-on-write. This means that
42 * assignment is cheap, but operations such as x++ will cause heap
43 * allocation. (But note that for most bigint operations, heap allocation is
44 * inevitable anyway.)
45 */
46 struct BigInt
47 {
48 private:
49 BigUint data; // BigInt adds signed arithmetic to BigUint.
50 bool sign = false;
51 public:
52 /**
53 * Construct a BigInt from a decimal or hexadecimal string. The number must
54 * be in the form of a decimal or hex literal. It may have a leading `+`
55 * or `-` sign, followed by `0x` or `0X` if hexadecimal. Underscores are
56 * permitted in any location after the `0x` and/or the sign of the number.
57 *
58 * Params:
59 * s = a finite bidirectional range of any character type
60 *
61 * Throws:
62 * $(REF ConvException, std,conv) if the string doesn't represent a valid number
63 */
64 this(Range)(Range s) if (
65 isBidirectionalRange!Range &&
66 isSomeChar!(ElementType!Range) &&
67 !isInfinite!Range &&
68 !isSomeString!Range)
69 {
70 import std.algorithm.iteration : filterBidirectional;
71 import std.algorithm.searching : startsWith;
72 import std.conv : ConvException;
73 import std.exception : enforce;
74 import std.utf : byChar;
75
76 enforce!ConvException(!s.empty, "Can't initialize BigInt with an empty range");
77
78 bool neg = false;
79 bool ok;
80
81 data = 0UL;
82
83 // check for signs and if the string is a hex value
84 if (s.front == '+')
85 {
86 s.popFront(); // skip '+'
87 }
88 else if (s.front == '-')
89 {
90 neg = true;
91 s.popFront();
92 }
93
94 if (s.save.startsWith("0x".byChar) ||
95 s.save.startsWith("0X".byChar))
96 {
97 s.popFront;
98 s.popFront;
99
100 if (!s.empty)
101 ok = data.fromHexString(s.filterBidirectional!(a => a != '_'));
102 else
103 ok = false;
104 }
105 else
106 {
107 ok = data.fromDecimalString(s.filterBidirectional!(a => a != '_'));
108 }
109
110 enforce!ConvException(ok, "Not a valid numerical string");
111
112 if (isZero())
113 neg = false;
114
115 sign = neg;
116 }
117
118 /// ditto
119 this(Range)(Range s) pure if (isSomeString!Range)
120 {
121 import std.utf : byCodeUnit;
122 this(s.byCodeUnit);
123 }
124
125 @system unittest
126 {
127 // system because of the dummy ranges eventually call std.array!string
128 import std.exception : assertThrown;
129 import std.internal.test.dummyrange;
130
131 auto r1 = new ReferenceBidirectionalRange!dchar("101");
132 auto big1 = BigInt(r1);
133 assert(big1 == BigInt(101));
134
135 auto r2 = new ReferenceBidirectionalRange!dchar("1_000");
136 auto big2 = BigInt(r2);
137 assert(big2 == BigInt(1000));
138
139 auto r3 = new ReferenceBidirectionalRange!dchar("0x0");
140 auto big3 = BigInt(r3);
141 assert(big3 == BigInt(0));
142
143 auto r4 = new ReferenceBidirectionalRange!dchar("0x");
144 assertThrown!ConvException(BigInt(r4));
145 }
146
147 /// Construct a BigInt from a built-in integral type.
148 this(T)(T x) pure nothrow if (isIntegral!T)
149 {
150 data = data.init; // @@@: Workaround for compiler bug
151 opAssign(x);
152 }
153
154 ///
155 @system unittest
156 {
157 // @system due to failure in FreeBSD32
158 ulong data = 1_000_000_000_000;
159 auto bigData = BigInt(data);
160 assert(data == BigInt("1_000_000_000_000"));
161 }
162
163 /// Construct a BigInt from another BigInt.
164 this(T)(T x) pure nothrow if (is(Unqual!T == BigInt))
165 {
166 opAssign(x);
167 }
168
169 ///
170 @system unittest
171 {
172 const(BigInt) b1 = BigInt("1_234_567_890");
173 BigInt b2 = BigInt(b1);
174 assert(b2 == BigInt("1_234_567_890"));
175 }
176
177 /// Assignment from built-in integer types.
178 BigInt opAssign(T)(T x) pure nothrow if (isIntegral!T)
179 {
180 data = cast(ulong) absUnsign(x);
181 sign = (x < 0);
182 return this;
183 }
184
185 ///
186 @system unittest
187 {
188 auto b = BigInt("123");
189 b = 456;
190 assert(b == BigInt("456"));
191 }
192
193 /// Assignment from another BigInt.
194 BigInt opAssign(T:BigInt)(T x) pure @nogc
195 {
196 data = x.data;
197 sign = x.sign;
198 return this;
199 }
200
201 ///
202 @system unittest
203 {
204 auto b1 = BigInt("123");
205 auto b2 = BigInt("456");
206 b2 = b1;
207 assert(b2 == BigInt("123"));
208 }
209
210 /**
211 * Implements assignment operators from built-in integers of the form
212 * $(D BigInt op= integer).
213 */
214 BigInt opOpAssign(string op, T)(T y) pure nothrow
215 if ((op=="+" || op=="-" || op=="*" || op=="/" || op=="%"
216 || op==">>" || op=="<<" || op=="^^" || op=="|" || op=="&" || op=="^") && isIntegral!T)
217 {
218 ulong u = absUnsign(y);
219
220 static if (op=="+")
221 {
222 data = BigUint.addOrSubInt(data, u, sign != (y<0), sign);
223 }
224 else static if (op=="-")
225 {
226 data = BigUint.addOrSubInt(data, u, sign == (y<0), sign);
227 }
228 else static if (op=="*")
229 {
230 if (y == 0)
231 {
232 sign = false;
233 data = 0UL;
234 }
235 else
236 {
237 sign = ( sign != (y<0) );
238 data = BigUint.mulInt(data, u);
239 }
240 }
241 else static if (op=="/")
242 {
243 assert(y != 0, "Division by zero");
244 static if (T.sizeof <= uint.sizeof)
245 {
246 data = BigUint.divInt(data, cast(uint) u);
247 }
248 else
249 {
250 data = BigUint.divInt(data, u);
251 }
252 sign = data.isZero() ? false : sign ^ (y < 0);
253 }
254 else static if (op=="%")
255 {
256 assert(y != 0, "Division by zero");
257 static if (is(immutable(T) == immutable(long)) || is( immutable(T) == immutable(ulong) ))
258 {
259 this %= BigInt(y);
260 }
261 else
262 {
263 data = cast(ulong) BigUint.modInt(data, cast(uint) u);
264 if (data.isZero())
265 sign = false;
266 }
267 // x%y always has the same sign as x.
268 // This is not the same as mathematical mod.
269 }
270 else static if (op==">>" || op=="<<")
271 {
272 // Do a left shift if y>0 and <<, or
273 // if y<0 and >>; else do a right shift.
274 if (y == 0)
275 return this;
276 else if ((y > 0) == (op=="<<"))
277 {
278 // Sign never changes during left shift
279 data = data.opShl(u);
280 } else
281 {
282 data = data.opShr(u);
283 if (data.isZero())
284 sign = false;
285 }
286 }
287 else static if (op=="^^")
288 {
289 sign = (y & 1) ? sign : false;
290 data = BigUint.pow(data, u);
291 }
292 else static if (op=="|" || op=="&" || op=="^")
293 {
294 BigInt b = y;
295 opOpAssign!op(b);
296 }
297 else static assert(0, "BigInt " ~ op[0..$-1] ~ "= " ~ T.stringof ~ " is not supported");
298 return this;
299 }
300
301 ///
302 @system unittest
303 {
304 //@system because opOpAssign is @system
305 auto b = BigInt("1_000_000_000");
306
307 b += 12345;
308 assert(b == BigInt("1_000_012_345"));
309
310 b /= 5;
311 assert(b == BigInt("200_002_469"));
312 }
313
314 /**
315 * Implements assignment operators of the form $(D BigInt op= BigInt).
316 */
317 BigInt opOpAssign(string op, T)(T y) pure nothrow
318 if ((op=="+" || op== "-" || op=="*" || op=="|" || op=="&" || op=="^" || op=="/" || op=="%")
319 && is (T: BigInt))
320 {
321 static if (op == "+")
322 {
323 data = BigUint.addOrSub(data, y.data, sign != y.sign, &sign);
324 }
325 else static if (op == "-")
326 {
327 data = BigUint.addOrSub(data, y.data, sign == y.sign, &sign);
328 }
329 else static if (op == "*")
330 {
331 data = BigUint.mul(data, y.data);
332 sign = isZero() ? false : sign ^ y.sign;
333 }
334 else static if (op == "/")
335 {
336 y.checkDivByZero();
337 if (!isZero())
338 {
339 data = BigUint.div(data, y.data);
340 sign = isZero() ? false : sign ^ y.sign;
341 }
342 }
343 else static if (op == "%")
344 {
345 y.checkDivByZero();
346 if (!isZero())
347 {
348 data = BigUint.mod(data, y.data);
349 // x%y always has the same sign as x.
350 if (isZero())
351 sign = false;
352 }
353 }
354 else static if (op == "|" || op == "&" || op == "^")
355 {
356 data = BigUint.bitwiseOp!op(data, y.data, sign, y.sign, sign);
357 }
358 else static assert(0, "BigInt " ~ op[0..$-1] ~ "= " ~
359 T.stringof ~ " is not supported");
360 return this;
361 }
362
363 ///
364 @system unittest
365 {
366 // @system because opOpAssign is @system
367 auto x = BigInt("123");
368 auto y = BigInt("321");
369 x += y;
370 assert(x == BigInt("444"));
371 }
372
373 /**
374 * Implements binary operators between BigInts.
375 */
376 BigInt opBinary(string op, T)(T y) pure nothrow const
377 if ((op=="+" || op == "*" || op=="-" || op=="|" || op=="&" || op=="^" ||
378 op=="/" || op=="%")
379 && is (T: BigInt))
380 {
381 BigInt r = this;
382 return r.opOpAssign!(op)(y);
383 }
384
385 ///
386 @system unittest
387 {
388 auto x = BigInt("123");
389 auto y = BigInt("456");
390 BigInt z = x * y;
391 assert(z == BigInt("56088"));
392 }
393
394 /**
395 * Implements binary operators between BigInt's and built-in integers.
396 */
397 BigInt opBinary(string op, T)(T y) pure nothrow const
398 if ((op=="+" || op == "*" || op=="-" || op=="/" || op=="|" || op=="&" ||
399 op=="^"|| op==">>" || op=="<<" || op=="^^")
400 && isIntegral!T)
401 {
402 BigInt r = this;
403 return r.opOpAssign!(op)(y);
404 }
405
406 ///
407 @system unittest
408 {
409 auto x = BigInt("123");
410 x *= 300;
411 assert(x == BigInt("36900"));
412 }
413
414 /**
415 Implements a narrowing remainder operation with built-in integer types.
416
417 This binary operator returns a narrower, built-in integer type
418 where applicable, according to the following table.
419
420 $(TABLE ,
421 $(TR $(TD `BigInt`) $(TD $(CODE_PERCENT)) $(TD `long`) $(TD $(RARR)) $(TD `long`))
422 $(TR $(TD `BigInt`) $(TD $(CODE_PERCENT)) $(TD `ulong`) $(TD $(RARR)) $(TD `BigInt`))
423 $(TR $(TD `BigInt`) $(TD $(CODE_PERCENT)) $(TD other type) $(TD $(RARR)) $(TD `int`))
424 )
425 */
426 auto opBinary(string op, T)(T y) pure nothrow const
427 if (op == "%" && isIntegral!T)
428 {
429 assert(y != 0);
430
431 // BigInt % long => long
432 // BigInt % ulong => BigInt
433 // BigInt % other_type => int
434 static if (is(Unqual!T == long) || is(Unqual!T == ulong))
435 {
436 auto r = this % BigInt(y);
437
438 static if (is(Unqual!T == long))
439 {
440 return r.toLong();
441 }
442 else
443 {
444 // return as-is to avoid overflow
445 return r;
446 }
447 }
448 else
449 {
450 immutable uint u = absUnsign(y);
451 int rem = BigUint.modInt(data, u);
452 // x%y always has the same sign as x.
453 // This is not the same as mathematical mod.
454 return sign ? -rem : rem;
455 }
456 }
457
458 ///
459 @system unittest
460 {
461 auto x = BigInt("1_000_000_500");
462 long l = 1_000_000L;
463 ulong ul = 2_000_000UL;
464 int i = 500_000;
465 short s = 30_000;
466
467 assert(is(typeof(x % l) == long) && x % l == 500L);
468 assert(is(typeof(x % ul) == BigInt) && x % ul == BigInt(500));
469 assert(is(typeof(x % i) == int) && x % i == 500);
470 assert(is(typeof(x % s) == int) && x % s == 10500);
471 }
472
473 /**
474 Implements operators with built-in integers on the left-hand side and
475 BigInt on the right-hand side.
476 */
477 BigInt opBinaryRight(string op, T)(T y) pure nothrow const
478 if ((op=="+" || op=="*" || op=="|" || op=="&" || op=="^") && isIntegral!T)
479 {
480 return opBinary!(op)(y);
481 }
482
483 ///
484 @system unittest
485 {
486 auto x = BigInt("100");
487 BigInt y = 123 + x;
488 assert(y == BigInt("223"));
489
490 BigInt z = 123 - x;
491 assert(z == BigInt("23"));
492
493 // Dividing a built-in integer type by BigInt always results in
494 // something that fits in a built-in type, so the built-in type is
495 // returned, not BigInt.
496 assert(is(typeof(1000 / x) == int));
497 assert(1000 / x == 10);
498 }
499
500 // BigInt = integer op BigInt
501 /// ditto
502 BigInt opBinaryRight(string op, T)(T y) pure nothrow const
503 if (op == "-" && isIntegral!T)
504 {
505 ulong u = absUnsign(y);
506 BigInt r;
507 static if (op == "-")
508 {
509 r.sign = sign;
510 r.data = BigUint.addOrSubInt(data, u, sign == (y<0), r.sign);
511 r.negate();
512 }
513 return r;
514 }
515
516 // integer = integer op BigInt
517 /// ditto
518 T opBinaryRight(string op, T)(T x) pure nothrow const
519 if ((op=="%" || op=="/") && isIntegral!T)
520 {
521 checkDivByZero();
522
523 static if (op == "%")
524 {
525 // x%y always has the same sign as x.
526 if (data.ulongLength > 1)
527 return x;
528 immutable u = absUnsign(x);
529 immutable rem = u % data.peekUlong(0);
530 // x%y always has the same sign as x.
531 return cast(T)((x<0) ? -rem : rem);
532 }
533 else static if (op == "/")
534 {
535 if (data.ulongLength > 1)
536 return 0;
537 return cast(T)(x / data.peekUlong(0));
538 }
539 }
540
541 // const unary operations
542 /**
543 Implements BigInt unary operators.
544 */
545 BigInt opUnary(string op)() pure nothrow const if (op=="+" || op=="-" || op=="~")
546 {
547 static if (op=="-")
548 {
549 BigInt r = this;
550 r.negate();
551 return r;
552 }
553 else static if (op=="~")
554 {
555 return -(this+1);
556 }
557 else static if (op=="+")
558 return this;
559 }
560
561 // non-const unary operations
562 /// ditto
563 BigInt opUnary(string op)() pure nothrow if (op=="++" || op=="--")
564 {
565 static if (op=="++")
566 {
567 data = BigUint.addOrSubInt(data, 1UL, sign, sign);
568 return this;
569 }
570 else static if (op=="--")
571 {
572 data = BigUint.addOrSubInt(data, 1UL, !sign, sign);
573 return this;
574 }
575 }
576
577 ///
578 @system unittest
579 {
580 auto x = BigInt("1234");
581 assert(-x == BigInt("-1234"));
582
583 ++x;
584 assert(x == BigInt("1235"));
585 }
586
587 /**
588 Implements BigInt equality test with other BigInt's and built-in
589 integer types.
590 */
opEqualsBigInt591 bool opEquals()(auto ref const BigInt y) const pure @nogc
592 {
593 return sign == y.sign && y.data == data;
594 }
595
596 /// ditto
597 bool opEquals(T)(T y) const pure nothrow @nogc if (isIntegral!T)
598 {
599 if (sign != (y<0))
600 return 0;
601 return data.opEquals(cast(ulong) absUnsign(y));
602 }
603
604 ///
605 @system unittest
606 {
607 auto x = BigInt("12345");
608 auto y = BigInt("12340");
609 int z = 12345;
610 int w = 54321;
611
612 assert(x == x);
613 assert(x != y);
614 assert(x == y + 5);
615 assert(x == z);
616 assert(x != w);
617 }
618
619 /**
620 Implements casting to bool.
621 */
622 T opCast(T:bool)() pure nothrow @nogc const
623 {
624 return !isZero();
625 }
626
627 ///
628 @system unittest
629 {
630 // Non-zero values are regarded as true
631 auto x = BigInt("1");
632 auto y = BigInt("10");
633 assert(x);
634 assert(y);
635
636 // Zero value is regarded as false
637 auto z = BigInt("0");
638 assert(!z);
639 }
640
641 /**
642 Implements casting to integer types.
643
644 Throws: $(REF ConvOverflowException, std,conv) if the number exceeds
645 the target type's range.
646 */
647 T opCast(T:ulong)() /*pure*/ const
648 {
649 if (isUnsigned!T && sign)
650 { /* throw */ }
651 else
652 if (data.ulongLength == 1)
653 {
654 ulong l = data.peekUlong(0);
655 if (isUnsigned!T || !sign)
656 {
657 if (l <= T.max)
658 return cast(T) l;
659 }
660 else
661 {
662 if (l <= ulong(T.max)+1)
663 return cast(T)-long(l); // -long.min == long.min
664 }
665 }
666
667 import std.conv : ConvOverflowException;
668 import std.string : format;
669 throw new ConvOverflowException(
670 "BigInt(%d) cannot be represented as a %s"
671 .format(this, T.stringof));
672 }
673
674 ///
675 @system unittest
676 {
677 import std.conv : to, ConvOverflowException;
678 import std.exception : assertThrown;
679
680 assert(BigInt("0").to!int == 0);
681
682 assert(BigInt("0").to!ubyte == 0);
683 assert(BigInt("255").to!ubyte == 255);
684 assertThrown!ConvOverflowException(BigInt("256").to!ubyte);
685 assertThrown!ConvOverflowException(BigInt("-1").to!ubyte);
686 }
687
688 @system unittest
689 {
690 import std.conv : to, ConvOverflowException;
691 import std.exception : assertThrown;
692
693 assert(BigInt("-1").to!byte == -1);
694 assert(BigInt("-128").to!byte == -128);
695 assert(BigInt("127").to!byte == 127);
696 assertThrown!ConvOverflowException(BigInt("-129").to!byte);
697 assertThrown!ConvOverflowException(BigInt("128").to!byte);
698
699 assert(BigInt("0").to!uint == 0);
700 assert(BigInt("4294967295").to!uint == uint.max);
701 assertThrown!ConvOverflowException(BigInt("4294967296").to!uint);
702 assertThrown!ConvOverflowException(BigInt("-1").to!uint);
703
704 assert(BigInt("-1").to!int == -1);
705 assert(BigInt("-2147483648").to!int == int.min);
706 assert(BigInt("2147483647").to!int == int.max);
707 assertThrown!ConvOverflowException(BigInt("-2147483649").to!int);
708 assertThrown!ConvOverflowException(BigInt("2147483648").to!int);
709
710 assert(BigInt("0").to!ulong == 0);
711 assert(BigInt("18446744073709551615").to!ulong == ulong.max);
712 assertThrown!ConvOverflowException(BigInt("18446744073709551616").to!ulong);
713 assertThrown!ConvOverflowException(BigInt("-1").to!ulong);
714
715 assert(BigInt("-1").to!long == -1);
716 assert(BigInt("-9223372036854775808").to!long == long.min);
717 assert(BigInt("9223372036854775807").to!long == long.max);
718 assertThrown!ConvOverflowException(BigInt("-9223372036854775809").to!long);
719 assertThrown!ConvOverflowException(BigInt("9223372036854775808").to!long);
720 }
721
722 /**
723 Implements casting to/from qualified BigInt's.
724
725 Warning: Casting to/from $(D const) or $(D immutable) may break type
726 system guarantees. Use with care.
727 */
728 T opCast(T)() pure nothrow @nogc const
729 if (is(Unqual!T == BigInt))
730 {
731 return this;
732 }
733
734 ///
735 @system unittest
736 {
737 const(BigInt) x = BigInt("123");
738 BigInt y = cast() x; // cast away const
739 assert(y == x);
740 }
741
742 // Hack to make BigInt's typeinfo.compare work properly.
743 // Note that this must appear before the other opCmp overloads, otherwise
744 // DMD won't find it.
745 /**
746 Implements 3-way comparisons of BigInt with BigInt or BigInt with
747 built-in integers.
748 */
opCmpBigInt749 int opCmp(ref const BigInt y) pure nothrow @nogc const
750 {
751 // Simply redirect to the "real" opCmp implementation.
752 return this.opCmp!BigInt(y);
753 }
754
755 /// ditto
756 int opCmp(T)(T y) pure nothrow @nogc const if (isIntegral!T)
757 {
758 if (sign != (y<0) )
759 return sign ? -1 : 1;
760 int cmp = data.opCmp(cast(ulong) absUnsign(y));
761 return sign? -cmp: cmp;
762 }
763 /// ditto
764 int opCmp(T:BigInt)(const T y) pure nothrow @nogc const
765 {
766 if (sign != y.sign)
767 return sign ? -1 : 1;
768 immutable cmp = data.opCmp(y.data);
769 return sign? -cmp: cmp;
770 }
771
772 ///
773 @system unittest
774 {
775 auto x = BigInt("100");
776 auto y = BigInt("10");
777 int z = 50;
778 const int w = 200;
779
780 assert(y < x);
781 assert(x > z);
782 assert(z > y);
783 assert(x < w);
784 }
785
786 /**
787 Returns: The value of this BigInt as a long, or +/- long.max if outside
788 the representable range.
789 */
toLongBigInt790 long toLong() @safe pure nothrow const @nogc
791 {
792 return (sign ? -1 : 1) *
793 (data.ulongLength == 1 && (data.peekUlong(0) <= sign+cast(ulong)(long.max)) // 1+long.max = |long.min|
794 ? cast(long)(data.peekUlong(0))
795 : long.max);
796 }
797
798 ///
799 @system unittest
800 {
801 auto b = BigInt("12345");
802 long l = b.toLong();
803 assert(l == 12345);
804 }
805
806 /**
807 Returns: The value of this BigInt as an int, or +/- int.max if outside
808 the representable range.
809 */
toIntBigInt810 int toInt() @safe pure nothrow @nogc const
811 {
812 return (sign ? -1 : 1) *
813 (data.uintLength == 1 && (data.peekUint(0) <= sign+cast(uint)(int.max)) // 1+int.max = |int.min|
814 ? cast(int)(data.peekUint(0))
815 : int.max);
816 }
817
818 ///
819 @system unittest
820 {
821 auto big = BigInt("5_000_000");
822 auto i = big.toInt();
823 assert(i == 5_000_000);
824
825 // Numbers that are too big to fit into an int will be clamped to int.max.
826 auto tooBig = BigInt("5_000_000_000");
827 i = tooBig.toInt();
828 assert(i == int.max);
829 }
830
831 /// Number of significant uints which are used in storing this number.
832 /// The absolute value of this BigInt is always < 2$(SUPERSCRIPT 32*uintLength)
uintLengthBigInt833 @property size_t uintLength() @safe pure nothrow @nogc const
834 {
835 return data.uintLength;
836 }
837
838 /// Number of significant ulongs which are used in storing this number.
839 /// The absolute value of this BigInt is always < 2$(SUPERSCRIPT 64*ulongLength)
ulongLengthBigInt840 @property size_t ulongLength() @safe pure nothrow @nogc const
841 {
842 return data.ulongLength;
843 }
844
845 /** Convert the BigInt to string, passing it to the given sink.
846 *
847 * Params:
848 * sink = A delegate for accepting possibly piecewise segments of the
849 * formatted string.
850 * formatString = A format string specifying the output format.
851 *
852 * $(TABLE Available output formats:,
853 * $(TR $(TD "d") $(TD Decimal))
854 * $(TR $(TD "o") $(TD Octal))
855 * $(TR $(TD "x") $(TD Hexadecimal, lower case))
856 * $(TR $(TD "X") $(TD Hexadecimal, upper case))
857 * $(TR $(TD "s") $(TD Default formatting (same as "d") ))
858 * $(TR $(TD null) $(TD Default formatting (same as "d") ))
859 * )
860 */
toStringBigInt861 void toString(scope void delegate(const (char)[]) sink, string formatString) const
862 {
863 auto f = FormatSpec!char(formatString);
864 f.writeUpToNextSpec(sink);
865 toString(sink, f);
866 }
867
868 /// ditto
869 void toString(scope void delegate(const(char)[]) sink, ref FormatSpec!char f) const
870 {
871 immutable hex = (f.spec == 'x' || f.spec == 'X');
872 if (!(f.spec == 's' || f.spec == 'd' || f.spec =='o' || hex))
873 throw new FormatException("Format specifier not understood: %" ~ f.spec);
874
875 char[] buff;
876 if (f.spec == 'X')
877 {
878 buff = data.toHexString(0, '_', 0, f.flZero ? '0' : ' ', LetterCase.upper);
879 }
880 else if (f.spec == 'x')
881 {
882 buff = data.toHexString(0, '_', 0, f.flZero ? '0' : ' ', LetterCase.lower);
883 }
884 else if (f.spec == 'o')
885 {
886 buff = data.toOctalString();
887 }
888 else
889 {
890 buff = data.toDecimalString(0);
891 }
892 assert(buff.length > 0);
893
894 char signChar = isNegative() ? '-' : 0;
895 auto minw = buff.length + (signChar ? 1 : 0);
896
897 if (!hex && !signChar && (f.width == 0 || minw < f.width))
898 {
899 if (f.flPlus)
900 {
901 signChar = '+';
902 ++minw;
903 }
904 else if (f.flSpace)
905 {
906 signChar = ' ';
907 ++minw;
908 }
909 }
910
911 immutable maxw = minw < f.width ? f.width : minw;
912 immutable difw = maxw - minw;
913
914 if (!f.flDash && !f.flZero)
915 foreach (i; 0 .. difw)
916 sink(" ");
917
918 if (signChar)
919 sink((&signChar)[0 .. 1]);
920
921 if (!f.flDash && f.flZero)
922 foreach (i; 0 .. difw)
923 sink("0");
924
925 sink(buff);
926
927 if (f.flDash)
928 foreach (i; 0 .. difw)
929 sink(" ");
930 }
931
932 /**
933 $(D toString) is rarely directly invoked; the usual way of using it is via
934 $(REF format, std, format):
935 */
936 @system unittest
937 {
938 import std.format : format;
939
940 auto x = BigInt("1_000_000");
941 x *= 12345;
942
943 assert(format("%d", x) == "12345000000");
944 assert(format("%x", x) == "2_dfd1c040");
945 assert(format("%X", x) == "2_DFD1C040");
946 assert(format("%o", x) == "133764340100");
947 }
948
949 // Implement toHash so that BigInt works properly as an AA key.
950 /**
951 Returns: A unique hash of the BigInt's value suitable for use in a hash
952 table.
953 */
toHashBigInt954 size_t toHash() const @safe nothrow
955 {
956 return data.toHash() + sign;
957 }
958
959 /**
960 $(D toHash) is rarely directly invoked; it is implicitly used when
961 BigInt is used as the key of an associative array.
962 */
963 @safe unittest
964 {
965 string[BigInt] aa;
966 aa[BigInt(123)] = "abc";
967 aa[BigInt(456)] = "def";
968
969 assert(aa[BigInt(123)] == "abc");
970 assert(aa[BigInt(456)] == "def");
971 }
972
973 private:
negateBigInt974 void negate() @safe pure nothrow @nogc
975 {
976 if (!data.isZero())
977 sign = !sign;
978 }
isZeroBigInt979 bool isZero() pure const nothrow @nogc @safe
980 {
981 return data.isZero();
982 }
isNegativeBigInt983 bool isNegative() pure const nothrow @nogc @safe
984 {
985 return sign;
986 }
987
988 // Generate a runtime error if division by zero occurs
checkDivByZeroBigInt989 void checkDivByZero() pure const nothrow @safe
990 {
991 if (isZero())
992 throw new Error("BigInt division by zero");
993 }
994 }
995
996 ///
997 @system unittest
998 {
999 BigInt a = "9588669891916142";
1000 BigInt b = "7452469135154800";
1001 auto c = a * b;
1002 assert(c == BigInt("71459266416693160362545788781600"));
1003 auto d = b * a;
1004 assert(d == BigInt("71459266416693160362545788781600"));
1005 assert(d == c);
1006 d = c * BigInt("794628672112");
1007 assert(d == BigInt("56783581982794522489042432639320434378739200"));
1008 auto e = c + d;
1009 assert(e == BigInt("56783581982865981755459125799682980167520800"));
1010 auto f = d + c;
1011 assert(f == e);
1012 auto g = f - c;
1013 assert(g == d);
1014 g = f - d;
1015 assert(g == c);
1016 e = 12345678;
1017 g = c + e;
1018 auto h = g / b;
1019 auto i = g % b;
1020 assert(h == a);
1021 assert(i == e);
1022 BigInt j = "-0x9A56_57f4_7B83_AB78";
1023 j ^^= 11;
1024 }
1025
1026 /**
1027 Params:
1028 x = The $(D BigInt) to convert to a decimal $(D string).
1029
1030 Returns:
1031 A $(D string) that represents the $(D BigInt) as a decimal number.
1032
1033 */
toDecimalString(const (BigInt)x)1034 string toDecimalString(const(BigInt) x)
1035 {
1036 string outbuff="";
1037 void sink(const(char)[] s) { outbuff ~= s; }
1038 x.toString(&sink, "%d");
1039 return outbuff;
1040 }
1041
1042 ///
1043 @system unittest
1044 {
1045 auto x = BigInt("123");
1046 x *= 1000;
1047 x += 456;
1048
1049 auto xstr = x.toDecimalString();
1050 assert(xstr == "123456");
1051 }
1052
1053 /**
1054 Params:
1055 x = The $(D BigInt) to convert to a hexadecimal $(D string).
1056
1057 Returns:
1058 A $(D string) that represents the $(D BigInt) as a hexadecimal (base 16)
1059 number in upper case.
1060
1061 */
toHex(const (BigInt)x)1062 string toHex(const(BigInt) x)
1063 {
1064 string outbuff="";
1065 void sink(const(char)[] s) { outbuff ~= s; }
1066 x.toString(&sink, "%X");
1067 return outbuff;
1068 }
1069
1070 ///
1071 @system unittest
1072 {
1073 auto x = BigInt("123");
1074 x *= 1000;
1075 x += 456;
1076
1077 auto xstr = x.toHex();
1078 assert(xstr == "1E240");
1079 }
1080
1081 /** Returns the absolute value of x converted to the corresponding unsigned
1082 type.
1083
1084 Params:
1085 x = The integral value to return the absolute value of.
1086
1087 Returns:
1088 The absolute value of x.
1089
1090 */
1091 Unsigned!T absUnsign(T)(T x)
1092 if (isIntegral!T)
1093 {
1094 static if (isSigned!T)
1095 {
1096 import std.conv : unsigned;
1097 /* This returns the correct result even when x = T.min
1098 * on two's complement machines because unsigned(T.min) = |T.min|
1099 * even though -T.min = T.min.
1100 */
1101 return unsigned((x < 0) ? cast(T)(0-x) : x);
1102 }
1103 else
1104 {
1105 return x;
1106 }
1107 }
1108
1109 ///
1110 nothrow pure @system
1111 unittest
1112 {
1113 assert((-1).absUnsign == 1);
1114 assert(1.absUnsign == 1);
1115 }
1116
1117 nothrow pure @system
1118 unittest
1119 {
1120 BigInt a, b;
1121 a = 1;
1122 b = 2;
1123 auto c = a + b;
1124 }
1125
1126 nothrow pure @system
1127 unittest
1128 {
1129 long a;
1130 BigInt b;
1131 auto c = a + b;
1132 auto d = b + a;
1133 }
1134
1135 nothrow pure @system
1136 unittest
1137 {
1138 BigInt x = 1, y = 2;
1139 assert(x < y);
1140 assert(x <= y);
1141 assert(y >= x);
1142 assert(y > x);
1143 assert(x != y);
1144
1145 long r1 = x.toLong;
1146 assert(r1 == 1);
1147
1148 BigInt r2 = 10 % x;
1149 assert(r2 == 0);
1150
1151 BigInt r3 = 10 / y;
1152 assert(r3 == 5);
1153
1154 BigInt[] arr = [BigInt(1)];
1155 auto incr = arr[0]++;
1156 assert(arr == [BigInt(2)]);
1157 assert(incr == BigInt(1));
1158 }
1159
1160 @system unittest
1161 {
1162 // Radix conversion
1163 assert( toDecimalString(BigInt("-1_234_567_890_123_456_789"))
1164 == "-1234567890123456789");
1165 assert( toHex(BigInt("0x1234567890123456789")) == "123_45678901_23456789");
1166 assert( toHex(BigInt("0x00000000000000000000000000000000000A234567890123456789"))
1167 == "A23_45678901_23456789");
1168 assert( toHex(BigInt("0x000_00_000000_000_000_000000000000_000000_")) == "0");
1169
1170 assert(BigInt(-0x12345678).toInt() == -0x12345678);
1171 assert(BigInt(-0x12345678).toLong() == -0x12345678);
1172 assert(BigInt(0x1234_5678_9ABC_5A5AL).ulongLength == 1);
1173 assert(BigInt(0x1234_5678_9ABC_5A5AL).toLong() == 0x1234_5678_9ABC_5A5AL);
1174 assert(BigInt(-0x1234_5678_9ABC_5A5AL).toLong() == -0x1234_5678_9ABC_5A5AL);
1175 assert(BigInt(0xF234_5678_9ABC_5A5AL).toLong() == long.max);
1176 assert(BigInt(-0x123456789ABCL).toInt() == -int.max);
1177 char[] s1 = "123".dup; // bug 8164
1178 assert(BigInt(s1) == 123);
1179 char[] s2 = "0xABC".dup;
1180 assert(BigInt(s2) == 2748);
1181
1182 assert((BigInt(-2) + BigInt(1)) == BigInt(-1));
1183 BigInt a = ulong.max - 5;
1184 auto b = -long.max % a;
1185 assert( b == -long.max % (ulong.max - 5));
1186 b = long.max / a;
1187 assert( b == long.max /(ulong.max - 5));
1188 assert(BigInt(1) - 1 == 0);
1189 assert((-4) % BigInt(5) == -4); // bug 5928
1190 assert(BigInt(-4) % BigInt(5) == -4);
1191 assert(BigInt(2)/BigInt(-3) == BigInt(0)); // bug 8022
1192 assert(BigInt("-1") > long.min); // bug 9548
1193
1194 assert(toDecimalString(BigInt("0000000000000000000000000000000000000000001234567"))
1195 == "1234567");
1196 }
1197
1198 @system unittest // Minimum signed value bug tests.
1199 {
1200 assert(BigInt("-0x8000000000000000") == BigInt(long.min));
1201 assert(BigInt("-0x8000000000000000")+1 > BigInt(long.min));
1202 assert(BigInt("-0x80000000") == BigInt(int.min));
1203 assert(BigInt("-0x80000000")+1 > BigInt(int.min));
1204 assert(BigInt(long.min).toLong() == long.min); // lossy toLong bug for long.min
1205 assert(BigInt(int.min).toInt() == int.min); // lossy toInt bug for int.min
1206 assert(BigInt(long.min).ulongLength == 1);
1207 assert(BigInt(int.min).uintLength == 1); // cast/sign extend bug in opAssign
1208 BigInt a;
1209 a += int.min;
1210 assert(a == BigInt(int.min));
1211 a = int.min - BigInt(int.min);
1212 assert(a == 0);
1213 a = int.min;
1214 assert(a == BigInt(int.min));
1215 assert(int.min % (BigInt(int.min)-1) == int.min);
1216 assert((BigInt(int.min)-1)%int.min == -1);
1217 }
1218
1219 @system unittest // Recursive division, bug 5568
1220 {
1221 enum Z = 4843;
1222 BigInt m = (BigInt(1) << (Z*8) ) - 1;
1223 m -= (BigInt(1) << (Z*6)) - 1;
1224 BigInt oldm = m;
1225
1226 BigInt a = (BigInt(1) << (Z*4) )-1;
1227 BigInt b = m % a;
1228 m /= a;
1229 m *= a;
1230 assert( m + b == oldm);
1231
1232 m = (BigInt(1) << (4846 + 4843) ) - 1;
1233 a = (BigInt(1) << 4846 ) - 1;
1234 b = (BigInt(1) << (4846*2 + 4843)) - 1;
1235 BigInt c = (BigInt(1) << (4846*2 + 4843*2)) - 1;
1236 BigInt w = c - b + a;
1237 assert(w % m == 0);
1238
1239 // Bug 6819. ^^
1240 BigInt z1 = BigInt(10)^^64;
1241 BigInt w1 = BigInt(10)^^128;
1242 assert(z1^^2 == w1);
1243 BigInt z2 = BigInt(1)<<64;
1244 BigInt w2 = BigInt(1)<<128;
1245 assert(z2^^2 == w2);
1246 // Bug 7993
1247 BigInt n7793 = 10;
1248 assert( n7793 / 1 == 10);
1249 // Bug 7973
1250 auto a7973 = 10_000_000_000_000_000;
1251 const c7973 = 10_000_000_000_000_000;
1252 immutable i7973 = 10_000_000_000_000_000;
1253 BigInt v7973 = 2551700137;
1254 v7973 %= a7973;
1255 assert(v7973 == 2551700137);
1256 v7973 %= c7973;
1257 assert(v7973 == 2551700137);
1258 v7973 %= i7973;
1259 assert(v7973 == 2551700137);
1260 // 8165
1261 BigInt[2] a8165;
1262 a8165[0] = a8165[1] = 1;
1263 }
1264
1265 @system unittest
1266 {
1267 import std.array;
1268 import std.format;
1269
1270 immutable string[][] table = [
1271 /* fmt, +10 -10 */
1272 ["%d", "10", "-10"],
1273 ["%+d", "+10", "-10"],
1274 ["%-d", "10", "-10"],
1275 ["%+-d", "+10", "-10"],
1276
1277 ["%4d", " 10", " -10"],
1278 ["%+4d", " +10", " -10"],
1279 ["%-4d", "10 ", "-10 "],
1280 ["%+-4d", "+10 ", "-10 "],
1281
1282 ["%04d", "0010", "-010"],
1283 ["%+04d", "+010", "-010"],
1284 ["%-04d", "10 ", "-10 "],
1285 ["%+-04d", "+10 ", "-10 "],
1286
1287 ["% 04d", " 010", "-010"],
1288 ["%+ 04d", "+010", "-010"],
1289 ["%- 04d", " 10 ", "-10 "],
1290 ["%+- 04d", "+10 ", "-10 "],
1291 ];
1292
1293 auto w1 = appender!(char[])();
1294 auto w2 = appender!(char[])();
1295
foreach(entry;table)1296 foreach (entry; table)
1297 {
1298 immutable fmt = entry[0];
1299
1300 formattedWrite(w1, fmt, BigInt(10));
1301 formattedWrite(w2, fmt, 10);
1302 assert(w1.data == w2.data);
1303 assert(w1.data == entry[1]);
1304 w1.clear();
1305 w2.clear();
1306
1307 formattedWrite(w1, fmt, BigInt(-10));
1308 formattedWrite(w2, fmt, -10);
1309 assert(w1.data == w2.data);
1310 assert(w1.data == entry[2]);
1311 w1.clear();
1312 w2.clear();
1313 }
1314 }
1315
1316 @system unittest
1317 {
1318 import std.array;
1319 import std.format;
1320
1321 immutable string[][] table = [
1322 /* fmt, +10 -10 */
1323 ["%x", "a", "-a"],
1324 ["%+x", "a", "-a"],
1325 ["%-x", "a", "-a"],
1326 ["%+-x", "a", "-a"],
1327
1328 ["%4x", " a", " -a"],
1329 ["%+4x", " a", " -a"],
1330 ["%-4x", "a ", "-a "],
1331 ["%+-4x", "a ", "-a "],
1332
1333 ["%04x", "000a", "-00a"],
1334 ["%+04x", "000a", "-00a"],
1335 ["%-04x", "a ", "-a "],
1336 ["%+-04x", "a ", "-a "],
1337
1338 ["% 04x", "000a", "-00a"],
1339 ["%+ 04x", "000a", "-00a"],
1340 ["%- 04x", "a ", "-a "],
1341 ["%+- 04x", "a ", "-a "],
1342 ];
1343
1344 auto w1 = appender!(char[])();
1345 auto w2 = appender!(char[])();
1346
foreach(entry;table)1347 foreach (entry; table)
1348 {
1349 immutable fmt = entry[0];
1350
1351 formattedWrite(w1, fmt, BigInt(10));
1352 formattedWrite(w2, fmt, 10);
1353 assert(w1.data == w2.data); // Equal only positive BigInt
1354 assert(w1.data == entry[1]);
1355 w1.clear();
1356 w2.clear();
1357
1358 formattedWrite(w1, fmt, BigInt(-10));
1359 //formattedWrite(w2, fmt, -10);
1360 //assert(w1.data == w2.data);
1361 assert(w1.data == entry[2]);
1362 w1.clear();
1363 //w2.clear();
1364 }
1365 }
1366
1367 @system unittest
1368 {
1369 import std.array;
1370 import std.format;
1371
1372 immutable string[][] table = [
1373 /* fmt, +10 -10 */
1374 ["%X", "A", "-A"],
1375 ["%+X", "A", "-A"],
1376 ["%-X", "A", "-A"],
1377 ["%+-X", "A", "-A"],
1378
1379 ["%4X", " A", " -A"],
1380 ["%+4X", " A", " -A"],
1381 ["%-4X", "A ", "-A "],
1382 ["%+-4X", "A ", "-A "],
1383
1384 ["%04X", "000A", "-00A"],
1385 ["%+04X", "000A", "-00A"],
1386 ["%-04X", "A ", "-A "],
1387 ["%+-04X", "A ", "-A "],
1388
1389 ["% 04X", "000A", "-00A"],
1390 ["%+ 04X", "000A", "-00A"],
1391 ["%- 04X", "A ", "-A "],
1392 ["%+- 04X", "A ", "-A "],
1393 ];
1394
1395 auto w1 = appender!(char[])();
1396 auto w2 = appender!(char[])();
1397
foreach(entry;table)1398 foreach (entry; table)
1399 {
1400 immutable fmt = entry[0];
1401
1402 formattedWrite(w1, fmt, BigInt(10));
1403 formattedWrite(w2, fmt, 10);
1404 assert(w1.data == w2.data); // Equal only positive BigInt
1405 assert(w1.data == entry[1]);
1406 w1.clear();
1407 w2.clear();
1408
1409 formattedWrite(w1, fmt, BigInt(-10));
1410 //formattedWrite(w2, fmt, -10);
1411 //assert(w1.data == w2.data);
1412 assert(w1.data == entry[2]);
1413 w1.clear();
1414 //w2.clear();
1415 }
1416 }
1417
1418 // 6448
1419 @system unittest
1420 {
1421 import std.array;
1422 import std.format;
1423
1424 auto w1 = appender!string();
1425 auto w2 = appender!string();
1426
1427 int x = 100;
1428 formattedWrite(w1, "%010d", x);
1429 BigInt bx = x;
1430 formattedWrite(w2, "%010d", bx);
1431 assert(w1.data == w2.data);
1432 //8011
1433 BigInt y = -3;
1434 ++y;
1435 assert(y.toLong() == -2);
1436 y = 1;
1437 --y;
1438 assert(y.toLong() == 0);
1439 --y;
1440 assert(y.toLong() == -1);
1441 --y;
1442 assert(y.toLong() == -2);
1443 }
1444
1445 @safe unittest
1446 {
1447 import std.math : abs;
1448 auto r = abs(BigInt(-1000)); // 6486
1449 assert(r == 1000);
1450
1451 auto r2 = abs(const(BigInt)(-500)); // 11188
1452 assert(r2 == 500);
1453 auto r3 = abs(immutable(BigInt)(-733)); // 11188
1454 assert(r3 == 733);
1455
1456 // opCast!bool
1457 BigInt one = 1, zero;
1458 assert(one && !zero);
1459 }
1460
1461 @system unittest // 6850
1462 {
pureTest()1463 pure long pureTest() {
1464 BigInt a = 1;
1465 BigInt b = 1336;
1466 a += b;
1467 return a.toLong();
1468 }
1469
1470 assert(pureTest() == 1337);
1471 }
1472
1473 @system unittest // 8435 & 10118
1474 {
1475 auto i = BigInt(100);
1476 auto j = BigInt(100);
1477
1478 // Two separate BigInt instances representing same value should have same
1479 // hash.
1480 assert(typeid(i).getHash(&i) == typeid(j).getHash(&j));
1481 assert(typeid(i).compare(&i, &j) == 0);
1482
1483 // BigInt AA keys should behave consistently.
1484 int[BigInt] aa;
1485 aa[BigInt(123)] = 123;
1486 assert(BigInt(123) in aa);
1487
1488 aa[BigInt(123)] = 321;
1489 assert(aa[BigInt(123)] == 321);
1490
1491 auto keys = aa.byKey;
1492 assert(keys.front == BigInt(123));
1493 keys.popFront();
1494 assert(keys.empty);
1495 }
1496
1497 @system unittest // 11148
1498 {
foo(BigInt)1499 void foo(BigInt) {}
1500 const BigInt cbi = 3;
1501 immutable BigInt ibi = 3;
1502
1503 assert(__traits(compiles, foo(cbi)));
1504 assert(__traits(compiles, foo(ibi)));
1505
1506 import std.conv : to;
1507 import std.meta : AliasSeq;
1508
1509 foreach (T1; AliasSeq!(BigInt, const(BigInt), immutable(BigInt)))
1510 {
1511 foreach (T2; AliasSeq!(BigInt, const(BigInt), immutable(BigInt)))
1512 {
1513 T1 t1 = 2;
1514 T2 t2 = t1;
1515
1516 T2 t2_1 = to!T2(t1);
1517 T2 t2_2 = cast(T2) t1;
1518
1519 assert(t2 == t1);
1520 assert(t2 == 2);
1521
1522 assert(t2_1 == t1);
1523 assert(t2_1 == 2);
1524
1525 assert(t2_2 == t1);
1526 assert(t2_2 == 2);
1527 }
1528 }
1529
1530 BigInt n = 2;
1531 n *= 2;
1532 }
1533
1534 @safe unittest // 8167
1535 {
1536 BigInt a = BigInt(3);
1537 BigInt b = BigInt(a);
1538 }
1539
1540 @safe unittest // 9061
1541 {
1542 long l1 = 0x12345678_90ABCDEF;
1543 long l2 = 0xFEDCBA09_87654321;
1544 long l3 = l1 | l2;
1545 long l4 = l1 & l2;
1546 long l5 = l1 ^ l2;
1547
1548 BigInt b1 = l1;
1549 BigInt b2 = l2;
1550 BigInt b3 = b1 | b2;
1551 BigInt b4 = b1 & b2;
1552 BigInt b5 = b1 ^ b2;
1553
1554 assert(l3 == b3);
1555 assert(l4 == b4);
1556 assert(l5 == b5);
1557 }
1558
1559 @system unittest // 11600
1560 {
1561 import std.conv;
1562 import std.exception : assertThrown;
1563
1564 // Original bug report
1565 assertThrown!ConvException(to!BigInt("avadakedavra"));
1566
1567 // Digit string lookalikes that are actually invalid
1568 assertThrown!ConvException(to!BigInt("0123hellothere"));
1569 assertThrown!ConvException(to!BigInt("-hihomarylowe"));
1570 assertThrown!ConvException(to!BigInt("__reallynow__"));
1571 assertThrown!ConvException(to!BigInt("-123four"));
1572 }
1573
1574 @safe unittest // 11583
1575 {
1576 BigInt x = 0;
1577 assert((x > 0) == false);
1578 }
1579
1580 @system unittest // 13391
1581 {
1582 BigInt x1 = "123456789";
1583 BigInt x2 = "123456789123456789";
1584 BigInt x3 = "123456789123456789123456789";
1585
1586 import std.meta : AliasSeq;
1587 foreach (T; AliasSeq!(byte, ubyte, short, ushort, int, uint, long, ulong))
1588 {
1589 assert((x1 * T.max) / T.max == x1);
1590 assert((x2 * T.max) / T.max == x2);
1591 assert((x3 * T.max) / T.max == x3);
1592 }
1593
1594 assert(x1 / -123456789 == -1);
1595 assert(x1 / 123456789U == 1);
1596 assert(x1 / -123456789L == -1);
1597 assert(x1 / 123456789UL == 1);
1598 assert(x2 / -123456789123456789L == -1);
1599 assert(x2 / 123456789123456789UL == 1);
1600
1601 assert(x1 / uint.max == 0);
1602 assert(x1 / ulong.max == 0);
1603 assert(x2 / ulong.max == 0);
1604
1605 x1 /= 123456789UL;
1606 assert(x1 == 1);
1607 x2 /= 123456789123456789UL;
1608 assert(x2 == 1);
1609 }
1610
1611 @system unittest // 13963
1612 {
1613 BigInt x = 1;
1614 import std.meta : AliasSeq;
1615 foreach (Int; AliasSeq!(byte, ubyte, short, ushort, int, uint))
1616 {
1617 assert(is(typeof(x % Int(1)) == int));
1618 }
1619 assert(is(typeof(x % 1L) == long));
1620 assert(is(typeof(x % 1UL) == BigInt));
1621
1622 auto x1 = BigInt(8);
1623 auto x2 = -BigInt(long.min) + 1;
1624
1625 // long
1626 assert(x1 % 2L == 0L);
1627 assert(-x1 % 2L == 0L);
1628
1629 assert(x1 % 3L == 2L);
1630 assert(x1 % -3L == 2L);
1631 assert(-x1 % 3L == -2L);
1632 assert(-x1 % -3L == -2L);
1633
1634 assert(x1 % 11L == 8L);
1635 assert(x1 % -11L == 8L);
1636 assert(-x1 % 11L == -8L);
1637 assert(-x1 % -11L == -8L);
1638
1639 // ulong
1640 assert(x1 % 2UL == BigInt(0));
1641 assert(-x1 % 2UL == BigInt(0));
1642
1643 assert(x1 % 3UL == BigInt(2));
1644 assert(-x1 % 3UL == -BigInt(2));
1645
1646 assert(x1 % 11UL == BigInt(8));
1647 assert(-x1 % 11UL == -BigInt(8));
1648
1649 assert(x2 % ulong.max == x2);
1650 assert(-x2 % ulong.max == -x2);
1651 }
1652
1653 @system unittest // 14124
1654 {
1655 auto x = BigInt(-3);
1656 x %= 3;
1657 assert(!x.isNegative());
1658 assert(x.isZero());
1659
1660 x = BigInt(-3);
1661 x %= cast(ushort) 3;
1662 assert(!x.isNegative());
1663 assert(x.isZero());
1664
1665 x = BigInt(-3);
1666 x %= 3L;
1667 assert(!x.isNegative());
1668 assert(x.isZero());
1669
1670 x = BigInt(3);
1671 x %= -3;
1672 assert(!x.isNegative());
1673 assert(x.isZero());
1674 }
1675
1676 // issue 15678
1677 @system unittest
1678 {
1679 import std.exception : assertThrown;
1680 assertThrown!ConvException(BigInt(""));
1681 assertThrown!ConvException(BigInt("0x1234BARF"));
1682 assertThrown!ConvException(BigInt("1234PUKE"));
1683 }
1684
1685 // Issue 6447
1686 @system unittest
1687 {
1688 import std.algorithm.comparison : equal;
1689 import std.range : iota;
1690
1691 auto s = BigInt(1_000_000_000_000);
1692 auto e = BigInt(1_000_000_000_003);
1693 auto r = iota(s, e);
1694 assert(r.equal([
1695 BigInt(1_000_000_000_000),
1696 BigInt(1_000_000_000_001),
1697 BigInt(1_000_000_000_002)
1698 ]));
1699 }
1700
1701 // Issue 17330
1702 @system unittest
1703 {
1704 auto b = immutable BigInt("123");
1705 }
1706