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