1 /** Arbitrary-precision ('bignum') arithmetic.
3 * Performance is optimized for numbers below ~1000 decimal digits.
4 * For X86 machines, highly optimised assembly routines are used.
6 * The following algorithms are currently implemented:
8 * $(LI Karatsuba multiplication)
9 * $(LI Squaring is optimized independently of multiplication)
10 * $(LI Divide-and-conquer division)
11 * $(LI Binary exponentiation)
14 * For very large numbers, consider using the $(HTTP gmplib.org, GMP library) instead.
16 * License: $(HTTP www.boost.org/LICENSE_1_0.txt, Boost License 1.0).
17 * Authors: Don Clugston
18 * Source: $(PHOBOSSRC std/bigint.d)
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)
28 import std
.conv
: ConvException
;
30 import std
.format
.spec
: FormatSpec
;
31 import std
.format
: FormatException
;
32 import std
.internal
.math
.biguintcore
;
33 import std
.internal
.math
.biguintnoasm
: BigDigit
;
34 import std
.range
.primitives
;
37 /** A struct representing an arbitrary precision integer.
39 * All arithmetic operations are supported, except unsigned shift right (`>>>`).
40 * Bitwise operations (`|`, `&`, `^`, `~`) are supported, and behave as if BigInt was
41 * an infinite length 2's complement number.
43 * BigInt implements value semantics using copy-on-write. This means that
44 * assignment is cheap, but operations such as x++ will cause heap
45 * allocation. (But note that for most bigint operations, heap allocation is
51 BigUint data
; // BigInt adds signed arithmetic to BigUint.
55 * Construct a `BigInt` from a decimal or hexadecimal string. The number must
56 * be in the form of a decimal or hex literal. It may have a leading `+`
57 * or `-` sign, followed by `0x` or `0X` if hexadecimal. Underscores are
58 * permitted in any location after the `0x` and/or the sign of the number.
61 * s = a finite bidirectional range of any character type
64 * $(REF ConvException, std,conv) if the string doesn't represent a valid number
66 this(Range
)(Range s
) if (
67 isBidirectionalRange
!Range
&&
68 isSomeChar
!(ElementType
!Range
) &&
70 !isNarrowString
!Range
)
72 import std
.algorithm
.iteration
: filterBidirectional
;
73 import std
.algorithm
.searching
: startsWith
;
74 import std
.conv
: ConvException
;
75 import std
.exception
: enforce
;
76 import std
.utf
: byChar
;
78 enforce
!ConvException(!s
.empty
, "Can't initialize BigInt with an empty range");
85 // check for signs and if the string is a hex value
88 s
.popFront(); // skip '+'
90 else if (s
.front
== '-')
96 if (s
.save
.startsWith("0x".byChar
) ||
97 s
.save
.startsWith("0X".byChar
))
103 ok
= data
.fromHexString(s
.filterBidirectional
!(a
=> a
!= '_'));
109 ok
= data
.fromDecimalString(s
.filterBidirectional
!(a
=> a
!= '_'));
112 enforce
!ConvException(ok
, "Not a valid numerical string");
121 this(Range
)(Range s
) pure
122 if (isNarrowString
!Range
)
124 import std
.utf
: byCodeUnit
;
130 // system because of the dummy ranges eventually call std.array!string
131 import std
.exception
: assertThrown
;
132 import std
.internal
.test.dummyrange
;
134 auto r1
= new ReferenceBidirectionalRange
!dchar("101");
135 auto big1
= BigInt(r1
);
136 assert(big1
== BigInt(101));
138 auto r2
= new ReferenceBidirectionalRange
!dchar("1_000");
139 auto big2
= BigInt(r2
);
140 assert(big2
== BigInt(1000));
142 auto r3
= new ReferenceBidirectionalRange
!dchar("0x0");
143 auto big3
= BigInt(r3
);
144 assert(big3
== BigInt(0));
146 auto r4
= new ReferenceBidirectionalRange
!dchar("0x");
147 assertThrown
!ConvException(BigInt(r4
));
151 * Construct a `BigInt` from a sign and a magnitude.
153 * The magnitude is an $(REF_ALTTEXT input range, isInputRange, std,range,primitives)
154 * of unsigned integers that satisfies either $(REF hasLength, std,range,primitives)
155 * or $(REF isForwardRange, std,range,primitives). The first (leftmost)
156 * element of the magnitude is considered the most significant.
159 * isNegative = true for negative, false for non-negative
160 * (ignored when magnitude is zero)
161 * magnitude = a finite range of unsigned integers
163 this(Range
)(bool isNegative
, Range magnitude
) if (
164 isInputRange
!Range
&&
165 isUnsigned
!(ElementType
!Range
) &&
166 (hasLength
!Range || isForwardRange
!Range
) &&
169 data
.fromMagnitude(magnitude
);
170 sign
= isNegative
&& !data
.isZero
;
176 ubyte[] magnitude
= [1, 2, 3, 4, 5, 6];
177 auto b1
= BigInt(false, magnitude
);
178 assert(cast(long) b1
== 0x01_02_03_04_05_06L);
179 auto b2
= BigInt(true, magnitude
);
180 assert(cast(long) b2
== -0x01_02_03_04_05_06L);
183 /// Construct a `BigInt` from a built-in integral type.
184 this(T
)(T x
) pure nothrow @safe if (isIntegral
!T
)
186 data
= data
.init
; // @@@: Workaround for compiler bug
193 ulong data
= 1_000_000_000_000;
194 auto bigData
= BigInt(data
);
195 assert(bigData
== BigInt("1_000_000_000_000"));
198 /// Construct a `BigInt` from another `BigInt`.
199 this(T
)(T x
) pure nothrow @safe if (is(immutable T
== immutable BigInt
))
207 const(BigInt
) b1
= BigInt("1_234_567_890");
208 BigInt b2
= BigInt(b1
);
209 assert(b2
== BigInt("1_234_567_890"));
212 /// Assignment from built-in integer types.
213 BigInt
opAssign(T
)(T x
) pure nothrow @safe if (isIntegral
!T
)
215 data
= cast(ulong) absUnsign(x
);
223 auto b
= BigInt("123");
225 assert(b
== BigInt("456"));
228 /// Assignment from another BigInt.
229 BigInt
opAssign(T
:BigInt
)(T x
) pure @nogc @safe
239 auto b1
= BigInt("123");
240 auto b2
= BigInt("456");
242 assert(b2
== BigInt("123"));
246 * Implements assignment operators from built-in integers of the form
247 * `BigInt op= integer`.
249 BigInt
opOpAssign(string op
, T
)(T y
) pure nothrow @safe return scope
250 if ((op
=="+" || op
=="-" || op
=="*" || op
=="/" || op
=="%"
251 || op
==">>" || op
=="<<" || op
=="^^" || op
=="|" || op
=="&" || op
=="^") && isIntegral
!T
)
253 ulong u
= absUnsign(y
);
257 data
= BigUint
.addOrSubInt
!ulong(data
, u
, wantSub
: sign
!= (y
<0), sign
);
259 else static if (op
=="-")
261 data
= BigUint
.addOrSubInt
!ulong(data
, u
, wantSub
: sign
== (y
<0), sign
);
263 else static if (op
=="*")
272 sign
= ( sign
!= (y
<0) );
273 data
= BigUint
.mulInt(data
, u
);
276 else static if (op
=="/")
278 assert(y
!= 0, "Division by zero");
279 static if (T
.sizeof
<= uint.sizeof
)
281 data
= BigUint
.divInt(data
, cast(uint) u
);
285 data
= BigUint
.divInt(data
, u
);
287 sign
= data
.isZero() ?
false : sign ^
(y
< 0);
289 else static if (op
=="%")
291 assert(y
!= 0, "Division by zero");
292 static if (is(immutable(T
) == immutable(long)) ||
is( immutable(T
) == immutable(ulong) ))
298 data
= cast(ulong) BigUint
.modInt(data
, cast(uint) u
);
302 // x%y always has the same sign as x.
303 // This is not the same as mathematical mod.
305 else static if (op
==">>" || op
=="<<")
307 // Do a left shift if y>0 and <<, or
308 // if y<0 and >>; else do a right shift.
311 else if ((y
> 0) == (op
=="<<"))
313 // Sign never changes during left shift
314 data
= data
.opBinary
!(op
)(u
);
318 data
= data
.opBinary
!(op
)(u
);
323 else static if (op
=="^^")
325 sign
= (y
& 1) ? sign
: false;
329 data
= cast(ulong) (data
== 1);
333 data
= BigUint
.pow(data
, u
);
336 else static if (op
=="&")
338 if (y
>= 0 && (y
<= 1 ||
!sign
)) // In these cases we can avoid some allocation.
340 static if (T
.sizeof
<= uint.sizeof
&& BigDigit
.sizeof
<= uint.sizeof
)
341 data
= cast(ulong) data
.peekUint(0) & y
;
343 data
= data
.peekUlong(0) & y
;
352 else static if (op
=="|" || op
=="^")
357 else static assert(0, "BigInt " ~ op
[0..$-1] ~ "= " ~ T
.stringof
~ " is not supported");
364 auto b
= BigInt("1_000_000_000");
367 assert(b
== BigInt("1_000_012_345"));
370 assert(b
== BigInt("200_002_469"));
373 // https://issues.dlang.org/show_bug.cgi?id=16264
377 `335690982744637013564796917901053301979460129353374296317539383938630086938` ~
378 `465898213033510992292836631752875403891802201862860531801760096359705447768` ~
379 `957432600293361240407059207520920532482429912948952142341440301429494694368` ~
380 `264560802292927144211230021750155988283029753927847924288850436812178022006` ~
381 `408597793414273953252832688620479083497367463977081627995406363446761896298` ~
382 `967177607401918269561385622811274398143647535024987050366350585544531063531` ~
383 `7118554808325723941557169427279911052268935775`);
386 `207672245542926038535480439528441949928508406405023044025560363701392340829` ~
387 `852529131306106648201340460604257466180580583656068555417076345439694125326` ~
388 `843947164365500055567495554645796102453565953360564114634705366335703491527` ~
389 `429426780005741168078089657359833601261803592920462081364401456331489106355` ~
390 `199133982282631108670436696758342051198891939367812305559960349479160308314` ~
391 `068518200681530999860641597181672463704794566473241690395901768680673716414` ~
392 `243691584391572899147223065906633310537507956952626106509069491302359792769` ~
393 `378934570685117202046921464019396759638376362935855896435623442486036961070` ~
394 `534574698959398017332214518246531363445309522357827985468581166065335726996` ~
395 `711467464306784543112544076165391268106101754253962102479935962248302404638` ~
396 `21737237102628470475027851189594709504`);
398 BigInt c
= a
* b
; // Crashes
401 `697137001950904057507249234183127244116872349433141878383548259425589716813` ~
402 `135440660252012378417669596912108637127036044977634382385990472429604619344` ~
403 `738746224291111527200379708978133071390303850450970292020176369525401803474` ~
404 `998613408923490273129022167907826017408385746675184651576154302536663744109` ~
405 `111018961065316024005076097634601030334948684412785487182572502394847587887` ~
406 `507385831062796361152176364659197432600147716058873232435238712648552844428` ~
407 `058885217631715287816333209463171932255049134340904981280717725999710525214` ~
408 `161541960645335744430049558161514565159449390036287489478108344584188898872` ~
409 `434914159748515512161981956372737022393466624249130107254611846175580584736` ~
410 `276213025837422102290580044755202968610542057651282410252208599309841499843` ~
411 `672251048622223867183370008181364966502137725166782667358559333222947265344` ~
412 `524195551978394625568228658697170315141077913403482061673401937141405425042` ~
413 `283546509102861986303306729882186190883772633960389974665467972016939172303` ~
414 `653623175801495207204880400522581834672918935651426160175413277309985678579` ~
415 `830872397214091472424064274864210953551447463312267310436493480881235642109` ~
416 `668498742629676513172286703948381906930297135997498416573231570483993847269` ~
417 `479552708416124555462530834668011570929850407031109157206202741051573633443` ~
422 // https://issues.dlang.org/show_bug.cgi?id=24028
425 import std
.exception
: assertThrown
;
426 import core
.exception
: AssertError
;
428 assert(BigInt(100) ^^
-1 == BigInt(0));
429 assert(BigInt(1) ^^
-1 == BigInt(1));
430 assert(BigInt(-1) ^^
-1 == BigInt(-1));
431 assert(BigInt(-1) ^^
-2 == BigInt(1));
432 assertThrown
!AssertError(BigInt(0) ^^
-1);
436 * Implements assignment operators of the form `BigInt op= BigInt`.
438 BigInt
opOpAssign(string op
, T
)(T y
) pure nothrow @safe return scope
439 if ((op
=="+" || op
== "-" || op
=="*" || op
=="|" || op
=="&" || op
=="^" || op
=="/" || op
=="%")
442 static if (op
== "+")
444 data
= BigUint
.addOrSub(data
, y
.data
, sign
!= y
.sign
, sign
);
446 else static if (op
== "-")
448 data
= BigUint
.addOrSub(data
, y
.data
, sign
== y
.sign
, sign
);
450 else static if (op
== "*")
452 data
= BigUint
.mul(data
, y
.data
);
453 sign
= isZero() ?
false : sign ^ y
.sign
;
455 else static if (op
== "/")
460 data
= BigUint
.div(data
, y
.data
);
461 sign
= isZero() ?
false : sign ^ y
.sign
;
464 else static if (op
== "%")
469 data
= BigUint
.mod(data
, y
.data
);
470 // x%y always has the same sign as x.
475 else static if (op
== "|" || op
== "&" || op
== "^")
477 data
= BigUint
.bitwiseOp
!op(data
, y
.data
, sign
, y
.sign
, sign
);
479 else static assert(0, "BigInt " ~ op
[0..$-1] ~ "= " ~
480 T
.stringof
~ " is not supported");
487 auto x
= BigInt("123");
488 auto y
= BigInt("321");
490 assert(x
== BigInt("444"));
494 * Implements binary operators between `BigInt`s.
496 BigInt
opBinary(string op
, T
)(T y
) pure nothrow @safe const return scope
497 if ((op
=="+" || op
== "*" || op
=="-" || op
=="|" || op
=="&" || op
=="^" ||
502 return r
.opOpAssign
!(op
)(y
);
508 auto x
= BigInt("123");
509 auto y
= BigInt("456");
511 assert(z
== BigInt("56088"));
515 * Implements binary operators between `BigInt`'s and built-in integers.
517 BigInt
opBinary(string op
, T
)(T y
) pure nothrow @safe const return scope
518 if ((op
=="+" || op
== "*" || op
=="-" || op
=="/" || op
=="|" || op
=="&" ||
519 op
=="^"|| op
==">>" || op
=="<<" || op
=="^^")
523 r
.opOpAssign
!(op
)(y
);
530 auto x
= BigInt("123");
532 assert(x
== BigInt("36900"));
536 Implements a narrowing remainder operation with built-in integer types.
538 This binary operator returns a narrower, built-in integer type
539 where applicable, according to the following table.
542 $(TR $(TD `BigInt`) $(TD $(CODE_PERCENT)) $(TD `uint`) $(TD $(RARR)) $(TD `long`))
543 $(TR $(TD `BigInt`) $(TD $(CODE_PERCENT)) $(TD `long`) $(TD $(RARR)) $(TD `long`))
544 $(TR $(TD `BigInt`) $(TD $(CODE_PERCENT)) $(TD `ulong`) $(TD $(RARR)) $(TD `BigInt`))
545 $(TR $(TD `BigInt`) $(TD $(CODE_PERCENT)) $(TD other type) $(TD $(RARR)) $(TD `int`))
548 auto opBinary(string op
, T
)(T y
) pure nothrow @safe const
549 if (op
== "%" && isIntegral
!T
)
551 assert(y
!= 0, "% 0 not allowed");
553 // BigInt % uint => long
554 // BigInt % long => long
555 // BigInt % ulong => BigInt
556 // BigInt % other_type => int
557 static if (is(immutable T
== immutable long) ||
is(immutable T
== immutable ulong))
559 auto r
= this % BigInt(y
);
561 static if (is(immutable T
== immutable long))
567 // return as-is to avoid overflow
573 immutable uint u
= absUnsign(y
);
574 static if (is(immutable T
== immutable uint))
578 R rem
= BigUint
.modInt(data
, u
);
579 // x%y always has the same sign as x.
580 // This is not the same as mathematical mod.
581 return sign ?
-rem
: rem
;
588 auto x
= BigInt("1_000_000_500");
590 ulong ul
= 2_000_000UL;
594 assert(is(typeof(x
% l
) == long) && x
% l
== 500L);
595 assert(is(typeof(x
% ul
) == BigInt
) && x
% ul
== BigInt(500));
596 assert(is(typeof(x
% i
) == int) && x
% i
== 500);
597 assert(is(typeof(x
% s
) == int) && x
% s
== 10500);
601 Implements operators with built-in integers on the left-hand side and
602 `BigInt` on the right-hand side.
604 BigInt
opBinaryRight(string op
, T
)(T y
) pure nothrow @safe const
605 if ((op
=="+" || op
=="*" || op
=="|" || op
=="&" || op
=="^") && isIntegral
!T
)
607 return opBinary
!(op
)(y
);
613 auto x
= BigInt("100");
615 assert(y
== BigInt("223"));
618 assert(z
== BigInt("23"));
620 // Dividing a built-in integer type by BigInt always results in
621 // something that fits in a built-in type, so the built-in type is
622 // returned, not BigInt.
623 assert(is(typeof(1000 / x
) == int));
624 assert(1000 / x
== 10);
627 // BigInt = integer op BigInt
629 BigInt
opBinaryRight(string op
, T
)(T y
) pure nothrow @safe const
630 if (op
== "-" && isIntegral
!T
)
632 ulong u
= absUnsign(y
);
634 static if (op
== "-")
637 r
.data
= BigUint
.addOrSubInt
!ulong(data
, u
, wantSub
: sign
== (y
<0), r
.sign
);
643 // integer = integer op BigInt
645 T
opBinaryRight(string op
, T
)(T x
) pure nothrow @safe const
646 if ((op
=="%" || op
=="/") && isIntegral
!T
)
650 static if (op
== "%")
652 // x%y always has the same sign as x.
653 if (data
.ulongLength
> 1)
655 immutable u
= absUnsign(x
);
656 immutable rem
= u
% data
.peekUlong(0);
657 // x%y always has the same sign as x.
658 return cast(T
)((x
<0) ?
-rem
: rem
);
660 else static if (op
== "/")
662 if (data
.ulongLength
> 1)
664 return cast(T
)(x
/ data
.peekUlong(0));
668 // const unary operations
670 Implements `BigInt` unary operators.
672 BigInt
opUnary(string op
)() pure nothrow @safe const if (op
=="+" || op
=="-" || op
=="~")
680 else static if (op
=="~")
684 else static if (op
=="+")
688 // non-const unary operations
690 BigInt
opUnary(string op
)() pure nothrow @safe if (op
=="++" || op
=="--")
694 data
= BigUint
.addOrSubInt
!ulong(data
, 1UL, wantSub
: sign
, sign
);
697 else static if (op
=="--")
699 data
= BigUint
.addOrSubInt
!ulong(data
, 1UL, wantSub
: !sign
, sign
);
707 auto x
= BigInt("1234");
708 assert(-x
== BigInt("-1234"));
711 assert(x
== BigInt("1235"));
715 Implements `BigInt` equality test with other `BigInt`'s and built-in
718 bool opEquals()(auto ref const BigInt y
) const pure @nogc @safe
720 return sign
== y
.sign
&& y
.data
== data
;
724 bool opEquals(T
)(const T y
) const pure nothrow @nogc @safe if (isIntegral
!T
)
728 return data
.opEquals(cast(ulong) absUnsign(y
));
732 bool opEquals(T
)(const T y
) const pure nothrow @nogc if (isFloatingPoint
!T
)
734 return 0 == opCmp(y
);
740 // Note that when comparing a BigInt to a float or double the
741 // full precision of the BigInt is always considered, unlike
742 // when comparing an int to a float or a long to a double.
743 assert(BigInt(123456789) != cast(float) 123456789);
748 auto x
= BigInt("12345");
749 auto y
= BigInt("12340");
762 import std
.math
.operations
: nextDown
, nextUp
;
764 const x
= BigInt("0x1abc_de80_0000_0000_0000_0000_0000_0000");
768 const d
= 0x1.abcde8p124
;
772 assert(x
!= nextUp(d
));
773 assert(x
!= nextDown(d
));
774 assert(x
!= double.nan
);
776 const dL
= 0x1.abcde8p124L
;
780 assert(x
!= nextUp(dL
));
781 assert(x
!= nextDown(dL
));
782 assert(x
!= real.nan
);
784 assert(BigInt(0) == 0.0f);
785 assert(BigInt(0) == 0.0);
786 assert(BigInt(0) == 0.0L);
787 assert(BigInt(0) == -0.0f);
788 assert(BigInt(0) == -0.0);
789 assert(BigInt(0) == -0.0L);
790 assert(BigInt("999_999_999_999_999_999_999_999_999_999_999_999_999") != float.infinity
);
794 Implements casting to `bool`.
796 T
opCast(T
:bool)() pure nothrow @nogc @safe const
804 // Non-zero values are regarded as true
805 auto x
= BigInt("1");
806 auto y
= BigInt("10");
810 // Zero value is regarded as false
811 auto z
= BigInt("0");
816 Implements casting to integer types.
818 Throws: $(REF ConvOverflowException, std,conv) if the number exceeds
819 the target type's range.
821 T
opCast(T
:ulong)() pure @safe const
823 if (isUnsigned
!T
&& sign
)
826 if (data
.ulongLength
== 1)
828 ulong l
= data
.peekUlong(0);
829 if (isUnsigned
!T ||
!sign
)
836 if (l
<= ulong(T
.max
)+1)
837 return cast(T
)-long(l
); // -long.min == long.min
841 import std
.conv
: ConvOverflowException
;
842 import std
.string
: format
;
843 throw new ConvOverflowException(
844 "BigInt(%s) cannot be represented as a %s"
845 .format(this.toDecimalString
, T
.stringof
));
851 import std
.conv
: to
, ConvOverflowException
;
852 import std
.exception
: assertThrown
;
854 assert(BigInt("0").to
!int == 0);
856 assert(BigInt("0").to
!ubyte == 0);
857 assert(BigInt("255").to
!ubyte == 255);
858 assertThrown
!ConvOverflowException(BigInt("256").to
!ubyte);
859 assertThrown
!ConvOverflowException(BigInt("-1").to
!ubyte);
864 import std
.conv
: to
, ConvOverflowException
;
865 import std
.exception
: assertThrown
;
867 assert(BigInt("-1").to
!byte == -1);
868 assert(BigInt("-128").to
!byte == -128);
869 assert(BigInt("127").to
!byte == 127);
870 assertThrown
!ConvOverflowException(BigInt("-129").to
!byte);
871 assertThrown
!ConvOverflowException(BigInt("128").to
!byte);
873 assert(BigInt("0").to
!uint == 0);
874 assert(BigInt("4294967295").to
!uint == uint.max
);
875 assertThrown
!ConvOverflowException(BigInt("4294967296").to
!uint);
876 assertThrown
!ConvOverflowException(BigInt("-1").to
!uint);
878 assert(BigInt("-1").to
!int == -1);
879 assert(BigInt("-2147483648").to
!int == int.min
);
880 assert(BigInt("2147483647").to
!int == int.max
);
881 assertThrown
!ConvOverflowException(BigInt("-2147483649").to
!int);
882 assertThrown
!ConvOverflowException(BigInt("2147483648").to
!int);
884 assert(BigInt("0").to
!ulong == 0);
885 assert(BigInt("18446744073709551615").to
!ulong == ulong.max
);
886 assertThrown
!ConvOverflowException(BigInt("18446744073709551616").to
!ulong);
887 assertThrown
!ConvOverflowException(BigInt("-1").to
!ulong);
889 assert(BigInt("-1").to
!long == -1);
890 assert(BigInt("-9223372036854775808").to
!long == long.min
);
891 assert(BigInt("9223372036854775807").to
!long == long.max
);
892 assertThrown
!ConvOverflowException(BigInt("-9223372036854775809").to
!long);
893 assertThrown
!ConvOverflowException(BigInt("9223372036854775808").to
!long);
897 Implements casting to floating point types.
899 T
opCast(T
)() @safe nothrow @nogc const if (isFloatingPoint
!T
)
901 return toFloat
!(T
, "nearest");
907 assert(cast(float) BigInt("35540592535949172786332045140593475584")
908 == 35540592535949172786332045140593475584.0f);
909 assert(cast(double) BigInt("35540601499647381470685035515422441472")
910 == 35540601499647381470685035515422441472.0);
911 assert(cast(real) BigInt("35540601499647381470685035515422441472")
912 == 35540601499647381470685035515422441472.0L);
914 assert(cast(float) BigInt("-0x1345_6780_0000_0000_0000_0000_0000") == -0x1.3456_78p
+108f );
915 assert(cast(double) BigInt("-0x1345_678a_bcde_f000_0000_0000_0000") == -0x1.3456_78ab_cdefp
+108 );
916 assert(cast(real) BigInt("-0x1345_678a_bcde_f000_0000_0000_0000") == -0x1.3456_78ab_cdefp
+108L);
919 /// Rounding when casting to floating point
922 // BigInts whose values cannot be exactly represented as float/double/real
923 // are rounded when cast to float/double/real. When cast to float or
924 // double or 64-bit real the rounding is strictly defined. When cast
925 // to extended-precision real the rounding rules vary by environment.
927 // BigInts that fall somewhere between two non-infinite floats/doubles
928 // are rounded to the closer value when cast to float/double.
929 assert(cast(float) BigInt(0x1aaa_aae
7) == 0x1.aaa_aaep
+28f);
930 assert(cast(float) BigInt(0x1aaa_aaff
) == 0x1.aaa_ab0p
+28f);
931 assert(cast(float) BigInt(-0x1aaa_aae
7) == -0x1.aaaaaep
+28f);
932 assert(cast(float) BigInt(-0x1aaa_aaff
) == -0x1.aaaab0p
+28f);
934 assert(cast(double) BigInt(0x1aaa_aaaa_aaaa_aa
77) == 0x1.aaa_aaaa_aaaa_aa00p
+60);
935 assert(cast(double) BigInt(0x1aaa_aaaa_aaaa_aaff
) == 0x1.aaa_aaaa_aaaa_ab00p
+60);
936 assert(cast(double) BigInt(-0x1aaa_aaaa_aaaa_aa
77) == -0x1.aaa_aaaa_aaaa_aa00p
+60);
937 assert(cast(double) BigInt(-0x1aaa_aaaa_aaaa_aaff
) == -0x1.aaa_aaaa_aaaa_ab00p
+60);
939 // BigInts that fall exactly between two non-infinite floats/doubles
940 // are rounded away from zero when cast to float/double. (Note that
941 // in most environments this is NOT the same rounding rule rule used
942 // when casting int/long to float/double.)
943 assert(cast(float) BigInt(0x1aaa_aaf
0) == 0x1.aaa_ab0p
+28f);
944 assert(cast(float) BigInt(-0x1aaa_aaf
0) == -0x1.aaaab0p
+28f);
946 assert(cast(double) BigInt(0x1aaa_aaaa_aaaa_aa
80) == 0x1.aaa_aaaa_aaaa_ab00p
+60);
947 assert(cast(double) BigInt(-0x1aaa_aaaa_aaaa_aa
80) == -0x1.aaa_aaaa_aaaa_ab00p
+60);
949 // BigInts that are bounded on one side by the largest positive or
950 // most negative finite float/double and on the other side by infinity
951 // or -infinity are rounded as if in place of infinity was the value
952 // `2^^(T.max_exp)` when cast to float/double.
953 assert(cast(float) BigInt("999_999_999_999_999_999_999_999_999_999_999_999_999") == float.infinity
);
954 assert(cast(float) BigInt("-999_999_999_999_999_999_999_999_999_999_999_999_999") == -float.infinity
);
956 assert(cast(double) BigInt("999_999_999_999_999_999_999_999_999_999_999_999_999") < double.infinity
);
957 assert(cast(real) BigInt("999_999_999_999_999_999_999_999_999_999_999_999_999") < real.infinity
);
962 // Test exponent overflow is correct.
963 assert(cast(float) BigInt(0x1fffffff) == 0x1.000000p
+29f);
964 assert(cast(double) BigInt(0x1fff_ffff_ffff_fff
0) == 0x1.000000p
+61);
967 private T
toFloat(T
, string roundingMode
)() @safe nothrow @nogc const
968 if (__traits(isFloating
, T
) && (roundingMode
== "nearest" || roundingMode
== "truncate"))
970 import core
.bitop
: bsr;
971 enum performRounding
= (roundingMode
== "nearest");
972 enum performTruncation
= (roundingMode
== "truncate");
973 static assert(performRounding || performTruncation
, "unrecognized rounding mode");
974 enum int totalNeededBits
= T
.mant_dig
+ int(performRounding
);
975 static if (totalNeededBits
<= 64)
977 // We need to examine the top two 64-bit words, not just the top one,
978 // since the top word could have just a single significant bit.
979 const ulongLength
= data
.ulongLength
;
980 const ulong w1
= data
.peekUlong(ulongLength
- 1);
982 return T(0); // Special: exponent should be all zero bits, plus bsr(w1) is undefined.
983 const ulong w2
= ulongLength
< 2 ?
0 : data
.peekUlong(ulongLength
- 2);
984 const uint w1BitCount
= bsr(w1
) + 1;
985 ulong sansExponent
= (w1
<< (64 - w1BitCount
)) |
(w2
>>> (w1BitCount
));
986 size_t exponent
= (ulongLength
- 1) * 64 + w1BitCount
+ 1;
987 static if (performRounding
)
989 sansExponent
+= 1UL << (64 - totalNeededBits
);
990 if (0 <= cast(long) sansExponent
) // Use high bit to detect overflow.
992 // Do not bother filling in the high bit of sansExponent
993 // with 1. It will be discarded by float and double and 80
994 // bit real cannot be on this path with rounding enabled.
998 static if (T
.mant_dig
== float.mant_dig
)
1000 if (exponent
>= T
.max_exp
)
1001 return isNegative ?
-T
.infinity
: T
.infinity
;
1002 uint resultBits
= (uint(isNegative
) << 31) |
// sign bit
1003 ((0xFF & (exponent
- float.min_exp
)) << 23) |
// exponent
1004 cast(uint) ((sansExponent
<< 1) >>> (64 - 23)); // mantissa.
1005 // TODO: remove @trusted lambda after DIP 1000 is enabled by default.
1006 return (() @trusted => *cast(float*) &resultBits
)();
1008 else static if (T
.mant_dig
== double.mant_dig
)
1010 if (exponent
>= T
.max_exp
)
1011 return isNegative ?
-T
.infinity
: T
.infinity
;
1012 ulong resultBits
= (ulong(isNegative
) << 63) |
// sign bit
1013 ((0x7FFUL
& (exponent
- double.min_exp
)) << 52) |
// exponent
1014 ((sansExponent
<< 1) >>> (64 - 52)); // mantissa.
1015 // TODO: remove @trusted lambda after DIP 1000 is enabled by default.
1016 return (() @trusted => *cast(double*) &resultBits
)();
1020 import core
.math
: ldexp
;
1021 return ldexp(isNegative ?
-cast(real) sansExponent
: cast(real) sansExponent
,
1022 cast(int) exponent
- 65);
1027 import core
.math
: ldexp
;
1028 const ulongLength
= data
.ulongLength
;
1029 if ((ulongLength
- 1) * 64L > int.max
)
1030 return isNegative ?
-T
.infinity
: T
.infinity
;
1031 int scale
= cast(int) ((ulongLength
- 1) * 64);
1032 const ulong w1
= data
.peekUlong(ulongLength
- 1);
1034 return T(0); // Special: bsr(w1) is undefined.
1035 int bitsStillNeeded
= totalNeededBits
- bsr(w1
) - 1;
1036 T acc
= ldexp(cast(T
) w1
, scale
);
1037 for (ptrdiff_t i
= ulongLength
- 2; i
>= 0 && bitsStillNeeded
> 0; i
--)
1039 ulong w
= data
.peekUlong(i
);
1040 // To round towards zero we must make sure not to use too many bits.
1041 if (bitsStillNeeded
>= 64)
1043 acc
+= ldexp(cast(T
) w
, scale
-= 64);
1044 bitsStillNeeded
-= 64;
1048 w
= (w
>>> (64 - bitsStillNeeded
)) << (64 - bitsStillNeeded
);
1049 acc
+= ldexp(cast(T
) w
, scale
-= 64);
1060 Implements casting to/from qualified `BigInt`'s.
1062 Warning: Casting to/from `const` or `immutable` may break type
1063 system guarantees. Use with care.
1065 T
opCast(T
)() pure nothrow @nogc const
1066 if (is(immutable T
== immutable BigInt
))
1074 const(BigInt
) x
= BigInt("123");
1075 BigInt y
= cast() x
; // cast away const
1079 // Hack to make BigInt's typeinfo.compare work properly.
1080 // Note that this must appear before the other opCmp overloads, otherwise
1081 // DMD won't find it.
1083 Implements 3-way comparisons of `BigInt` with `BigInt` or `BigInt` with
1084 built-in numeric types.
1086 int opCmp(ref const BigInt y
) pure nothrow @nogc @safe const
1088 // Simply redirect to the "real" opCmp implementation.
1089 return this.opCmp
!BigInt(y
);
1093 int opCmp(T
)(const T y
) pure nothrow @nogc @safe const if (isIntegral
!T
)
1096 return sign ?
-1 : 1;
1097 int cmp = data
.opCmp(cast(ulong) absUnsign(y
));
1098 return sign?
-cmp: cmp;
1101 int opCmp(T
)(const T y
) nothrow @nogc @safe const if (isFloatingPoint
!T
)
1103 import core
.bitop
: bsr;
1104 import std
.math
.operations
: cmp;
1105 import std
.math
.traits
: isFinite
;
1107 const asFloat
= toFloat
!(T
, "truncate");
1109 return cmp(asFloat
, y
); // handles +/- NaN.
1111 return isNegative ?
1 : -1;
1112 const ulongLength
= data
.ulongLength
;
1113 const w1
= data
.peekUlong(ulongLength
- 1);
1115 return 0; // Special: bsr(w1) is undefined.
1116 const numSignificantBits
= (ulongLength
- 1) * 64 + bsr(w1
) + 1;
1117 for (ptrdiff_t bitsRemainingToCheck
= numSignificantBits
- T
.mant_dig
, i
= 0;
1118 bitsRemainingToCheck
> 0; i
++, bitsRemainingToCheck
-= 64)
1120 auto word
= data
.peekUlong(i
);
1123 // Make sure we're only checking digits that are beyond
1124 // the precision of `y`.
1125 if (bitsRemainingToCheck
< 64 && (word
<< (64 - bitsRemainingToCheck
)) == 0)
1126 break; // This can only happen on the last loop iteration.
1127 return isNegative ?
-1 : 1;
1132 int opCmp(T
:BigInt
)(const T y
) pure nothrow @nogc @safe const
1135 return sign ?
-1 : 1;
1136 immutable cmp = data
.opCmp(y
.data
);
1137 return sign?
-cmp: cmp;
1143 auto x
= BigInt("100");
1144 auto y
= BigInt("10");
1157 auto x
= BigInt("0x1abc_de80_0000_0000_0000_0000_0000_0000");
1161 double d
= 0x1.abcde8p124
;
1164 assert(x
>= d
&& x
<= d
);
1166 // Note that when comparing a BigInt to a float or double the
1167 // full precision of the BigInt is always considered, unlike
1168 // when comparing an int to a float or a long to a double.
1169 assert(BigInt(123456789) < cast(float) 123456789);
1174 assert(BigInt("999_999_999_999_999_999_999_999_999_999_999_999_999") < float.infinity
);
1176 // Test `real` works.
1177 auto x
= BigInt("0x1abc_de80_0000_0000_0000_0000_0000_0000");
1181 real d
= 0x1.abcde8p124
;
1184 assert(x
>= d
&& x
<= d
);
1186 // Test comparison for numbers of 64 bits or fewer.
1187 auto w1
= BigInt(0x1abc_de
80_0000_0000);
1190 assert(w1
.ulongLength
== 1);
1191 assert(w2
.ulongLength
== 1);
1192 assert(w3
.ulongLength
== 1);
1194 double e
= 0x1.abcde8p
+60;
1195 assert(w1
>= e
&& w1
<= e
);
1199 real eL
= 0x1.abcde8p
+60;
1200 assert(w1
>= eL
&& w1
<= eL
);
1206 Returns: The value of this `BigInt` as a `long`, or `long.max`/`long.min`
1207 if outside the representable range.
1209 long toLong() @safe pure nothrow const @nogc
1211 return (sign ?
-1 : 1) *
1212 (data
.ulongLength
== 1 && (data
.peekUlong(0) <= sign
+cast(ulong)(long.max
)) // 1+long.max = |long.min|
1213 ?
cast(long)(data
.peekUlong(0))
1220 auto b
= BigInt("12345");
1221 long l
= b
.toLong();
1226 Returns: The value of this `BigInt` as an `int`, or `int.max`/`int.min` if outside
1227 the representable range.
1229 int toInt() @safe pure nothrow @nogc const
1231 return (sign ?
-1 : 1) *
1232 (data
.uintLength
== 1 && (data
.peekUint(0) <= sign
+cast(uint)(int.max
)) // 1+int.max = |int.min|
1233 ?
cast(int)(data
.peekUint(0))
1240 auto big
= BigInt("5_000_000");
1241 auto i
= big
.toInt();
1242 assert(i
== 5_000_000);
1244 // Numbers that are too big to fit into an int will be clamped to int.max.
1245 auto tooBig
= BigInt("5_000_000_000");
1247 assert(i
== int.max
);
1250 /// Number of significant `uint`s which are used in storing this number.
1251 /// The absolute value of this `BigInt` is always < 2$(SUPERSCRIPT 32*uintLength)
1252 @property size_t
uintLength() @safe pure nothrow @nogc const
1254 return data
.uintLength
;
1257 /// Number of significant `ulong`s which are used in storing this number.
1258 /// The absolute value of this `BigInt` is always < 2$(SUPERSCRIPT 64*ulongLength)
1259 @property size_t
ulongLength() @safe pure nothrow @nogc const
1261 return data
.ulongLength
;
1264 /** Convert the `BigInt` to `string`, passing it to the given sink.
1267 * sink = An OutputRange for accepting possibly piecewise segments of the
1269 * formatString = A format string specifying the output format.
1271 * $(TABLE Available output formats:,
1272 * $(TR $(TD "d") $(TD Decimal))
1273 * $(TR $(TD "o") $(TD Octal))
1274 * $(TR $(TD "x") $(TD Hexadecimal, lower case))
1275 * $(TR $(TD "X") $(TD Hexadecimal, upper case))
1276 * $(TR $(TD "s") $(TD Default formatting (same as "d") ))
1277 * $(TR $(TD null) $(TD Default formatting (same as "d") ))
1280 void toString(Writer
)(scope ref Writer sink
, string formatString
) const
1282 auto f
= FormatSpec
!char(formatString
);
1283 f
.writeUpToNextSpec(sink
);
1284 toString
!Writer(sink
, f
);
1288 void toString(Writer
)(scope ref Writer sink
, scope const ref FormatSpec
!char f
) const
1290 import std
.range
.primitives
: put
;
1291 const spec
= f
.spec
;
1292 immutable hex
= (spec
== 'x' || spec
== 'X');
1293 if (!(spec
== 's' || spec
== 'd' || spec
=='o' || hex
))
1294 throw new FormatException("Format specifier not understood: %" ~ spec
);
1299 buff
= data
.toHexString(0, '_', 0, f
.flZero ?
'0' : ' ', LetterCase
.upper
);
1301 else if (spec
== 'x')
1303 buff
= data
.toHexString(0, '_', 0, f
.flZero ?
'0' : ' ', LetterCase
.lower
);
1305 else if (spec
== 'o')
1307 buff
= data
.toOctalString();
1311 buff
= data
.toDecimalString(0);
1313 assert(buff
.length
> 0, "Invalid buffer length");
1315 char signChar
= isNegative ?
'-' : 0;
1316 auto minw
= buff
.length
+ (signChar ?
1 : 0);
1318 if (!hex
&& !signChar
&& (f
.width
== 0 || minw
< f
.width
))
1332 immutable maxw
= minw
< f
.width ? f
.width
: minw
;
1333 immutable difw
= maxw
- minw
;
1335 if (!f
.flDash
&& !f
.flZero
)
1336 foreach (i
; 0 .. difw
)
1341 scope char[1] buf
= signChar
;
1345 if (!f
.flDash
&& f
.flZero
)
1346 foreach (i
; 0 .. difw
)
1352 foreach (i
; 0 .. difw
)
1357 `toString` is rarely directly invoked; the usual way of using it is via
1358 $(REF format, std, format):
1362 import std
.format
: format
;
1364 auto x
= BigInt("1_000_000");
1367 assert(format("%d", x
) == "12345000000");
1368 assert(format("%x", x
) == "2_dfd1c040");
1369 assert(format("%X", x
) == "2_DFD1C040");
1370 assert(format("%o", x
) == "133764340100");
1373 // for backwards compatibility, see unittest below
1375 void toString(scope void delegate(scope const(char)[]) sink
, string formatString
) const
1377 toString
!(void delegate(scope const(char)[]))(sink
, formatString
);
1380 // for backwards compatibility, see unittest below
1382 void toString(scope void delegate(scope const(char)[]) sink
, scope const ref FormatSpec
!char f
) const
1384 toString
!(void delegate(scope const(char)[]))(sink
, f
);
1387 // Backwards compatibility test
1388 // BigInt.toString used to only accept a delegate sink function, but this does not work
1389 // well with attributes such as @safe. A template function toString was added that
1390 // works on OutputRanges, but when a delegate was passed in the form of an untyped
1391 // lambda such as `str => dst.put(str)` the parameter type was inferred as `void` and
1392 // the function failed to instantiate.
1395 import std
.format
.spec
: FormatSpec
;
1396 import std
.array
: appender
;
1398 auto dst
= appender
!string();
1399 num
.toString(str => dst
.put(str), null);
1400 assert(dst
[] == "503");
1402 auto f
= FormatSpec
!char("");
1403 num
.toString(str => dst
.put(str), f
);
1404 assert(dst
[] == "503504");
1407 // Implement toHash so that BigInt works properly as an AA key.
1409 Returns: A unique hash of the `BigInt`'s value suitable for use in a hash
1412 size_t
toHash() const @safe pure nothrow @nogc
1414 return data
.toHash() + sign
;
1418 `toHash` is rarely directly invoked; it is implicitly used when
1419 BigInt is used as the key of an associative array.
1424 aa
[BigInt(123)] = "abc";
1425 aa
[BigInt(456)] = "def";
1427 assert(aa
[BigInt(123)] == "abc");
1428 assert(aa
[BigInt(456)] == "def");
1432 * Gets the nth number in the underlying representation that makes up the whole
1436 * T = the type to view the underlying representation as
1437 * n = The nth number to retrieve. Must be less than $(LREF ulongLength) or
1438 * $(LREF uintLength) with respect to `T`.
1440 * The nth `ulong` in the representation of this `BigInt`.
1442 T
getDigit(T
= ulong)(size_t n
) const
1443 if (is(T
== ulong) ||
is(T
== uint))
1445 static if (is(T
== ulong))
1447 assert(n
< ulongLength(), "getDigit index out of bounds");
1448 return data
.peekUlong(n
);
1452 assert(n
< uintLength(), "getDigit index out of bounds");
1453 return data
.peekUint(n
);
1460 auto a
= BigInt("1000");
1461 assert(a
.ulongLength() == 1);
1462 assert(a
.getDigit(0) == 1000);
1464 assert(a
.uintLength() == 1);
1465 assert(a
.getDigit
!uint(0) == 1000);
1467 auto b
= BigInt("2_000_000_000_000_000_000_000_000_000");
1468 assert(b
.ulongLength() == 2);
1469 assert(b
.getDigit(0) == 4584946418820579328);
1470 assert(b
.getDigit(1) == 108420217);
1472 assert(b
.uintLength() == 3);
1473 assert(b
.getDigit
!uint(0) == 3489660928);
1474 assert(b
.getDigit
!uint(1) == 1067516025);
1475 assert(b
.getDigit
!uint(2) == 108420217);
1479 void negate() @safe pure nothrow @nogc scope
1484 bool isZero() pure const nothrow @nogc @safe scope
1486 return data
.isZero();
1488 alias isNegative
= sign
;
1490 // Generate a runtime error if division by zero occurs
1491 void checkDivByZero() pure const nothrow @safe scope
1493 assert(!isZero(), "BigInt division by zero");
1500 BigInt a
= "9588669891916142";
1501 BigInt b
= "7452469135154800";
1503 assert(c
== BigInt("71459266416693160362545788781600"));
1505 assert(d
== BigInt("71459266416693160362545788781600"));
1507 d
= c
* BigInt("794628672112");
1508 assert(d
== BigInt("56783581982794522489042432639320434378739200"));
1510 assert(e
== BigInt("56783581982865981755459125799682980167520800"));
1523 BigInt j
= "-0x9A56_57f4_7B83_AB78";
1526 assert(k ^^
11 == j
);
1531 x = The `BigInt` to convert to a decimal `string`.
1534 A `string` that represents the `BigInt` as a decimal number.
1537 string
toDecimalString(const(BigInt
) x
) pure nothrow @safe
1539 auto buff
= x
.data
.toDecimalString(x
.isNegative ?
1 : 0);
1548 auto x
= BigInt("123");
1552 auto xstr
= x
.toDecimalString();
1553 assert(xstr
== "123456");
1558 x = The `BigInt` to convert to a hexadecimal `string`.
1561 A `string` that represents the `BigInt` as a hexadecimal (base 16)
1562 number in upper case.
1565 string
toHex(const(BigInt
) x
) pure @safe
1567 import std
.array
: appender
;
1568 auto outbuff
= appender
!string();
1569 x
.toString(outbuff
, "%X");
1576 auto x
= BigInt("123");
1580 auto xstr
= x
.toHex();
1581 assert(xstr
== "1E240");
1584 /** Returns the absolute value of x converted to the corresponding unsigned
1588 x = The integral value to return the absolute value of.
1591 The absolute value of x.
1594 Unsigned
!T
absUnsign(T
)(T x
)
1597 static if (isSigned
!T
)
1599 import std
.conv
: unsigned
;
1600 /* This returns the correct result even when x = T.min
1601 * on two's complement machines because unsigned(T.min) = |T.min|
1602 * even though -T.min = T.min.
1604 return unsigned((x
< 0) ?
cast(T
)(0-x
) : x
);
1616 assert((-1).absUnsign
== 1);
1617 assert(1.absUnsign
== 1);
1644 BigInt x
= 1, y
= 2;
1660 BigInt
[] arr
= [BigInt(1)];
1661 auto incr
= arr
[0]++;
1662 assert(arr
== [BigInt(2)]);
1663 assert(incr
== BigInt(1));
1669 assert( toDecimalString(BigInt("-1_234_567_890_123_456_789"))
1670 == "-1234567890123456789");
1671 assert( toHex(BigInt("0x1234567890123456789")) == "123_45678901_23456789");
1672 assert( toHex(BigInt("0x00000000000000000000000000000000000A234567890123456789"))
1673 == "A23_45678901_23456789");
1674 assert( toHex(BigInt("0x000_00_000000_000_000_000000000000_000000_")) == "0");
1676 assert(BigInt(-0x12345678).toInt() == -0x12345678);
1677 assert(BigInt(-0x12345678).toLong() == -0x12345678);
1678 assert(BigInt(0x1234_5678_9ABC
_5A
5AL
).ulongLength
== 1);
1679 assert(BigInt(0x1234_5678_9ABC
_5A
5AL
).toLong() == 0x1234_5678_9ABC
_5A
5AL
);
1680 assert(BigInt(-0x1234_5678_9ABC
_5A
5AL
).toLong() == -0x1234_5678_9ABC
_5A
5AL
);
1681 assert(BigInt(0xF234_5678_9ABC
_5A
5AL
).toLong() == long.max
);
1682 assert(BigInt(-0x123456789ABCL
).toInt() == -int.max
);
1683 char[] s1
= "123".dup
; // https://issues.dlang.org/show_bug.cgi?id=8164
1684 assert(BigInt(s1
) == 123);
1685 char[] s2
= "0xABC".dup
;
1686 assert(BigInt(s2
) == 2748);
1688 assert((BigInt(-2) + BigInt(1)) == BigInt(-1));
1689 BigInt a
= ulong.max
- 5;
1690 auto b
= -long.max
% a
;
1691 assert( b
== -long.max
% (ulong.max
- 5));
1693 assert( b
== long.max
/(ulong.max
- 5));
1694 assert(BigInt(1) - 1 == 0);
1695 assert((-4) % BigInt(5) == -4); // https://issues.dlang.org/show_bug.cgi?id=5928
1696 assert(BigInt(-4) % BigInt(5) == -4);
1697 assert(BigInt(2)/BigInt(-3) == BigInt(0)); // https://issues.dlang.org/show_bug.cgi?id=8022
1698 assert(BigInt("-1") > long.min
); // https://issues.dlang.org/show_bug.cgi?id=9548
1700 assert(toDecimalString(BigInt("0000000000000000000000000000000000000000001234567"))
1704 @safe unittest // Minimum signed value bug tests.
1706 assert(BigInt("-0x8000000000000000") == BigInt(long.min
));
1707 assert(BigInt("-0x8000000000000000")+1 > BigInt(long.min
));
1708 assert(BigInt("-0x80000000") == BigInt(int.min
));
1709 assert(BigInt("-0x80000000")+1 > BigInt(int.min
));
1710 assert(BigInt(long.min
).toLong() == long.min
); // lossy toLong bug for long.min
1711 assert(BigInt(int.min
).toInt() == int.min
); // lossy toInt bug for int.min
1712 assert(BigInt(long.min
).ulongLength
== 1);
1713 assert(BigInt(int.min
).uintLength
== 1); // cast/sign extend bug in opAssign
1716 assert(a
== BigInt(int.min
));
1717 a
= int.min
- BigInt(int.min
);
1720 assert(a
== BigInt(int.min
));
1721 assert(int.min
% (BigInt(int.min
)-1) == int.min
);
1722 assert((BigInt(int.min
)-1)%int.min
== -1);
1725 // Recursive division (https://issues.dlang.org/show_bug.cgi?id=5568)
1729 BigInt m
= (BigInt(1) << (Z
*8) ) - 1;
1730 m
-= (BigInt(1) << (Z
*6)) - 1;
1733 BigInt a
= (BigInt(1) << (Z
*4) )-1;
1737 assert( m
+ b
== oldm
);
1739 m
= (BigInt(1) << (4846 + 4843) ) - 1;
1740 a
= (BigInt(1) << 4846 ) - 1;
1741 b
= (BigInt(1) << (4846*2 + 4843)) - 1;
1742 BigInt c
= (BigInt(1) << (4846*2 + 4843*2)) - 1;
1743 BigInt w
= c
- b
+ a
;
1746 // https://issues.dlang.org/show_bug.cgi?id=6819
1747 BigInt z1
= BigInt(10)^^
64;
1748 BigInt w1
= BigInt(10)^^
128;
1749 assert(z1^^
2 == w1
);
1750 BigInt z2
= BigInt(1)<<64;
1751 BigInt w2
= BigInt(1)<<128;
1752 assert(z2^^
2 == w2
);
1753 // https://issues.dlang.org/show_bug.cgi?id=7993
1755 assert( n7793
/ 1 == 10);
1756 // https://issues.dlang.org/show_bug.cgi?id=7973
1757 auto a7973
= 10_000_000_000_000_000;
1758 const c7973
= 10_000_000_000_000_000;
1759 immutable i7973
= 10_000_000_000_000_000;
1760 BigInt v7973
= 2551700137;
1762 assert(v7973
== 2551700137);
1764 assert(v7973
== 2551700137);
1766 assert(v7973
== 2551700137);
1767 // https://issues.dlang.org/show_bug.cgi?id=8165
1769 a8165
[0] = a8165
[1] = 1;
1775 import std
.format
.write
: formattedWrite
;
1777 immutable string
[][] table
= [
1779 ["%d", "10", "-10"],
1780 ["%+d", "+10", "-10"],
1781 ["%-d", "10", "-10"],
1782 ["%+-d", "+10", "-10"],
1784 ["%4d", " 10", " -10"],
1785 ["%+4d", " +10", " -10"],
1786 ["%-4d", "10 ", "-10 "],
1787 ["%+-4d", "+10 ", "-10 "],
1789 ["%04d", "0010", "-010"],
1790 ["%+04d", "+010", "-010"],
1791 ["%-04d", "10 ", "-10 "],
1792 ["%+-04d", "+10 ", "-10 "],
1794 ["% 04d", " 010", "-010"],
1795 ["%+ 04d", "+010", "-010"],
1796 ["%- 04d", " 10 ", "-10 "],
1797 ["%+- 04d", "+10 ", "-10 "],
1800 auto w1
= appender
!(char[])();
1801 auto w2
= appender
!(char[])();
1803 foreach (entry
; table
)
1805 immutable fmt
= entry
[0];
1807 formattedWrite(w1
, fmt
, BigInt(10));
1808 formattedWrite(w2
, fmt
, 10);
1809 assert(w1
.data
== w2
.data
);
1810 assert(w1
.data
== entry
[1]);
1814 formattedWrite(w1
, fmt
, BigInt(-10));
1815 formattedWrite(w2
, fmt
, -10);
1816 assert(w1
.data
== w2
.data
);
1817 assert(w1
.data
== entry
[2]);
1826 import std
.format
.write
: formattedWrite
;
1828 immutable string
[][] table
= [
1833 ["%+-x", "a", "-a"],
1835 ["%4x", " a", " -a"],
1836 ["%+4x", " a", " -a"],
1837 ["%-4x", "a ", "-a "],
1838 ["%+-4x", "a ", "-a "],
1840 ["%04x", "000a", "-00a"],
1841 ["%+04x", "000a", "-00a"],
1842 ["%-04x", "a ", "-a "],
1843 ["%+-04x", "a ", "-a "],
1845 ["% 04x", "000a", "-00a"],
1846 ["%+ 04x", "000a", "-00a"],
1847 ["%- 04x", "a ", "-a "],
1848 ["%+- 04x", "a ", "-a "],
1851 auto w1
= appender
!(char[])();
1852 auto w2
= appender
!(char[])();
1854 foreach (entry
; table
)
1856 immutable fmt
= entry
[0];
1858 formattedWrite(w1
, fmt
, BigInt(10));
1859 formattedWrite(w2
, fmt
, 10);
1860 assert(w1
.data
== w2
.data
); // Equal only positive BigInt
1861 assert(w1
.data
== entry
[1]);
1865 formattedWrite(w1
, fmt
, BigInt(-10));
1866 //formattedWrite(w2, fmt, -10);
1867 //assert(w1.data == w2.data);
1868 assert(w1
.data
== entry
[2]);
1877 import std
.format
.write
: formattedWrite
;
1879 immutable string
[][] table
= [
1884 ["%+-X", "A", "-A"],
1886 ["%4X", " A", " -A"],
1887 ["%+4X", " A", " -A"],
1888 ["%-4X", "A ", "-A "],
1889 ["%+-4X", "A ", "-A "],
1891 ["%04X", "000A", "-00A"],
1892 ["%+04X", "000A", "-00A"],
1893 ["%-04X", "A ", "-A "],
1894 ["%+-04X", "A ", "-A "],
1896 ["% 04X", "000A", "-00A"],
1897 ["%+ 04X", "000A", "-00A"],
1898 ["%- 04X", "A ", "-A "],
1899 ["%+- 04X", "A ", "-A "],
1902 auto w1
= appender
!(char[])();
1903 auto w2
= appender
!(char[])();
1905 foreach (entry
; table
)
1907 immutable fmt
= entry
[0];
1909 formattedWrite(w1
, fmt
, BigInt(10));
1910 formattedWrite(w2
, fmt
, 10);
1911 assert(w1
.data
== w2
.data
); // Equal only positive BigInt
1912 assert(w1
.data
== entry
[1]);
1916 formattedWrite(w1
, fmt
, BigInt(-10));
1917 //formattedWrite(w2, fmt, -10);
1918 //assert(w1.data == w2.data);
1919 assert(w1
.data
== entry
[2]);
1925 // https://issues.dlang.org/show_bug.cgi?id=6448
1929 import std
.format
.write
: formattedWrite
;
1931 auto w1
= appender
!string();
1932 auto w2
= appender
!string();
1935 formattedWrite(w1
, "%010d", x
);
1937 formattedWrite(w2
, "%010d", bx
);
1938 assert(w1
.data
== w2
.data
);
1939 // https://issues.dlang.org/show_bug.cgi?id=8011
1942 assert(y
.toLong() == -2);
1945 assert(y
.toLong() == 0);
1947 assert(y
.toLong() == -1);
1949 assert(y
.toLong() == -2);
1954 import std
.math
.algebraic
: abs
;
1955 auto r
= abs(BigInt(-1000)); // https://issues.dlang.org/show_bug.cgi?id=6486
1958 auto r2
= abs(const(BigInt
)(-500)); // https://issues.dlang.org/show_bug.cgi?id=11188
1960 auto r3
= abs(immutable(BigInt
)(-733)); // https://issues.dlang.org/show_bug.cgi?id=11188
1964 BigInt one
= 1, zero
;
1965 assert(one
&& !zero
);
1968 // https://issues.dlang.org/show_bug.cgi?id=6850
1971 pure long pureTest() {
1978 assert(pureTest() == 1337);
1981 // https://issues.dlang.org/show_bug.cgi?id=8435
1982 // https://issues.dlang.org/show_bug.cgi?id=10118
1985 auto i
= BigInt(100);
1986 auto j
= BigInt(100);
1988 // Two separate BigInt instances representing same value should have same
1990 assert(typeid(i
).getHash(&i
) == typeid(j
).getHash(&j
));
1991 assert(typeid(i
).compare(&i
, &j
) == 0);
1993 // BigInt AA keys should behave consistently.
1995 aa
[BigInt(123)] = 123;
1996 assert(BigInt(123) in aa
);
1998 aa
[BigInt(123)] = 321;
1999 assert(aa
[BigInt(123)] == 321);
2001 auto keys
= aa
.byKey
;
2002 assert(keys
.front
== BigInt(123));
2007 // https://issues.dlang.org/show_bug.cgi?id=11148
2011 const BigInt cbi
= 3;
2012 immutable BigInt ibi
= 3;
2017 import std
.conv
: to
;
2018 import std
.meta
: AliasSeq
;
2020 static foreach (T1
; AliasSeq
!(BigInt
, const(BigInt
), immutable(BigInt
)))
2022 static foreach (T2
; AliasSeq
!(BigInt
, const(BigInt
), immutable(BigInt
)))
2027 T2 t2_1
= to
!T2(t1
);
2028 T2 t2_2
= cast(T2
) t1
;
2046 // https://issues.dlang.org/show_bug.cgi?id=8167
2049 BigInt a
= BigInt(3);
2050 BigInt b
= BigInt(a
);
2054 // https://issues.dlang.org/show_bug.cgi?id=9061
2057 long l1
= 0x12345678_90ABCDEF
;
2058 long l2
= 0xFEDCBA09_87654321;
2065 BigInt b3
= b1 | b2
;
2066 BigInt b4
= b1
& b2
;
2067 BigInt b5
= b1 ^ b2
;
2074 // https://issues.dlang.org/show_bug.cgi?id=11600
2078 import std
.exception
: assertThrown
;
2080 // Original bug report
2081 assertThrown
!ConvException(to
!BigInt("avadakedavra"));
2083 // Digit string lookalikes that are actually invalid
2084 assertThrown
!ConvException(to
!BigInt("0123hellothere"));
2085 assertThrown
!ConvException(to
!BigInt("-hihomarylowe"));
2086 assertThrown
!ConvException(to
!BigInt("__reallynow__"));
2087 assertThrown
!ConvException(to
!BigInt("-123four"));
2090 // https://issues.dlang.org/show_bug.cgi?id=11583
2094 assert((x
> 0) == false);
2097 // https://issues.dlang.org/show_bug.cgi?id=13391
2100 BigInt x1
= "123456789";
2101 BigInt x2
= "123456789123456789";
2102 BigInt x3
= "123456789123456789123456789";
2104 import std
.meta
: AliasSeq
;
2105 static foreach (T
; AliasSeq
!(byte, ubyte, short, ushort, int, uint, long, ulong))
2107 assert((x1
* T
.max
) / T
.max
== x1
);
2108 assert((x2
* T
.max
) / T
.max
== x2
);
2109 assert((x3
* T
.max
) / T
.max
== x3
);
2112 assert(x1
/ -123456789 == -1);
2113 assert(x1
/ 123456789U == 1);
2114 assert(x1
/ -123456789L == -1);
2115 assert(x1
/ 123456789UL == 1);
2116 assert(x2
/ -123456789123456789L == -1);
2117 assert(x2
/ 123456789123456789UL == 1);
2119 assert(x1
/ uint.max
== 0);
2120 assert(x1
/ ulong.max
== 0);
2121 assert(x2
/ ulong.max
== 0);
2125 x2
/= 123456789123456789UL;
2129 // https://issues.dlang.org/show_bug.cgi?id=13963
2133 import std
.meta
: AliasSeq
;
2134 static foreach (Int
; AliasSeq
!(byte, ubyte, short, ushort, int))
2136 assert(is(typeof(x
% Int(1)) == int));
2138 assert(is(typeof(x
% 1U) == long));
2139 assert(is(typeof(x
% 1L) == long));
2140 assert(is(typeof(x
% 1UL) == BigInt
));
2142 auto x0
= BigInt(uint.max
- 1);
2143 auto x1
= BigInt(8);
2144 assert(x1
/ x
== x1
);
2145 auto x2
= -BigInt(long.min
) + 1;
2148 assert( x0
% uint.max
== x0
% BigInt(uint.max
));
2149 assert(-x0
% uint.max
== -x0
% BigInt(uint.max
));
2150 assert( x0
% uint.max
== long(uint.max
- 1));
2151 assert(-x0
% uint.max
== -long(uint.max
- 1));
2154 assert(x1
% 2L == 0L);
2155 assert(-x1
% 2L == 0L);
2157 assert(x1
% 3L == 2L);
2158 assert(x1
% -3L == 2L);
2159 assert(-x1
% 3L == -2L);
2160 assert(-x1
% -3L == -2L);
2162 assert(x1
% 11L == 8L);
2163 assert(x1
% -11L == 8L);
2164 assert(-x1
% 11L == -8L);
2165 assert(-x1
% -11L == -8L);
2168 assert(x1
% 2UL == BigInt(0));
2169 assert(-x1
% 2UL == BigInt(0));
2171 assert(x1
% 3UL == BigInt(2));
2172 assert(-x1
% 3UL == -BigInt(2));
2174 assert(x1
% 11UL == BigInt(8));
2175 assert(-x1
% 11UL == -BigInt(8));
2177 assert(x2
% ulong.max
== x2
);
2178 assert(-x2
% ulong.max
== -x2
);
2181 // https://issues.dlang.org/show_bug.cgi?id=14124
2184 auto x
= BigInt(-3);
2186 assert(!x
.isNegative
);
2190 x
%= cast(ushort) 3;
2191 assert(!x
.isNegative
);
2196 assert(!x
.isNegative
);
2201 assert(!x
.isNegative
);
2205 // https://issues.dlang.org/show_bug.cgi?id=15678
2208 import std
.exception
: assertThrown
;
2209 assertThrown
!ConvException(BigInt(""));
2210 assertThrown
!ConvException(BigInt("0x1234BARF"));
2211 assertThrown
!ConvException(BigInt("1234PUKE"));
2214 // https://issues.dlang.org/show_bug.cgi?id=6447
2217 import std
.algorithm
.comparison
: equal
;
2218 import std
.range
: iota
;
2220 auto s
= BigInt(1_000_000_000_000);
2221 auto e
= BigInt(1_000_000_000_003);
2222 auto r
= iota(s
, e
);
2224 BigInt(1_000_000_000_000),
2225 BigInt(1_000_000_000_001),
2226 BigInt(1_000_000_000_002)
2230 // https://issues.dlang.org/show_bug.cgi?id=17330
2233 auto b
= immutable BigInt("123");
2237 // https://issues.dlang.org/show_bug.cgi?id=14767
2240 static immutable a
= BigInt("340282366920938463463374607431768211455");
2241 assert(a
== BigInt("340282366920938463463374607431768211455"));
2243 BigInt
plusTwo(in BigInt n
)
2248 enum BigInt test1
= BigInt(123);
2249 enum BigInt test2
= plusTwo(test1
);
2250 assert(test2
== 125);
2254 * Finds the quotient and remainder for the given dividend and divisor in one operation.
2257 * dividend = the $(LREF BigInt) to divide
2258 * divisor = the $(LREF BigInt) to divide the dividend by
2259 * quotient = is set to the result of the division
2260 * remainder = is set to the remainder of the division
2262 void divMod(const BigInt dividend
, const BigInt divisor
, out BigInt quotient
, out BigInt remainder
) pure nothrow @safe
2265 BigUint
.divMod(dividend
.data
, divisor
.data
, q
, r
);
2266 quotient
.sign
= dividend
.sign
!= divisor
.sign
;
2268 remainder
.sign
= r
.isZero() ?
false : dividend
.sign
;
2273 @safe pure nothrow unittest
2275 auto a
= BigInt(123);
2276 auto b
= BigInt(25);
2283 assert(q
* b
+ r
== a
);
2286 // https://issues.dlang.org/show_bug.cgi?id=18086
2287 @safe pure nothrow unittest
2297 assert((q
* d
+ r
) == c
);
2299 divMod(c
, -d
, q
, r
);
2302 assert(q
* -d
+ r
== c
);
2304 divMod(-c
, -d
, q
, r
);
2307 assert(q
* -d
+ r
== -c
);
2309 divMod(-c
, d
, q
, r
);
2312 assert(q
* d
+ r
== -c
);
2315 // https://issues.dlang.org/show_bug.cgi?id=22771
2316 @safe pure nothrow unittest
2318 BigInt quotient
, remainder
;
2319 divMod(BigInt(-50), BigInt(1), quotient
, remainder
);
2320 assert(remainder
== 0);
2323 // https://issues.dlang.org/show_bug.cgi?id=19740
2327 "241127122100380210001001124020210001001100000200003101000062221012075223052000021042250111300200000000000" ~
2328 "000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000");
2330 "700200000000500418321000401140010110000022007221432000000141020011323301104104060202100200457210001600142" ~
2331 "000001012245300100001110215200000000120000000000000000000000000000000000000000000000000000000000000000000" ~
2332 "00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000");
2336 "1688372108948068874722901180228375682334987075822938736581472847151834613694489486296103575639363261807341" ~
2337 "3910091006778604956808730652275328822700182498926542563654351871390166691461743896850906716336187966456064" ~
2338 "2702007176328110013356024000000000000000000000000000000000000000000000000000000000000000000000000000000000" ~
2339 "0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000" ~
2340 "0000000000000000000000000000000000000000000000000000000000000000000000000000000000000"));
2345 auto n
= BigInt("1234"d
);
2349 Fast power modulus calculation for $(LREF BigInt) operands.
2351 base = the $(LREF BigInt) is basic operands.
2352 exponent = the $(LREF BigInt) is power exponent of base.
2353 modulus = the $(LREF BigInt) is modules to be modular of base ^ exponent.
2355 The power modulus value of (base ^ exponent) % modulus.
2357 BigInt
powmod(BigInt base
, BigInt exponent
, BigInt modulus
) pure nothrow @safe
2363 if (exponent
.data
.peekUint(0) & 1)
2365 result
= (result
* base
) % modulus
;
2368 auto tmp
= base
% modulus
;
2369 base
= (tmp
* tmp
) % modulus
;
2379 BigInt base
= BigInt("123456789012345678901234567890");
2380 BigInt exponent
= BigInt("1234567890123456789012345678901234567");
2381 BigInt modulus
= BigInt("1234567");
2383 BigInt result
= powmod(base
, exponent
, modulus
);
2384 assert(result
== 359079);