1 /++ 2 Note: 3 The module doesn't provide full arithmetic API for now. 4 +/ 5 module mir.bignum.integer; 6 7 import mir.bitop; 8 import mir.serde: serdeProxy, serdeScoped; 9 import mir.utility; 10 import std.traits; 11 12 /++ 13 Stack-allocated big signed integer. 14 Params: 15 size64 = count of 64bit words in coefficient 16 +/ 17 @serdeScoped @serdeProxy!(const(char)[]) 18 struct BigInt(uint size64) 19 if (size64 && size64 <= ushort.max) 20 { 21 import mir.bignum.low_level_view; 22 import mir.bignum.fixed; 23 24 /// 25 bool sign; 26 /// 27 uint length; 28 /// 29 size_t[ulong.sizeof / size_t.sizeof * size64] data;// = void; 30 31 @safe: 32 33 /// 34 this(uint size)(UInt!size fixedInt) 35 { 36 this(fixedInt.data); 37 } 38 39 /// 40 this(uint N)(size_t[N] data) 41 if (N <= this.data.length) 42 { 43 static if (data.length == 0) 44 { 45 sign = false; 46 length = 0; 47 } 48 static if (data.length == 1) 49 { 50 this(data[0]); 51 } 52 else 53 static if (data.length == 2) 54 { 55 sign = false; 56 this.data[0] = data[0]; 57 this.data[1] = data[1]; 58 this.length = data[1] ? 2 : data[0] != 0; 59 } 60 else 61 { 62 sign = false; 63 this.data[0 .. N] = data; 64 length = data.length; 65 normalize; 66 } 67 } 68 69 /// 70 this(ulong data) 71 { 72 sign = false; 73 static if (size_t.sizeof == ulong.sizeof) 74 { 75 length = data != 0; 76 this.data[0] = data; 77 } 78 else 79 { 80 this.length = !!data + !!(data >> 32); 81 this.data[0] = cast(uint) data; 82 this.data[1] = cast(uint) (data >> 32); 83 } 84 } 85 86 /// 87 this(long data) 88 { 89 this(ulong(data < 0 ? -data : data)); 90 this.sign = data < 0; 91 } 92 93 /// 94 this(int data) 95 { 96 this(long(data)); 97 } 98 99 /// 100 this(uint data) 101 { 102 this(ulong(data)); 103 } 104 105 /// 106 this()(scope const(char)[] str) @safe pure @nogc 107 { 108 if (fromStringImpl(str)) 109 return; 110 static if (__traits(compiles, () @nogc { throw new Exception("Can't parse BigInt."); })) 111 { 112 import mir.exception: MirException; 113 throw new MirException("Can't parse BigInt!" ~ size64.stringof ~ " from string `", str , "`."); 114 } 115 else 116 { 117 static immutable exception = new Exception("Can't parse BigInt!" ~ size64.stringof ~ "."); 118 { import mir.exception : toMutable; throw exception.toMutable; } 119 } 120 } 121 122 /// 123 inout(size_t)[] coefficients()() inout @property scope return 124 { 125 return data[0 .. length]; 126 } 127 128 /// 129 ref opAssign(ulong data) return scope 130 { 131 __ctor(data); 132 return this; 133 } 134 135 /// 136 ref opAssign(long data) return scope 137 { 138 __ctor(data); 139 return this; 140 } 141 142 /// 143 ref opAssign(uint data) return scope 144 { 145 __ctor(data); 146 return this; 147 } 148 149 /// 150 ref opAssign(int data) return scope 151 { 152 __ctor(data); 153 return this; 154 } 155 156 /// 157 ref opAssign(uint rhsSize)(UInt!rhsSize data) return scope 158 { 159 __ctor(data); 160 return this; 161 } 162 163 static if (size64 == 3) 164 /// 165 version(mir_bignum_test) @safe pure @nogc unittest 166 { 167 import mir.math.constant: PI; 168 BigInt!4 integer = "-34010447314490204552169750449563978034784726557588085989975288830070948234680"; // constructor 169 assert(integer.sign); 170 integer.sign = false; 171 assert(integer == BigInt!4.fromHexString("4b313b23aa560e1b0985f89cbe6df5460860e39a64ba92b4abdd3ee77e4e05b8")); 172 } 173 174 /// 175 ref opAssign(uint rhsSize64)(auto ref scope const BigInt!rhsSize64 rhs) return 176 @trusted pure nothrow @nogc 177 in (rhs.length <= this.data.length) 178 { 179 static if (size64 == rhsSize64) 180 { 181 if (&this is &rhs) 182 return this; 183 } 184 this.sign = rhs.sign; 185 this.length = rhs.length; 186 this.data[0 .. length] = rhs.data[0 .. length]; 187 return this; 188 } 189 190 /// 191 static BigInt fromBigEndian()(scope const(ubyte)[] data, bool sign = false) 192 @trusted pure @nogc 193 { 194 static immutable bigIntOverflowException = new Exception("BigInt!" ~ size64.stringof ~ ".fromBigEndian: data overflow"); 195 BigInt ret = void; 196 if (!ret.copyFromBigEndian(data, sign)) 197 { import mir.exception : toMutable; throw bigIntOverflowException.toMutable; } 198 return ret; 199 } 200 201 /// 202 bool copyFromBigEndian()(scope const(ubyte)[] data, bool sign = false) 203 @trusted pure @nogc 204 { 205 while(data.length && data[0] == 0) 206 data = data[1 .. $]; 207 if (data.length == 0) 208 { 209 this.length = 0; 210 this.sign = false; 211 } 212 else 213 { 214 if (data.length > this.data.sizeof) 215 return false; 216 this.sign = sign; 217 this.length = cast(uint) (data.length / size_t.sizeof); 218 auto tail = data[0 .. data.length % size_t.sizeof]; 219 data = data[data.length % size_t.sizeof .. $]; 220 foreach_reverse (ref c; this.coefficients) 221 { 222 size_t value; 223 foreach (j; 0 .. size_t.sizeof) 224 { 225 value <<= 8; 226 value |= data[0]; 227 data = data[1 .. $]; 228 } 229 c = value; 230 } 231 assert(data.length == 0); 232 if (tail.length) 233 { 234 this.length++; 235 size_t value; 236 foreach (b; tail) 237 { 238 value <<= 8; 239 value |= b; 240 } 241 this.data[length - 1] = value; 242 } 243 } 244 return true; 245 } 246 247 /++ 248 Returns: false in case of overflow or incorrect string. 249 Precondition: non-empty coefficients. 250 +/ 251 bool fromStringImpl(C)(scope const(C)[] str) 252 scope @trusted pure @nogc nothrow 253 if (isSomeChar!C) 254 { 255 auto work = data[].BigIntView!size_t; 256 if (work.fromStringImpl(str)) 257 { 258 length = cast(uint) work.coefficients.length; 259 sign = work.sign; 260 return true; 261 } 262 return false; 263 } 264 265 /// 266 BigInt copy() @property 267 { 268 BigInt ret = void; 269 ret.sign = sign; 270 ret.length = length; 271 ret.data[0 .. length] = data[0 .. length]; 272 return ret; 273 } 274 275 /// 276 bool opEquals()(auto ref const BigInt rhs) 277 const @safe pure nothrow @nogc 278 { 279 return view == rhs.view; 280 } 281 282 /// 283 bool opEquals(ulong rhs, bool rhsSign = false) 284 const @safe pure nothrow @nogc 285 { 286 if (rhs == 0 && this.length == 0 || this.length == 1 && this.sign == rhsSign && this.data[0] == rhs) 287 return true; 288 static if (is(size_t == ulong) || size64 == 1) 289 return false; 290 else 291 return this.length == 2 && this.data[0] == cast(uint) rhs && this.data[1] == cast(uint) (rhs >> 32); 292 } 293 294 /// 295 bool opEquals(long rhs) 296 const @safe pure nothrow @nogc 297 { 298 auto sign = rhs < 0; 299 return this.opEquals(sign ? ulong(-rhs) : ulong(rhs), sign); 300 } 301 302 /// 303 bool opEquals(uint rhs) 304 const @safe pure nothrow @nogc 305 { 306 return opEquals(ulong(rhs), false); 307 } 308 309 /// 310 bool opEquals(int rhs) 311 const @safe pure nothrow @nogc 312 { 313 return opEquals(long(rhs)); 314 } 315 316 /++ 317 +/ 318 auto opCmp()(auto ref const BigInt rhs) 319 const @safe pure nothrow @nogc 320 { 321 return view.opCmp(rhs.view); 322 } 323 324 /// 325 BigIntView!size_t view()() scope return @property 326 { 327 return typeof(return)(this.data[0 .. this.length], this.sign); 328 } 329 330 /// 331 BigIntView!(const size_t) view()() const scope return @property 332 { 333 return typeof(return)(this.data[0 .. this.length], this.sign); 334 } 335 336 /// 337 void normalize()() 338 { 339 pragma(inline, false); 340 auto norm = view.normalized; 341 this.length = cast(uint) norm.unsigned.coefficients.length; 342 this.sign = norm.sign; 343 } 344 345 /++ 346 +/ 347 void putCoefficient(size_t value) 348 { 349 assert(length < data.length); 350 data[length++] = value; 351 } 352 353 /++ 354 Performs `size_t overflow = (big += overflow) *= scalar` operatrion. 355 Params: 356 rhs = unsigned value to multiply by 357 overflow = initial overflow value 358 Returns: 359 unsigned overflow value 360 +/ 361 size_t opOpAssign(string op : "*")(size_t rhs, size_t overflow = 0u) 362 @safe pure nothrow @nogc 363 { 364 if (length == 0) 365 goto L; 366 overflow = view.unsigned.opOpAssign!op(rhs, overflow); 367 if (overflow && length < data.length) 368 { 369 L: 370 putCoefficient(overflow); 371 overflow = 0; 372 } 373 return overflow; 374 } 375 376 /++ 377 Performs `uint remainder = (overflow$big) /= scalar` operatrion, where `$` denotes big-endian concatenation. 378 Precondition: `overflow < rhs` 379 Params: 380 rhs = unsigned value to devide by 381 overflow = initial unsigned overflow 382 Returns: 383 unsigned remainder value (evaluated overflow) 384 +/ 385 uint opOpAssign(string op : "/")(uint rhs, uint overflow = 0) 386 @safe pure nothrow @nogc 387 { 388 assert(overflow < rhs); 389 if (length) 390 return view.unsigned.opOpAssign!op(rhs, overflow); 391 return overflow; 392 } 393 394 /++ 395 Performs `size_t overflow = (big += overflow) *= fixed` operatrion. 396 Params: 397 rhs = unsigned value to multiply by 398 overflow = initial overflow value 399 Returns: 400 unsigned overflow value 401 +/ 402 UInt!size opOpAssign(string op : "*", size_t size)(UInt!size rhs, UInt!size overflow = 0) 403 @safe pure nothrow @nogc 404 { 405 if (length == 0) 406 goto L; 407 overflow = view.unsigned.opOpAssign!op(rhs, overflow); 408 if (overflow && length < data.length) 409 { 410 L: 411 static if (size <= 64) 412 { 413 auto o = cast(ulong)overflow; 414 static if (size_t.sizeof == ulong.sizeof) 415 { 416 putCoefficient(o); 417 overflow = UInt!size.init; 418 } 419 else 420 { 421 putCoefficient(cast(uint)o); 422 o >>= 32; 423 if (length < data.length) 424 { 425 putCoefficient(cast(uint)o); 426 o = 0; 427 } 428 overflow = UInt!size(o); 429 } 430 } 431 else 432 { 433 do 434 { 435 putCoefficient(cast(size_t)overflow); 436 overflow >>= size_t.sizeof * 8; 437 } 438 while(overflow && length < data.length); 439 } 440 } 441 return overflow; 442 } 443 444 /// 445 ref opOpAssign(string op, size_t size)(UInt!size rhs) 446 @safe pure nothrow @nogc scope return 447 if (op == "/" || op == "%") 448 { 449 BigInt!(size / 64) bigRhs = rhs; 450 return this.opOpAssign!op(bigRhs); 451 } 452 453 /// ditto 454 ref opOpAssign(string op)(ulong rhs) 455 @safe pure nothrow @nogc scope return 456 if (op == "/" || op == "%") 457 { 458 BigInt!1 bigRhs = rhs; 459 return this.opOpAssign!op(bigRhs); 460 } 461 462 /// ditto 463 ref opOpAssign(string op)(long rhs) 464 @safe pure nothrow @nogc scope return 465 if (op == "/" || op == "%") 466 { 467 BigInt!1 bigRhs = rhs; 468 return this.opOpAssign!op(bigRhs); 469 } 470 471 /++ 472 +/ 473 ref powMod(uint expSize)(scope ref const BigInt!expSize exponent, scope ref const BigInt modulus) 474 @safe pure nothrow @nogc return scope 475 in(!exponent.sign) 476 { 477 return this.powMod(exponent.view.unsigned, modulus); 478 } 479 480 ///ditto 481 ref powMod()(scope BigUIntView!(const size_t) exponent, scope ref const BigInt modulus) 482 @safe pure nothrow @nogc return scope 483 { 484 pragma(inline, false); 485 486 import mir.ndslice.topology: bitwise; 487 488 if (modulus == 1 || modulus == -1) 489 { 490 this.sign = 0; 491 this.length = 0; 492 return this; 493 } 494 495 BigInt!(size64 * 2) bas = void; 496 bas = this; 497 BigInt!(size64 * 2) res = void; 498 res = 1u; 499 500 foreach (b; exponent.coefficients.bitwise[0 .. $ - exponent.ctlz]) 501 { 502 bas %= modulus; 503 if (b) 504 { 505 res *= bas; 506 res %= modulus; 507 } 508 bas *= bas; 509 } 510 511 this = res; 512 return this; 513 } 514 515 /// 516 static if (size64 == 3) 517 version (mir_bignum_test) 518 unittest 519 { 520 BigInt!3 x = 2; 521 BigInt!3 e = 10; 522 BigInt!3 m = 100; 523 524 x.powMod(e, m); 525 assert(x == 24); 526 } 527 528 /// 529 static if (size64 == 3) 530 version (mir_bignum_test) 531 unittest 532 { 533 BigInt!3 x = 564321; 534 BigInt!3 e = "13763753091226345046315979581580902400000310"; 535 BigInt!3 m = "13763753091226345046315979581580902400000311"; 536 537 x.powMod(e, m); 538 assert(x == 1); 539 } 540 541 /++ 542 +/ 543 ref multiply(uint aSize64, uint bSize64) 544 ( 545 scope ref const BigInt!aSize64 a, 546 scope ref const BigInt!bSize64 b, 547 ) 548 @safe pure nothrow @nogc scope return 549 if (size64 >= aSize64 + bSize64) 550 { 551 import mir.utility: max; 552 import mir.bignum.internal.kernel : multiply, karatsubaRequiredBuffSize; 553 enum sizeM = ulong.sizeof / size_t.sizeof; 554 size_t[max(aSize64 * sizeM, bSize64 * sizeM).karatsubaRequiredBuffSize] buffer = void; 555 this.length = cast(uint) multiply(data, a.coefficients, b.coefficients, buffer); 556 this.sign = (this.length != 0) & (a.sign ^ b.sign); 557 return this; 558 } 559 560 /// 561 ref divMod(uint divisorSize64, uint remainderSize = size64) 562 ( 563 scope ref const BigInt!divisorSize64 divisor, 564 scope ref BigInt!size64 quotient, 565 scope ref BigInt!remainderSize remainder, 566 ) 567 const @trusted pure nothrow @nogc scope return 568 if (remainderSize >= divisorSize64) 569 { 570 return this.divMod(divisor, quotient, &remainder); 571 } 572 573 private ref divMod(uint divisorSize64, uint remainderSize = size64) 574 ( 575 scope ref const BigInt!divisorSize64 divisor, 576 scope ref BigInt!size64 quotient, 577 scope BigInt!remainderSize* remainder = null, 578 ) 579 const @trusted pure nothrow @nogc scope return 580 if (remainderSize >= divisorSize64) 581 { 582 import mir.bignum.internal.kernel : divMod, divisionRequiredBuffSize; 583 584 pragma(inline, false); 585 586 if (divisor.length == 0) 587 assert(0, "Zero BigInt divizor"); 588 if (divisor.coefficients[$ - 1] == 0) 589 assert(0, "Denormalized BigInt divizor"); 590 591 if (this.length < divisor.length) 592 { 593 if (remainder !is null) 594 { 595 if (&this !is remainder) 596 *remainder = this; 597 remainder.sign = 0; 598 } 599 600 static if (size64 == remainderSize) 601 if ("ient is remainder) 602 return this; 603 604 quotient.sign = 0; 605 quotient.length = 0; 606 607 return this; 608 } 609 610 enum sizeM = ulong.sizeof / size_t.sizeof; 611 enum vlen = min(divisorSize64, size64); 612 size_t[divisionRequiredBuffSize(size64 * sizeM, vlen * sizeM)] buffer = void; 613 614 quotient.length = cast(uint) divMod( 615 quotient.data, 616 remainder !is null ? remainder.data[] : null, 617 this.coefficients, 618 divisor.coefficients, 619 buffer, 620 ); 621 622 quotient.sign = (this.sign ^ divisor.sign) && quotient.length; 623 624 if (remainder !is null) 625 { 626 remainder.sign = 0; 627 remainder.length = divisor.length; 628 remainder.normalize; 629 } 630 631 return this; 632 } 633 634 /++ 635 Performs `this %= rhs` and `this /= rhs` operations. 636 Params: 637 rhs = value to divide by 638 Returns: 639 remainder or quotient from the truncated division 640 +/ 641 ref opOpAssign(string op, size_t rhsSize64)(scope const ref BigInt!rhsSize64 rhs) 642 @safe pure nothrow @nogc return 643 if (op == "/" || op == "%") 644 { 645 enum isRem = op == "%"; 646 return this.divMod(rhs, this, isRem ? &this : null); 647 } 648 649 /++ 650 Performs `this %= rhs` and `this /= rhs` operations. 651 Params: 652 rhs = value to divide by 653 Returns: 654 remainder or quotient from the truncated division 655 +/ 656 ref opOpAssign(string op : "*", size_t rhsSize64)(scope const ref BigInt!rhsSize64 rhs) 657 @safe pure nothrow @nogc return 658 { 659 BigInt!(size64 + rhsSize64) c = void; 660 c.multiply(this, rhs); 661 this = c; 662 return this; 663 } 664 665 /// 666 static if (size64 == 3) 667 version (mir_bignum_test) 668 unittest 669 { 670 BigInt!32 x = "236089459999051800787306800176765276560685597708945239133346035689205694959466543423391020917332149321603397284295007899190053323478336179162578944"; 671 BigInt!32 y = "19095614279677503764429420557677401943131308638097701560446870251856566051181587499424174939645900335127490246389509326965738171086235365599977209919032320327138167362675030414072140005376"; 672 BigInt!32 z = "4508273263639244391466225874448166762388283627989411942887789415132291146444880491003321910228134369483394456858712486391978856464207606191606690798518090459546799016472580324664149788791167494389789813815605288815981925073283892089331019170542792502117265455020551819803771537458327634120582677504637693661973404860326560198184402944"; 673 x *= y; 674 assert(x == z); 675 } 676 677 /++ 678 Performs `size_t overflow = big *= fixed` operatrion. 679 Params: 680 rhs = unsigned value to multiply by 681 Returns: 682 overflow 683 +/ 684 bool opOpAssign(string op, size_t rhsSize64)(ref const BigInt!rhsSize64 rhs) 685 @safe pure nothrow @nogc 686 if (op == "+" || op == "-") 687 { 688 return opOpAssign!op(rhs.view); 689 } 690 691 /// ditto 692 bool opOpAssign(string op)(BigIntView!(const size_t) rhs) 693 @safe pure nothrow @nogc 694 if (op == "+" || op == "-") 695 { 696 sizediff_t diff = length - rhs.coefficients.length; 697 if (diff < 0) 698 { 699 auto oldLength = length; 700 length = cast(int)rhs.coefficients.length; 701 coefficients[oldLength .. $] = 0; 702 } 703 else 704 if (rhs.coefficients.length == 0) 705 return false; 706 auto thisView = view; 707 auto overflow = thisView.opOpAssign!op(rhs); 708 this.sign = thisView.sign; 709 if (overflow) 710 { 711 if (length < data.length) 712 { 713 putCoefficient(overflow); 714 overflow = false; 715 } 716 } 717 else 718 { 719 normalize; 720 } 721 return overflow; 722 } 723 724 /// ditto 725 bool opOpAssign(string op)(ulong rhs) 726 @safe pure nothrow @nogc 727 if (op == "+" || op == "-") 728 { 729 import mir.ndslice.bignum.fixed: UInt; 730 return this.opOpAssign!op(rhs.UInt!64.view.signed); 731 } 732 733 /// ditto 734 bool opOpAssign(string op)(uint rhs) 735 @safe pure nothrow @nogc 736 if (op == "+" || op == "-") 737 { 738 return this.opOpAssign!op(ulong(rhs)); 739 } 740 741 /// ditto 742 bool opOpAssign(string op)(long rhs) 743 @safe pure nothrow @nogc 744 if (op == "+" || op == "-") 745 { 746 import mir.bignum.fixed: UInt; 747 auto sign = rhs < 0; 748 rhs = sign ? -rhs : rhs; 749 return this.opOpAssign!op(rhs.UInt!64.view.normalized.signed(sign)); 750 } 751 752 /// ditto 753 bool opOpAssign(string op)(int rhs) 754 @safe pure nothrow @nogc 755 if (op == "+" || op == "-") 756 { 757 return this.opOpAssign!op(long(rhs)); 758 } 759 760 /++ 761 +/ 762 static BigInt fromHexString(bool allowUnderscores = false)(scope const(char)[] str) 763 @trusted pure 764 { 765 BigInt ret = void; 766 if (ret.fromHexStringImpl!(char, allowUnderscores)(str)) 767 return ret; 768 version(D_Exceptions) 769 { import mir.exception : toMutable; throw hexStringException.toMutable; } 770 else 771 assert(0, hexStringErrorMsg); 772 } 773 774 /++ 775 +/ 776 bool fromHexStringImpl(C, bool allowUnderscores = false)(scope const(C)[] str) 777 @safe pure @nogc nothrow 778 if (isSomeChar!C) 779 { 780 auto work = BigIntView!size_t(data); 781 auto ret = work.fromHexStringImpl!(C, allowUnderscores)(str); 782 length = cast(uint)work.unsigned.coefficients.length; 783 sign = work.sign; 784 return ret; 785 } 786 787 /++ 788 +/ 789 static BigInt fromBinaryString(bool allowUnderscores = false)(scope const(char)[] str) 790 @trusted pure 791 { 792 BigInt ret = void; 793 if (ret.fromBinaryStringImpl!(char, allowUnderscores)(str)) 794 return ret; 795 version(D_Exceptions) 796 { import mir.exception : toMutable; throw binaryStringException.toMutable; } 797 else 798 assert(0, binaryStringErrorMsg); 799 } 800 801 static if (size64 == 3) 802 /// 803 version(mir_bignum_test) @safe pure @nogc unittest 804 { 805 BigInt!4 integer = "-34010447314490204552169750449563978034784726557588085989975288830070948234680"; // constructor 806 assert(integer == BigInt!4.fromBinaryString("-100101100110001001110110010001110101010010101100000111000011011000010011000010111111000100111001011111001101101111101010100011000001000011000001110001110011010011001001011101010010010101101001010101111011101001111101110011101111110010011100000010110111000")); 807 } 808 809 /++ 810 +/ 811 bool fromBinaryStringImpl(C, bool allowUnderscores = false)(scope const(C)[] str) 812 @safe pure @nogc nothrow 813 if (isSomeChar!C) 814 { 815 auto work = BigIntView!size_t(data); 816 auto ret = work.fromBinaryStringImpl!(C, allowUnderscores)(str); 817 length = cast(uint)work.unsigned.coefficients.length; 818 sign = work.sign; 819 return ret; 820 } 821 822 /// 823 ref pow()(ulong degree) 824 { 825 BigInt!size64 bas = void; 826 bas = this; 827 this = 1u; 828 829 while (degree) 830 { 831 if (degree & 1) 832 this *= bas; 833 bas *= bas; 834 degree >>= 1; 835 } 836 return this; 837 } 838 839 /// 840 bool mulPow5()(ulong degree) 841 { 842 import mir.bignum.internal.dec2float: MaxWordPow5; 843 // assert(approxCanMulPow5(degree)); 844 if (length == 0) 845 return false; 846 enum n = MaxWordPow5!size_t; 847 enum wordInit = size_t(5) ^^ n; 848 size_t word = wordInit; 849 size_t overflow; 850 851 while(degree) 852 { 853 if (degree >= n) 854 { 855 degree -= n; 856 } 857 else 858 { 859 word = 1; 860 do word *= 5; 861 while(--degree); 862 } 863 overflow |= this *= word; 864 } 865 return overflow != 0; 866 } 867 868 /// 869 ref BigInt opOpAssign(string op)(size_t shift) 870 @safe pure nothrow @nogc return 871 if (op == "<<" || op == ">>") 872 { 873 auto index = shift / (size_t.sizeof * 8); 874 auto bs = shift % (size_t.sizeof * 8); 875 auto ss = size_t.sizeof * 8 - bs; 876 static if (op == ">>") 877 { 878 if (index >= length) 879 { 880 length = 0; 881 return this; 882 } 883 auto d = view.coefficients; 884 if (bs) 885 { 886 foreach (j; 0 .. d.length - (index + 1)) 887 { 888 d[j] = (d[j + index] >>> bs) | (d[j + (index + 1)] << ss); 889 } 890 } 891 else 892 { 893 foreach (j; 0 .. d.length - (index + 1)) 894 { 895 d[j] = d[j + index]; 896 } 897 } 898 auto most = d[$ - (index + 1)] = d[$ - 1] >>> bs; 899 length -= index + (most == 0); 900 } 901 else 902 { 903 if (index >= data.length || length == 0) 904 { 905 length = 0; 906 return this; 907 } 908 909 if (bs) 910 { 911 auto most = coefficients[$ - 1] >> ss; 912 length += index; 913 if (length < data.length) 914 { 915 if (most) 916 { 917 length++; 918 coefficients[$ - 1] = most; 919 length--; 920 } 921 } 922 else 923 { 924 length = data.length; 925 } 926 927 auto d = view.coefficients; 928 foreach_reverse (j; index + 1 .. length) 929 { 930 d[j] = (d[j - index] << bs) | (d[j - (index + 1)] >> ss); 931 } 932 d[index] = d[0] << bs; 933 if (length < data.length) 934 length += most != 0; 935 } 936 else 937 { 938 length = cast(uint) min(length + index, cast(uint)data.length); 939 auto d = view.coefficients; 940 foreach_reverse (j; index .. length) 941 { 942 d[j] = d[j - index]; 943 } 944 } 945 view.coefficients[0 .. index] = 0; 946 } 947 return this; 948 } 949 950 /// 951 T opCast(T)() const 952 if (isFloatingPoint!T && isMutable!T) 953 { 954 return view.opCast!T; 955 } 956 957 /// 958 T opCast(T, bool nonZero = false)() const 959 if (is(T == long) || is(T == int)) 960 { 961 return this.view.opCast!(T, nonZero); 962 } 963 964 /++ 965 Returns: overflow flag 966 +/ 967 bool copyFrom(W)(scope const(W)[] coefficients, bool sign = false) 968 if (__traits(isUnsigned, W)) 969 { 970 static if (W.sizeof > size_t.sizeof) 971 { 972 return this.copyFrom(cast(BigIntView!(const size_t))view, sign); 973 } 974 else 975 { 976 this.sign = sign; 977 auto dest = cast(W[])data; 978 auto overflow = dest.length < coefficients.length; 979 auto n = overflow ? dest.length : coefficients.length; 980 this.length = cast(uint)(n / (size_t.sizeof / W.sizeof)); 981 dest[0 .. n] = coefficients[0 .. n]; 982 static if (size_t.sizeof / W.sizeof > 1) 983 { 984 if (auto tail = n % (size_t.sizeof / W.sizeof)) 985 { 986 this.length++; 987 auto shift = ((size_t.sizeof / W.sizeof) - tail) * (W.sizeof * 8); 988 auto value = this.coefficients[$ - 1]; 989 value <<= shift; 990 value >>= shift; 991 this.coefficients[$ - 1] = value; 992 } 993 } 994 return overflow; 995 } 996 } 997 998 /// 999 immutable(C)[] toString(C = char)() scope const @safe pure nothrow 1000 if(isSomeChar!C && isMutable!C) 1001 { 1002 C[ceilLog10Exp2(data.length * (size_t.sizeof * 8)) + 1] buffer = void; 1003 BigInt copy = this; 1004 auto len = copy.view.unsigned.toStringImpl(buffer); 1005 if (sign) 1006 buffer[$ - ++len] = '-'; 1007 return buffer[$ - len .. $].idup; 1008 } 1009 1010 static if (size64 == 3) 1011 /// 1012 version(mir_bignum_test) @safe pure unittest 1013 { 1014 auto str = "-34010447314490204552169750449563978034784726557588085989975288830070948234680"; 1015 auto integer = BigInt!4(str); 1016 assert(integer.toString == str); 1017 1018 integer = BigInt!4.init; 1019 assert(integer.toString == "0"); 1020 } 1021 1022 /// 1023 void toString(C = char, W)(ref scope W w) scope const 1024 if(isSomeChar!C && isMutable!C) 1025 { 1026 C[ceilLog10Exp2(data.length * (size_t.sizeof * 8)) + 1] buffer = void; 1027 BigInt copy = this; 1028 auto len = copy.view.unsigned.toStringImpl(buffer); 1029 if (sign) 1030 buffer[$ - ++len] = '-'; 1031 w.put(buffer[$ - len .. $]); 1032 } 1033 1034 /// 1035 size_t bitLength()() const @property 1036 { 1037 return length == 0 ? 0 : length * size_t.sizeof * 8 - data[length - 1].ctlz; 1038 } 1039 1040 /// 1041 size_t ctlz()() const @property 1042 { 1043 return data.sizeof * 8 - bitLength; 1044 } 1045 } 1046 1047 /// Check @nogc toString impl 1048 version(mir_bignum_test) @safe pure @nogc unittest 1049 { 1050 import mir.format; 1051 auto str = "-34010447314490204552169750449563978034784726557588085989975288830070948234680"; 1052 auto integer = BigInt!4(str); 1053 auto buffer = stringBuf; 1054 buffer << integer; 1055 assert(buffer.data == str); 1056 } 1057 1058 /// 1059 version(mir_bignum_test) 1060 unittest 1061 { 1062 import mir.test; 1063 import mir.bignum.fixed; 1064 import mir.bignum.low_level_view; 1065 1066 { 1067 auto a = BigInt!4.fromHexString("c39b18a9f06fd8e962d99935cea0707f79a222050aaeaaaed17feb7aa76999d7"); 1068 auto b = UInt!128.fromHexString("f79a222050aaeaaa417fa25a2ac93291"); 1069 1070 // ca3d7e25aebe687b 168dcef32d0bb2f0 1071 auto c = BigInt!4.fromHexString("bf4c87424431d21563f23b1fc00d75ac"); 1072 a %= b; 1073 a.should == c; 1074 a = BigInt!4.fromHexString("c39b18a9f06fd8e962d99935cea0707f79a222050aaeaaaed17feb7aa76999d7"); 1075 a /= b; 1076 assert(a == BigInt!4.fromHexString("ca3d7e25aebe687b7cc1b250b44690fb")); 1077 } 1078 1079 { 1080 auto a = BigInt!4.fromHexString("7fff000080000000000000000000"); 1081 auto b = UInt!128.fromHexString("80000000000000000001"); 1082 1083 auto c = BigInt!4.fromHexString("fffe0000"); 1084 a /= b; 1085 a.should == c; 1086 1087 a = BigInt!4.fromHexString("7fff000080000000000000000000"); 1088 assert((a %= b) == BigInt!4.fromHexString("7fffffffffff00020000")); 1089 } 1090 1091 { 1092 auto a = BigInt!16.fromHexString("76d053cdcc87ec8c9455c375d6a08c799fad73cf07415e70af5dfacaff4bd306647a7cceb98839cce89ae65900938821564fd2af3c9d881c172264bb17e3530ce79b938d5eb7ffec558be43ab5b684978417c5053fb8df63fc65c9efd8b2e86469c53259509eb597f81647930f24ef05a79bfecf04e5ec52414c6a3f7481d533"); 1093 auto b = UInt!128.fromHexString("9c5c1aa6ad7ad18065a3a74598e27bee"); 1094 1095 assert((a /= b) == BigInt!16.fromHexString("c2871f2b07522bda1e63de12850d2208bb242c716b5739d6744ee1d9c937b8d765d3742e18785d08c2405e5c83f3c875d5726d09dfaee29e813675a4f91bfee01e8cbbbca9588325d54cf2a625faffde4d8709e0517f786f609d8ce6997e0e71d2f976ae169b0c4be7a7dba3135af96c")); 1096 a = BigInt!16.fromHexString("76d053cdcc87ec8c9455c375d6a08c799fad73cf07415e70af5dfacaff4bd306647a7cceb98839cce89ae65900938821564fd2af3c9d881c172264bb17e3530ce79b938d5eb7ffec558be43ab5b684978417c5053fb8df63fc65c9efd8b2e86469c53259509eb597f81647930f24ef05a79bfecf04e5ec52414c6a3f7481d533"); 1097 assert((a %= b) == BigInt!16.fromHexString("85d81587a8b62af1874315d26ebf0ecb")); 1098 } 1099 1100 { 1101 auto a = BigInt!4.fromHexString("DEADBEEF"); 1102 auto b = UInt!256.fromHexString("18aeff9fa4aace484a9f8f9002cdf38fa6e53fc0f6c035051dc86931c1c08316"); 1103 1104 assert((a /= b) == 0); 1105 a = BigInt!4.fromHexString("DEADBEEF"); 1106 assert((a %= b) == 0xDEADBEEF); 1107 } 1108 1109 void test(const long av, const long bv) 1110 { 1111 auto a = BigInt!4(av); 1112 const b = BigInt!4(bv); 1113 a /= b; 1114 assert(a == av / bv); 1115 a = BigInt!4(av); 1116 a %= b; 1117 assert(a == av % bv); 1118 } 1119 1120 { 1121 auto av = 0xDEADBEEF; 1122 auto bv = 0xDEAD; 1123 test(+av, +bv); 1124 // test(+av, -bv); 1125 // test(-av, +bv); 1126 // test(+av, +bv); 1127 } 1128 } 1129 1130 /// 1131 version(mir_bignum_test) 1132 unittest 1133 { 1134 import mir.bignum.fixed; 1135 import mir.bignum.low_level_view; 1136 1137 auto a = BigInt!4.fromHexString("4b313b23aa560e1b0985f89cbe6df5460860e39a64ba92b4abdd3ee77e4e05b8"); 1138 auto b = BigInt!4.fromHexString("c39b18a9f06fd8e962d99935cea0707f79a222050aaeaaaed17feb7aa76999d7"); 1139 auto c = BigInt!4.fromHexString("7869dd864619cace5953a09910327b3971413e6aa5f417fa25a2ac93291b941f"); 1140 c.sign = true; 1141 assert(a != b); 1142 assert(a < b); 1143 a -= b; 1144 assert(a.sign); 1145 assert(a == c); 1146 a -= a; 1147 assert(!a.sign); 1148 assert(!a.length); 1149 1150 auto d = BigInt!4.fromHexString("0de1a911c6dc8f90a7169a148e65d22cf34f6a8254ae26362b064f26ac44218a"); 1151 assert((b *= 0x7869dd86) == 0x5c019770); 1152 assert(b == d); 1153 1154 d = BigInt!4.fromHexString("856eeb23e68cc73f2a517448862cdc97e83f9dfa23768296724bf00fda7df32a"); 1155 auto o = b *= UInt!128.fromHexString("f79a222050aaeaaa417fa25a2ac93291"); 1156 assert(o == UInt!128.fromHexString("d6d15b99499b73e68c3331eb0f7bf16")); 1157 assert(b == d); 1158 1159 d = BigInt!4.fromHexString("d"); // initial value 1160 d.mulPow5(60); 1161 c = BigInt!4.fromHexString("81704fcef32d3bd8117effd5c4389285b05d"); 1162 assert(d == c); 1163 1164 d >>= 80; 1165 c = BigInt!4.fromHexString("81704fcef32d3bd8"); 1166 assert(d == c); 1167 1168 c = BigInt!4.fromHexString("c39b18a9f06fd8e962d99935cea0707f79a222050aaeaaaed17feb7aa76999d7"); 1169 d = BigInt!4.fromHexString("9935cea0707f79a222050aaeaaaed17feb7aa76999d700000000000000000000"); 1170 c <<= 80; 1171 assert(d == c); 1172 c >>= 80; 1173 c <<= 84; 1174 d <<= 4; 1175 assert(d == c); 1176 assert(c != b); 1177 b.sign = true; 1178 assert(!c.copyFrom(b.coefficients, b.sign)); 1179 assert(c == b); 1180 b >>= 18; 1181 auto bView = cast(BigIntView!ushort)b.view; 1182 assert(!c.copyFrom(bView.coefficients[0 .. $ - 1], bView.sign)); 1183 assert(c == b); 1184 } 1185 1186 version(mir_bignum_test) 1187 @safe pure @nogc unittest 1188 { 1189 BigInt!4 i = "-0"; 1190 assert(i.coefficients.length == 0); 1191 assert(!i.sign); 1192 assert(cast(long) i == 0); 1193 }