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