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