mcs/class/System.Numerics/System.Numerics/BigInteger.cs

   1 /* ****************************************************************************\r
   2  *\r
   3  * Copyright (c) Microsoft Corporation. \r
   4  *\r
   5  * This source code is subject to terms and conditions of the Microsoft Public License. A \r
   6  * copy of the license can be found in the License.html file at the root of this distribution. If \r
   7  * you cannot locate the  Microsoft Public License, please send an email to \r
   8  * dlr@microsoft.com. By using this source code in any fashion, you are agreeing to be bound \r
   9  * by the terms of the Microsoft Public License.\r
  10  *\r
  11  * You must not remove this notice, or any other, from this software.\r
  12  *\r
  13  *\r
  14  * ***************************************************************************/\r
  15 \r
  16 using System;\r
  17 using System.Collections.Generic;\r
  18 using System.Diagnostics;\r
  19 using System.Diagnostics.CodeAnalysis;\r
  20 using System.Globalization;\r
  21 using System.Text;\r
  22 \r
  23 namespace System.Numerics {\r
  24     /// <summary>\r
  25     /// arbitrary precision integers\r
  26     /// </summary>\r
  27     [Serializable]\r
  28     public sealed class BigInteger : IFormattable, IComparable, IConvertible, IEquatable<BigInteger> {\r
  29         private const int BitsPerDigit = 32;\r
  30         private const ulong Base = 0x100000000;\r
  31 \r
  32         // -1 if negative, +1 if positive, 0 if zero.\r
  33         private readonly short sign;\r
  34 \r
  35         // Non-null. data[0] is the least significant 32 bits.\r
  36         private readonly uint[] data;\r
  37 \r
  38         [SuppressMessage("Microsoft.Security", "CA2104:DoNotDeclareReadOnlyMutableReferenceTypes")]\r
  39         public static readonly BigInteger Zero = new BigInteger(0, new uint[0]);\r
  40         [SuppressMessage("Microsoft.Security", "CA2104:DoNotDeclareReadOnlyMutableReferenceTypes")]\r
  41         public static readonly BigInteger One = new BigInteger(+1, new uint[] { 1 });\r
  42         private const int bias = 1075;\r
  43 \r
  44         [CLSCompliant(false)]\r
  45         public static BigInteger Create(ulong v) {\r
  46             return new BigInteger(+1, (uint)v, (uint)(v >> BitsPerDigit));\r
  47         }\r
  48 \r
  49         [CLSCompliant(false)]\r
  50         public static BigInteger Create(uint v) {\r
  51             if (v == 0) return Zero;\r
  52             else if (v == 1) return One;\r
  53             else return new BigInteger(+1, v);\r
  54         }\r
  55 \r
  56         public static BigInteger Create(long v) {\r
  57             ulong x;\r
  58             int s = +1;\r
  59             if (v < 0) {\r
  60                 x = (ulong)-v; s = -1;\r
  61             } else {\r
  62                 x = (ulong)v;\r
  63             }\r
  64 \r
  65             return new BigInteger(s, (uint)x, (uint)(x >> BitsPerDigit));\r
  66         }\r
  67 \r
  68         public static BigInteger Create(int v) {\r
  69             if (v == 0) return Zero;\r
  70             else if (v == 1) return One;\r
  71             else if (v < 0) return new BigInteger(-1, (uint)-v);\r
  72             else return new BigInteger(+1, (uint)v);\r
  73         }\r
  74 \r
  75         private const Int32 DecimalScaleFactorMask = 0x00FF0000;\r
  76         private const Int32 DecimalSignMask = unchecked((Int32)0x80000000);\r
  77 \r
  78         public static BigInteger Create(decimal v) {\r
  79             // First truncate to get scale to 0 and extract bits\r
  80             int[] bits = Decimal.GetBits(Decimal.Truncate(v));\r
  81 \r
  82             Debug.Assert(bits.Length == 4 && (bits[3] & DecimalScaleFactorMask) == 0);\r
  83 \r
  84             int size = 3;\r
  85             while (size > 0 && bits[size - 1] == 0) size--;\r
  86 \r
  87             if (size == 0) {\r
  88                 return BigInteger.Zero;\r
  89             }\r
  90 \r
  91             UInt32[] array = new UInt32[size];\r
  92             array[0] = (UInt32)bits[0];\r
  93             if (size > 1) array[1] = (UInt32)bits[1];\r
  94             if (size > 2) array[2] = (UInt32)bits[2];\r
  95 \r
  96             return new BigInteger(((bits[3] & DecimalSignMask) != 0) ? -1 : +1, array);\r
  97         }\r
  98 \r
  99         /// <summary>\r
 100         /// Create a BigInteger from a little-endian twos-complement byte array\r
 101         /// (inverse of ToByteArray())\r
 102         /// </summary>\r
 103         public static BigInteger Create(byte[] v) {\r
 104             if (v == null)\r
 105                 throw new ArgumentNullException ("v");\r
 106             if (v.Length == 0) return Create(0);\r
 107 \r
 108             int byteCount = v.Length;\r
 109             int unalignedBytes = byteCount % 4;\r
 110             int dwordCount = byteCount / 4 + (unalignedBytes == 0 ? 0 : 1);\r
 111             uint[] data = new uint[dwordCount];\r
 112 \r
 113             bool isNegative = (v[byteCount - 1] & 0x80) == 0x80;\r
 114 \r
 115             bool isZero = true;\r
 116 \r
 117             // Copy all dwords, except but don't do the last one if it's not a full four bytes\r
 118             int curDword, curByte, byteInDword;\r
 119             curByte = 3;\r
 120             for (curDword = 0; curDword < dwordCount - (unalignedBytes == 0 ? 0 : 1); curDword++) {\r
 121                 byteInDword = 0;\r
 122                 while (byteInDword < 4) {\r
 123                     if (v[curByte] != 0x00) isZero = false;\r
 124                     data[curDword] <<= 8;\r
 125                     data[curDword] |= v[curByte];\r
 126                     curByte--;\r
 127                     byteInDword++;\r
 128                 }\r
 129                 curByte += 8;\r
 130             }\r
 131 \r
 132             // Copy the last dword specially if it's not aligned\r
 133             if (unalignedBytes != 0) {\r
 134                 if (isNegative) data[dwordCount - 1] = 0xffffffff;\r
 135                 for (curByte = byteCount - 1; curByte >= byteCount - unalignedBytes; curByte--) {\r
 136                     if (v[curByte] != 0x00) isZero = false;\r
 137                     data[curDword] <<= 8;\r
 138                     data[curDword] |= v[curByte];\r
 139                 }\r
 140             }\r
 141 \r
 142             if (isZero) return Zero;\r
 143 \r
 144             if (isNegative) {\r
 145                 makeTwosComplement(data);\r
 146                 return new BigInteger(-1, data);\r
 147             }\r
 148             return new BigInteger(1, data);\r
 149         }\r
 150 \r
 151 \r
 152         private static bool Negative(byte[] v) {\r
 153             return ((v[7] & 0x80) != 0);\r
 154         }\r
 155 \r
 156         private static ushort Exponent(byte[] v) {\r
 157             return (ushort)((((ushort)(v[7] & 0x7F)) << (ushort)4) | (((ushort)(v[6] & 0xF0)) >> 4));\r
 158         }\r
 159 \r
 160         private static ulong Mantissa(byte[] v) {\r
 161             uint i1 = ((uint)v[0] | ((uint)v[1] << 8) | ((uint)v[2] << 16) | ((uint)v[3] << 24));\r
 162             uint i2 = ((uint)v[4] | ((uint)v[5] << 8) | ((uint)(v[6] & 0xF) << 16));\r
 163 \r
 164             return (ulong)((ulong)i1 | ((ulong)i2 << 32));\r
 165         }\r
 166 \r
 167         public static BigInteger Create(double v) {\r
 168             if (Double.IsNaN(v) || Double.IsInfinity(v)) {\r
 169                 throw new OverflowException();\r
 170             }\r
 171 \r
 172             byte[] bytes = System.BitConverter.GetBytes(v);\r
 173             ulong mantissa = Mantissa(bytes);\r
 174             if (mantissa == 0) {\r
 175                 // 1.0 * 2**exp, we have a power of 2\r
 176                 int exponent = Exponent(bytes);\r
 177                 if (exponent == 0) return Zero;\r
 178 \r
 179                 BigInteger res = Negative(bytes) ? Negate(One) : One;\r
 180                 res = res << (exponent - 0x3ff);\r
 181                 return res;\r
 182             } else {\r
 183                 // 1.mantissa * 2**exp\r
 184                 int exponent = Exponent(bytes);\r
 185                 mantissa |= 0x10000000000000ul;\r
 186                 BigInteger res = BigInteger.Create(mantissa);\r
 187                 res = exponent > bias ? res << (exponent - bias) : res >> (bias - exponent);\r
 188                 return Negative(bytes) ? res * (-1) : res;\r
 189             }\r
 190         }\r
 191 \r
 192         public static implicit operator BigInteger(byte i) {\r
 193             return Create((uint)i);\r
 194         }\r
 195 \r
 196         [CLSCompliant(false)]\r
 197         public static implicit operator BigInteger(sbyte i) {\r
 198             return Create((int)i);\r
 199         }\r
 200 \r
 201         public static implicit operator BigInteger(short i) {\r
 202             return Create((int)i);\r
 203         }\r
 204 \r
 205         [CLSCompliant(false)]\r
 206         public static implicit operator BigInteger(ushort i) {\r
 207             return Create((uint)i);\r
 208         }\r
 209 \r
 210         [CLSCompliant(false)]\r
 211         public static implicit operator BigInteger(uint i) {\r
 212             return Create(i);\r
 213         }\r
 214 \r
 215         public static implicit operator BigInteger(int i) {\r
 216             return Create(i);\r
 217         }\r
 218 \r
 219         [CLSCompliant(false)]\r
 220         public static implicit operator BigInteger(ulong i) {\r
 221             return Create(i);\r
 222         }\r
 223 \r
 224         public static implicit operator BigInteger(long i) {\r
 225             return Create(i);\r
 226         }\r
 227 \r
 228         public static implicit operator BigInteger(decimal i) {\r
 229             return Create(i);\r
 230         }\r
 231 \r
 232         public static explicit operator BigInteger(double self) {\r
 233             return Create(self);\r
 234         }\r
 235 \r
 236         public static explicit operator BigInteger(float self) {\r
 237             return Create((double)self);\r
 238         }\r
 239 \r
 240         public static explicit operator double(BigInteger self) {\r
 241             if (object.ReferenceEquals(self, null)) {\r
 242                 throw new ArgumentNullException("self");\r
 243             }\r
 244             return self.ToFloat64();\r
 245         }\r
 246 \r
 247         public static explicit operator float(BigInteger self) {\r
 248             if (object.ReferenceEquals(self, null)) {\r
 249                 throw new ArgumentNullException("self");\r
 250             }\r
 251             return checked((float)self.ToFloat64());\r
 252         }\r
 253 \r
 254         public static explicit operator decimal(BigInteger self) {\r
 255             decimal res;\r
 256             if (self.AsDecimal(out res)) {\r
 257                 return res;\r
 258             }\r
 259             throw new OverflowException();\r
 260         }\r
 261 \r
 262         public static explicit operator byte(BigInteger self) {\r
 263             int tmp;\r
 264             if (self.AsInt32(out tmp)) {\r
 265                 return checked((byte)tmp);\r
 266             }\r
 267             throw new OverflowException();\r
 268         }\r
 269 \r
 270         [CLSCompliant(false)]\r
 271         public static explicit operator sbyte(BigInteger self) {\r
 272             int tmp;\r
 273             if (self.AsInt32(out tmp)) {\r
 274                 return checked((sbyte)tmp);\r
 275             }\r
 276             throw new OverflowException();\r
 277         }\r
 278 \r
 279         [CLSCompliant(false)]\r
 280         public static explicit operator UInt16(BigInteger self) {\r
 281             int tmp;\r
 282             if (self.AsInt32(out tmp)) {\r
 283                 return checked((UInt16)tmp);\r
 284             }\r
 285             throw new OverflowException();\r
 286         }\r
 287 \r
 288         public static explicit operator Int16(BigInteger self) {\r
 289             int tmp;\r
 290             if (self.AsInt32(out tmp)) {\r
 291                 return checked((Int16)tmp);\r
 292             }\r
 293             throw new OverflowException();\r
 294         }\r
 295 \r
 296         [CLSCompliant(false)]\r
 297         public static explicit operator UInt32(BigInteger self) {\r
 298             uint tmp;\r
 299             if (self.AsUInt32(out tmp)) {\r
 300                 return tmp;\r
 301             }\r
 302             throw new OverflowException();\r
 303         }\r
 304 \r
 305         public static explicit operator Int32(BigInteger self) {\r
 306             int tmp;\r
 307             if (self.AsInt32(out tmp)) {\r
 308                 return tmp;\r
 309             }\r
 310             throw new OverflowException();\r
 311         }\r
 312 \r
 313         public static explicit operator Int64(BigInteger self) {\r
 314             long tmp;\r
 315             if (self.AsInt64(out tmp)) {\r
 316                 return tmp;\r
 317             }\r
 318             throw new OverflowException();\r
 319         }\r
 320 \r
 321         [CLSCompliant(false)]\r
 322         public static explicit operator UInt64(BigInteger self) {\r
 323             ulong tmp;\r
 324             if (self.AsUInt64(out tmp)) {\r
 325                 return tmp;\r
 326             }\r
 327             throw new OverflowException();\r
 328         }\r
 329 \r
 330         public BigInteger(BigInteger copy) {\r
 331             if (object.ReferenceEquals(copy, null)) {\r
 332                 throw new ArgumentNullException("copy");\r
 333             }\r
 334             this.sign = copy.sign;\r
 335             this.data = copy.data;\r
 336         }\r
 337 \r
 338         [CLSCompliant(false)]\r
 339         public BigInteger(int sign, params uint[] data) {\r
 340             if (data == null)\r
 341                 throw new ArgumentNullException ("data");\r
 342             if (!(sign >= -1 && sign <= +1))\r
 343                 throw new ArgumentException ("sign");\r
 344             int length = GetLength(data);\r
 345             if (!(length == 0 || sign != 0))\r
 346                 throw new ArgumentException ("sign");\r
 347             \r
 348             this.data = data;\r
 349             this.sign = (short)(length == 0 ? 0 : sign);\r
 350         }\r
 351 \r
 352         /// <summary>\r
 353         /// Return the magnitude of this BigInteger as an array of zero or more uints.\r
 354         /// Element zero is the value of the least significant four bytes, element one is\r
 355         /// the value of the four next most significant bytes, etc.\r
 356         /// \r
 357         /// The returned data is the unsigned magnitude of the number. To determine the sign,\r
 358         /// use GetSign().\r
 359         /// \r
 360         /// It is guaranteed that the highest element of the returned array is never zero.\r
 361         /// This means that if the value of this BigInteger is zero, a zero-length array\r
 362         /// is returned.\r
 363         /// </summary>\r
 364         [CLSCompliant(false)]\r
 365         public uint[] GetWords() {\r
 366             if (sign == 0) return new uint[0];\r
 367             int w = GetWordCount();\r
 368             uint[] bits = new uint[w];\r
 369             Array.Copy(data, bits, w);\r
 370             return bits;\r
 371         }\r
 372 \r
 373         [CLSCompliant(false)]\r
 374         public uint GetWord(int index) {\r
 375             return data[index];\r
 376         }\r
 377 \r
 378         public int GetBitCount() {\r
 379             if (IsZero()) {\r
 380                 return 0;\r
 381             }\r
 382             int w = GetWordCount() - 1;\r
 383             uint b = data[w];\r
 384             Debug.Assert(b > 0);\r
 385             int result = w * 32;\r
 386             do {\r
 387                 b >>= 1;\r
 388                 result++;\r
 389             } while (b > 0);\r
 390 \r
 391             return result;\r
 392         }\r
 393 \r
 394         public int GetByteCount() {\r
 395             return (GetBitCount() + 7) / 8;\r
 396         }\r
 397 \r
 398         /// <summary>\r
 399         /// Return the sign of this BigInteger: -1, 0, or 1.\r
 400         /// </summary>\r
 401         public short Sign {\r
 402             get {\r
 403                 return sign;\r
 404             }\r
 405         }\r
 406 \r
 407         public bool AsInt64(out long ret) {\r
 408             ret = 0;\r
 409             if (sign == 0) return true;\r
 410             if (GetWordCount() > 2) return false;\r
 411             if (data.Length == 1) {\r
 412                 ret = sign * (long)data[0];\r
 413                 return true;\r
 414             }\r
 415             ulong tmp = (((ulong)data[1]) << 32 | (ulong)data[0]);\r
 416             if (tmp > 0x8000000000000000) return false;\r
 417             if (tmp == 0x8000000000000000 && sign == 1) return false;\r
 418             ret = ((long)tmp) * sign;\r
 419             return true;\r
 420         }\r
 421 \r
 422         [CLSCompliant(false)]\r
 423         public bool AsUInt32(out uint ret) {\r
 424             ret = 0;\r
 425             if (sign == 0) return true;\r
 426             if (sign < 0) return false;\r
 427             if (GetWordCount() > 1) return false;\r
 428             ret = data[0];\r
 429             return true;\r
 430         }\r
 431 \r
 432         [CLSCompliant(false)]\r
 433         public bool AsUInt64(out ulong ret) {\r
 434             ret = 0;\r
 435             if (sign == 0) return true;\r
 436             if (sign < 0) return false;\r
 437             if (GetWordCount() > 2) return false;\r
 438             ret = (ulong)data[0];\r
 439             if (data.Length > 1) {\r
 440                 ret |= ((ulong)data[1]) << 32;\r
 441             }\r
 442             return true;\r
 443         }\r
 444 \r
 445         public bool AsInt32(out int ret) {\r
 446             ret = 0;\r
 447             if (sign == 0) return true;\r
 448             if (GetWordCount() > 1) return false;\r
 449             if (data[0] > 0x80000000) return false;\r
 450             if (data[0] == 0x80000000 && sign == 1) return false;\r
 451             ret = (int)data[0];\r
 452             ret *= sign;\r
 453             return true;\r
 454         }\r
 455 \r
 456         public bool AsDecimal(out Decimal ret) {\r
 457             if (sign == 0) {\r
 458                 ret = Decimal.Zero;\r
 459                 return true;\r
 460             }\r
 461 \r
 462             int length = GetWordCount();\r
 463             if (length > 3) {\r
 464                 ret = default(Decimal);\r
 465                 return false;\r
 466             }\r
 467 \r
 468             int lo = 0, mi = 0, hi = 0;\r
 469             if (length > 2) hi = (Int32)data[2];\r
 470             if (length > 1) mi = (Int32)data[1];\r
 471             if (length > 0) lo = (Int32)data[0];\r
 472 \r
 473             ret = new Decimal(lo, mi, hi, sign < 0, 0);\r
 474             return true;\r
 475         }\r
 476 \r
 477 \r
 478         [CLSCompliant(false)]\r
 479         public uint ToUInt32() {\r
 480             uint ret;\r
 481             if (AsUInt32(out ret)) return ret;\r
 482             throw new OverflowException("big integer won't fit into uint");\r
 483         }\r
 484 \r
 485         public int ToInt32() {\r
 486             int ret;\r
 487             if (AsInt32(out ret)) return ret;\r
 488             throw new OverflowException("big integer won't fit into int");\r
 489         }\r
 490 \r
 491         public decimal ToDecimal() {\r
 492             decimal ret;\r
 493             if (AsDecimal(out ret)) return ret;\r
 494             throw new OverflowException("big integer won't fit into decimal");\r
 495         }\r
 496 \r
 497         [CLSCompliant(false)]\r
 498         public ulong ToUInt64() {\r
 499             ulong ret;\r
 500             if (AsUInt64(out ret)) return ret;\r
 501             throw new OverflowException("big integer won't fit into ulong");\r
 502         }\r
 503 \r
 504         public long ToInt64() {\r
 505             long ret;\r
 506             if (AsInt64(out ret)) return ret;\r
 507             throw new OverflowException("big integer won't fit into long");\r
 508         }\r
 509 \r
 510         public bool TryToFloat64(out double result) {\r
 511             return double.TryParse(ToString(10),\r
 512                 System.Globalization.NumberStyles.Number,\r
 513                 System.Globalization.CultureInfo.InvariantCulture.NumberFormat,\r
 514                 out result);\r
 515         }\r
 516 \r
 517         public double ToFloat64() {\r
 518             return double.Parse(\r
 519                 ToString(10),\r
 520                 System.Globalization.CultureInfo.InvariantCulture.NumberFormat\r
 521                 );\r
 522         }\r
 523 \r
 524         public int GetWordCount() {\r
 525             return GetLength(data);\r
 526         }\r
 527 \r
 528         private static int GetLength(uint[] data) {\r
 529             int ret = data.Length - 1;\r
 530             while (ret >= 0 && data[ret] == 0) ret--;\r
 531             return ret + 1;\r
 532         }\r
 533 \r
 534 \r
 535         private static uint[] copy(uint[] v) {\r
 536             uint[] ret = new uint[v.Length];\r
 537             Array.Copy(v, ret, v.Length);\r
 538             return ret;\r
 539         }\r
 540 \r
 541         private static uint[] resize(uint[] v, int len) {\r
 542             if (v.Length == len) return v;\r
 543             uint[] ret = new uint[len];\r
 544             int n = System.Math.Min(v.Length, len);\r
 545             for (int i = 0; i < n; i++) {\r
 546                 ret[i] = v[i];\r
 547             }\r
 548             return ret;\r
 549         }\r
 550 \r
 551         private static uint[] InternalAdd(uint[] x, int xl, uint[] y, int yl) {\r
 552             Debug.Assert(xl >= yl);\r
 553             uint[] z = new uint[xl];\r
 554 \r
 555             int i;\r
 556             ulong sum = 0;\r
 557             for (i = 0; i < yl; i++) {\r
 558                 sum = sum + x[i] + y[i];\r
 559                 z[i] = (uint)sum;\r
 560                 sum >>= BitsPerDigit;\r
 561             }\r
 562 \r
 563             for (; i < xl && sum != 0; i++) {\r
 564                 sum = sum + x[i];\r
 565                 z[i] = (uint)sum;\r
 566                 sum >>= BitsPerDigit;\r
 567             }\r
 568             if (sum != 0) {\r
 569                 z = resize(z, xl + 1);\r
 570                 z[i] = (uint)sum;\r
 571             } else {\r
 572                 for (; i < xl; i++) {\r
 573                     z[i] = x[i];\r
 574                 }\r
 575             }\r
 576             return z;\r
 577         }\r
 578 \r
 579         private static uint[] sub(uint[] x, int xl, uint[] y, int yl) {\r
 580             Debug.Assert(xl >= yl);\r
 581             uint[] z = new uint[xl];\r
 582 \r
 583             int i;\r
 584             bool borrow = false;\r
 585             for (i = 0; i < yl; i++) {\r
 586                 uint xi = x[i];\r
 587                 uint yi = y[i];\r
 588                 if (borrow) {\r
 589                     if (xi == 0) {\r
 590                         xi = 0xffffffff;\r
 591                         borrow = true;\r
 592                     } else {\r
 593                         xi -= 1;\r
 594                         borrow = false;\r
 595                     }\r
 596                 }\r
 597                 if (yi > xi) borrow = true;\r
 598                 z[i] = xi - yi;\r
 599             }\r
 600 \r
 601             if (borrow) {\r
 602                 for (; i < xl; i++) {\r
 603                     uint xi = x[i];\r
 604                     z[i] = xi - 1;\r
 605                     if (xi != 0) { i++; break; }\r
 606                 }\r
 607             }\r
 608             for (; i < xl; i++) {\r
 609                 z[i] = x[i];\r
 610             }\r
 611             return z;  // may have leading zeros\r
 612         }\r
 613 \r
 614         private static uint[] add0(uint[] x, int xl, uint[] y, int yl) {\r
 615             if (xl >= yl) return InternalAdd(x, xl, y, yl);\r
 616             else return InternalAdd(y, yl, x, xl);\r
 617         }\r
 618 \r
 619         public static int Compare(BigInteger x, BigInteger y) {\r
 620             if (object.ReferenceEquals(x, null)) {\r
 621                 throw new ArgumentNullException("x");\r
 622             }\r
 623             if (object.ReferenceEquals(y, null)) {\r
 624                 throw new ArgumentNullException("y");\r
 625             }\r
 626             if (x.sign == y.sign) {\r
 627                 int xl = x.GetWordCount();\r
 628                 int yl = y.GetWordCount();\r
 629                 if (xl == yl) {\r
 630                     for (int i = xl - 1; i >= 0; i--) {\r
 631                         if (x.data[i] == y.data[i]) continue;\r
 632                         return x.data[i] > y.data[i] ? x.sign : -x.sign;\r
 633                     }\r
 634                     return 0;\r
 635                 } else {\r
 636                     return xl > yl ? +x.sign : -x.sign;\r
 637                 }\r
 638             } else {\r
 639                 return x.sign > y.sign ? +1 : -1;\r
 640             }\r
 641         }\r
 642 \r
 643         public static bool operator ==(BigInteger x, int y) {\r
 644             return x == (BigInteger)y;\r
 645         }\r
 646 \r
 647         public static bool operator !=(BigInteger x, int y) {\r
 648             return !(x == y);\r
 649         }\r
 650 \r
 651         [System.Diagnostics.CodeAnalysis.SuppressMessage("Microsoft.Design", "CA1065:DoNotRaiseExceptionsInUnexpectedLocations")] // TODO: fix\r
 652         public static bool operator ==(BigInteger x, double y) {\r
 653             if (object.ReferenceEquals(x, null)) {\r
 654                 throw new ArgumentNullException("x");\r
 655             }\r
 656 \r
 657             // we can hold all double values, but not all double values\r
 658             // can hold BigInteger values, and we may lose precision.  Convert\r
 659             // the double to a big int, then compare.\r
 660 \r
 661             if ((y % 1) != 0) return false;  // not a whole number, can't be equal\r
 662 \r
 663             return x == BigInteger.Create(y);\r
 664         }\r
 665 \r
 666         public static bool operator ==(double x, BigInteger y) {\r
 667             return y == x;\r
 668         }\r
 669 \r
 670         public static bool operator !=(BigInteger x, double y) {\r
 671             return !(x == y);\r
 672         }\r
 673 \r
 674         public static bool operator !=(double x, BigInteger y) {\r
 675             return !(x == y);\r
 676         }\r
 677 \r
 678 \r
 679         public static bool operator ==(BigInteger x, BigInteger y) {\r
 680             return Compare(x, y) == 0;\r
 681         }\r
 682 \r
 683         public static bool operator !=(BigInteger x, BigInteger y) {\r
 684             return Compare(x, y) != 0;\r
 685         }\r
 686         public static bool operator <(BigInteger x, BigInteger y) {\r
 687             return Compare(x, y) < 0;\r
 688         }\r
 689         public static bool operator <=(BigInteger x, BigInteger y) {\r
 690             return Compare(x, y) <= 0;\r
 691         }\r
 692         public static bool operator >(BigInteger x, BigInteger y) {\r
 693             return Compare(x, y) > 0;\r
 694         }\r
 695         public static bool operator >=(BigInteger x, BigInteger y) {\r
 696             return Compare(x, y) >= 0;\r
 697         }\r
 698 \r
 699         public static BigInteger Add(BigInteger x, BigInteger y) {\r
 700             return x + y;\r
 701         }\r
 702 \r
 703         public static BigInteger operator +(BigInteger x, BigInteger y) {\r
 704             if (object.ReferenceEquals(x, null)) {\r
 705                 throw new ArgumentNullException("x");\r
 706             }\r
 707             if (object.ReferenceEquals(y, null)) {\r
 708                 throw new ArgumentNullException("y");\r
 709             }\r
 710 \r
 711             if (x.sign == y.sign) {\r
 712                 return new BigInteger(x.sign, add0(x.data, x.GetWordCount(), y.data, y.GetWordCount()));\r
 713             } else {\r
 714                 return x - new BigInteger(-y.sign, y.data);  //??? performance issue\r
 715             }\r
 716         }\r
 717 \r
 718         public static BigInteger Subtract(BigInteger x, BigInteger y) {\r
 719             return x - y;\r
 720         }\r
 721 \r
 722         public static BigInteger operator -(BigInteger x, BigInteger y) {\r
 723             int c = Compare(x, y);\r
 724             if (c == 0) return Zero;\r
 725 \r
 726             if (x.sign == y.sign) {\r
 727                 uint[] z;\r
 728                 switch (c * x.sign) {\r
 729                     case +1:\r
 730                         z = sub(x.data, x.GetWordCount(), y.data, y.GetWordCount());\r
 731                         break;\r
 732                     case -1:\r
 733                         z = sub(y.data, y.GetWordCount(), x.data, x.GetWordCount());\r
 734                         break;\r
 735                     default:\r
 736                         return Zero;\r
 737                 }\r
 738                 return new BigInteger(c, z);\r
 739             } else {\r
 740                 uint[] z = add0(x.data, x.GetWordCount(), y.data, y.GetWordCount());\r
 741                 return new BigInteger(c, z);\r
 742             }\r
 743         }\r
 744 \r
 745         public static BigInteger Multiply(BigInteger x, BigInteger y) {\r
 746             return x * y;\r
 747         }\r
 748 \r
 749         public static BigInteger operator *(BigInteger x, BigInteger y) {\r
 750             if (object.ReferenceEquals(x, null)) {\r
 751                 throw new ArgumentNullException("x");\r
 752             }\r
 753             if (object.ReferenceEquals(y, null)) {\r
 754                 throw new ArgumentNullException("y");\r
 755             }\r
 756             int xl = x.GetWordCount();\r
 757             int yl = y.GetWordCount();\r
 758             int zl = xl + yl;\r
 759             uint[] xd = x.data, yd = y.data, zd = new uint[zl];\r
 760 \r
 761             for (int xi = 0; xi < xl; xi++) {\r
 762                 uint xv = xd[xi];\r
 763                 int zi = xi;\r
 764                 ulong carry = 0;\r
 765                 for (int yi = 0; yi < yl; yi++) {\r
 766                     carry = carry + ((ulong)xv) * yd[yi] + zd[zi];\r
 767                     zd[zi++] = (uint)carry;\r
 768                     carry >>= BitsPerDigit;\r
 769                 }\r
 770                 while (carry != 0) {\r
 771                     carry += zd[zi];\r
 772                     zd[zi++] = (uint)carry;\r
 773                     carry >>= BitsPerDigit;\r
 774                 }\r
 775             }\r
 776 \r
 777             return new BigInteger(x.sign * y.sign, zd);\r
 778         }\r
 779 \r
 780         public static BigInteger Divide(BigInteger x, BigInteger y) {\r
 781             return x / y;\r
 782         }\r
 783 \r
 784         public static BigInteger operator /(BigInteger x, BigInteger y) {\r
 785             BigInteger dummy;\r
 786             return DivRem(x, y, out dummy);\r
 787         }\r
 788 \r
 789         public static BigInteger Mod(BigInteger x, BigInteger y) {\r
 790             return x % y;\r
 791         }\r
 792 \r
 793         public static BigInteger operator %(BigInteger x, BigInteger y) {\r
 794             BigInteger ret;\r
 795             DivRem(x, y, out ret);\r
 796             return ret;\r
 797         }\r
 798 \r
 799         private static int GetNormalizeShift(uint value) {\r
 800             int shift = 0;\r
 801 \r
 802             if ((value & 0xFFFF0000) == 0) { value <<= 16; shift += 16; }\r
 803             if ((value & 0xFF000000) == 0) { value <<= 8; shift += 8; }\r
 804             if ((value & 0xF0000000) == 0) { value <<= 4; shift += 4; }\r
 805             if ((value & 0xC0000000) == 0) { value <<= 2; shift += 2; }\r
 806             if ((value & 0x80000000) == 0) { value <<= 1; shift += 1; }\r
 807 \r
 808             return shift;\r
 809         }\r
 810 \r
 811         [Conditional("DEBUG")]\r
 812         [SuppressMessage("Microsoft.Usage", "CA1806:DoNotIgnoreMethodResults", MessageId = "Microsoft.Scripting.Math.BigInteger")]\r
 813         private static void TestNormalize(uint[] u, uint[] un, int shift) {\r
 814             BigInteger i = new BigInteger(1, u);\r
 815             BigInteger j = new BigInteger(1, un);\r
 816             BigInteger k = j >> shift;\r
 817 \r
 818             Debug.Assert(i == k);\r
 819         }\r
 820 \r
 821         [Conditional("DEBUG")]\r
 822         private static void TestDivisionStep(uint[] un, uint[] vn, uint[] q, uint[] u, uint[] v) {\r
 823             int n = GetLength(v);\r
 824             int shift = GetNormalizeShift(v[n - 1]);\r
 825 \r
 826             BigInteger uni = new BigInteger(1, un);\r
 827             BigInteger vni = new BigInteger(1, vn);\r
 828             BigInteger qi = new BigInteger(1, q);\r
 829             BigInteger ui = new BigInteger(1, u);\r
 830 \r
 831             BigInteger expected = vni * qi + uni;\r
 832             BigInteger usi = ui << shift;\r
 833 \r
 834             Debug.Assert(expected == usi);\r
 835         }\r
 836 \r
 837         [Conditional("DEBUG")]\r
 838         [SuppressMessage("Microsoft.Usage", "CA1806:DoNotIgnoreMethodResults", MessageId = "Microsoft.Scripting.Math.BigInteger")]\r
 839         private static void TestResult(uint[] u, uint[] v, uint[] q, uint[] r) {\r
 840             BigInteger ui = new BigInteger(1, u);\r
 841             BigInteger vi = new BigInteger(1, v);\r
 842             BigInteger qi = new BigInteger(1, q);\r
 843             BigInteger ri = new BigInteger(1, r);\r
 844 \r
 845             BigInteger viqi = vi * qi;\r
 846             BigInteger expected = viqi + ri;\r
 847             Debug.Assert(ui == expected);\r
 848             Debug.Assert(ri < vi);\r
 849         }\r
 850 \r
 851         private static void Normalize(uint[] u, int l, uint[] un, int shift) {\r
 852             Debug.Assert(un.Length == l || un.Length == l + 1);\r
 853             Debug.Assert(un.Length == l + 1 || ((u[l - 1] << shift) >> shift) == u[l - 1]);\r
 854             Debug.Assert(0 <= shift && shift < 32);\r
 855 \r
 856             uint carry = 0;\r
 857             int i;\r
 858             if (shift > 0) {\r
 859                 int rshift = BitsPerDigit - shift;\r
 860                 for (i = 0; i < l; i++) {\r
 861                     uint ui = u[i];\r
 862                     un[i] = (ui << shift) | carry;\r
 863                     carry = ui >> rshift;\r
 864                 }\r
 865             } else {\r
 866                 for (i = 0; i < l; i++) {\r
 867                     un[i] = u[i];\r
 868                 }\r
 869             }\r
 870 \r
 871             while (i < un.Length) {\r
 872                 un[i++] = 0;\r
 873             }\r
 874 \r
 875             if (carry != 0) {\r
 876                 Debug.Assert(l == un.Length - 1);\r
 877                 un[l] = carry;\r
 878             }\r
 879 \r
 880             TestNormalize(u, un, shift);\r
 881         }\r
 882 \r
 883         private static void Unnormalize(uint[] un, out uint[] r, int shift) {\r
 884             Debug.Assert(0 <= shift && shift < 32);\r
 885 \r
 886             int length = GetLength(un);\r
 887             r = new uint[length];\r
 888 \r
 889             if (shift > 0) {\r
 890                 int lshift = 32 - shift;\r
 891                 uint carry = 0;\r
 892                 for (int i = length - 1; i >= 0; i--) {\r
 893                     uint uni = un[i];\r
 894                     r[i] = (uni >> shift) | carry;\r
 895                     carry = (uni << lshift);\r
 896                 }\r
 897             } else {\r
 898                 for (int i = 0; i < length; i++) {\r
 899                     r[i] = un[i];\r
 900                 }\r
 901             }\r
 902 \r
 903             TestNormalize(r, un, shift);\r
 904         }\r
 905 \r
 906         private static void DivModUnsigned(uint[] u, uint[] v, out uint[] q, out uint[] r) {\r
 907             int m = GetLength(u);\r
 908             int n = GetLength(v);\r
 909 \r
 910             if (n <= 1) {\r
 911                 if (n == 0) {\r
 912                     throw new DivideByZeroException();\r
 913                 }\r
 914 \r
 915                 //  Divide by single digit\r
 916                 //\r
 917                 ulong rem = 0;\r
 918                 uint v0 = v[0];\r
 919                 q = new uint[m];\r
 920                 r = new uint[1];\r
 921 \r
 922                 for (int j = m - 1; j >= 0; j--) {\r
 923                     rem *= Base;\r
 924                     rem += u[j];\r
 925 \r
 926                     ulong div = rem / v0;\r
 927                     rem -= div * v0;\r
 928                     q[j] = (uint)div;\r
 929                 }\r
 930                 r[0] = (uint)rem;\r
 931             } else if (m >= n) {\r
 932                 int shift = GetNormalizeShift(v[n - 1]);\r
 933 \r
 934                 uint[] un = new uint[m + 1];\r
 935                 uint[] vn = new uint[n];\r
 936 \r
 937                 Normalize(u, m, un, shift);\r
 938                 Normalize(v, n, vn, shift);\r
 939 \r
 940                 q = new uint[m - n + 1];\r
 941                 r = null;\r
 942 \r
 943                 TestDivisionStep(un, vn, q, u, v);\r
 944 \r
 945                 //  Main division loop\r
 946                 //\r
 947                 for (int j = m - n; j >= 0; j--) {\r
 948                     ulong rr, qq;\r
 949                     int i;\r
 950 \r
 951                     rr = Base * un[j + n] + un[j + n - 1];\r
 952                     qq = rr / vn[n - 1];\r
 953                     rr -= qq * vn[n - 1];\r
 954 \r
 955                     Debug.Assert((Base * un[j + n] + un[j + n - 1]) == qq * vn[n - 1] + rr);\r
 956 \r
 957                     for (; ; ) {\r
 958                         // Estimate too big ?\r
 959                         //\r
 960                         if ((qq >= Base) || (qq * vn[n - 2] > (rr * Base + un[j + n - 2]))) {\r
 961                             qq--;\r
 962                             rr += (ulong)vn[n - 1];\r
 963                             if (rr < Base) continue;\r
 964                         }\r
 965                         break;\r
 966                     }\r
 967 \r
 968                     Debug.Assert((Base * un[j + n] + un[j + n - 1]) == qq * vn[n - 1] + rr);\r
 969 \r
 970                     //  Multiply and subtract\r
 971                     //\r
 972                     long b = 0;\r
 973                     long t = 0;\r
 974                     for (i = 0; i < n; i++) {\r
 975                         ulong p = vn[i] * qq;\r
 976                         t = (long)un[i + j] - (long)(uint)p - b;\r
 977                         un[i + j] = (uint)t;\r
 978                         p >>= 32;\r
 979                         t >>= 32;\r
 980                         Debug.Assert(t == 0 || t == -1 || t == -2);\r
 981                         b = (long)p - t;\r
 982                     }\r
 983                     t = (long)un[j + n] - b;\r
 984                     un[j + n] = (uint)t;\r
 985 \r
 986                     //  Store the calculated value\r
 987                     //\r
 988                     q[j] = (uint)qq;\r
 989 \r
 990                     //  Add back vn[0..n] to un[j..j+n]\r
 991                     //\r
 992                     if (t < 0) {\r
 993                         q[j]--;\r
 994                         ulong c = 0;\r
 995                         for (i = 0; i < n; i++) {\r
 996                             c = (ulong)vn[i] + un[j + i] + c;\r
 997                             un[j + i] = (uint)c;\r
 998                             c >>= 32;\r
 999                         }\r
1000                         c += (ulong)un[j + n];\r
1001                         un[j + n] = (uint)c;\r
1002                     }\r
1003 \r
1004                     TestDivisionStep(un, vn, q, u, v);\r
1005                 }\r
1006 \r
1007                 Unnormalize(un, out r, shift);\r
1008 \r
1009                 //  Test normalized value ... Call TestNormalize\r
1010                 //  only pass the values in different order.\r
1011                 //\r
1012                 TestNormalize(r, un, shift);\r
1013             } else {\r
1014                 q = new uint[] { 0 };\r
1015                 r = u;\r
1016             }\r
1017 \r
1018             TestResult(u, v, q, r);\r
1019         }\r
1020 \r
1021         public static BigInteger DivRem(BigInteger x, BigInteger y, out BigInteger remainder) {\r
1022             if (object.ReferenceEquals(x, null)) {\r
1023                 throw new ArgumentNullException("x");\r
1024             }\r
1025             if (object.ReferenceEquals(y, null)) {\r
1026                 throw new ArgumentNullException("y");\r
1027             }\r
1028 \r
1029             uint[] q;\r
1030             uint[] r;\r
1031 \r
1032             DivModUnsigned(x.data, y.data, out q, out r);\r
1033 \r
1034             remainder = new BigInteger(x.sign, r);\r
1035             return new BigInteger(x.sign * y.sign, q);\r
1036         }\r
1037 \r
1038         private static uint extend(uint v, ref bool seenNonZero) {\r
1039             if (seenNonZero) {\r
1040                 return ~v;\r
1041             } else {\r
1042                 if (v == 0) {\r
1043                     return 0;\r
1044                 } else {\r
1045                     seenNonZero = true;\r
1046                     return ~v + 1;\r
1047                 }\r
1048             }\r
1049         }\r
1050 \r
1051         private static uint getOne(bool isNeg, uint[] data, int i, ref bool seenNonZero) {\r
1052             if (i < data.Length) {\r
1053                 uint ret = data[i];\r
1054                 return isNeg ? extend(ret, ref seenNonZero) : ret;\r
1055             } else {\r
1056                 return isNeg ? uint.MaxValue : 0;\r
1057             }\r
1058         }\r
1059 \r
1060         /// <summary>\r
1061         /// Do an in-place twos complement of d and also return the result.\r
1062         /// </summary>\r
1063         private static uint[] makeTwosComplement(uint[] d) {\r
1064             // first do complement and +1 as long as carry is needed\r
1065             int i = 0;\r
1066             uint v = 0;\r
1067             for (; i < d.Length; i++) {\r
1068                 v = ~d[i] + 1;\r
1069                 d[i] = v;\r
1070                 if (v != 0) { i++; break; }\r
1071             }\r
1072 \r
1073             if (v != 0) {\r
1074                 // now ones complement is sufficient\r
1075                 for (; i < d.Length; i++) {\r
1076                     d[i] = ~d[i];\r
1077                 }\r
1078             } else {\r
1079                 //??? this is weird\r
1080                 d = resize(d, d.Length + 1);\r
1081                 d[d.Length - 1] = 1;\r
1082             }\r
1083             return d;\r
1084         }\r
1085 \r
1086         public static BigInteger BitwiseAnd(BigInteger x, BigInteger y) {\r
1087             return x & y;\r
1088         }\r
1089 \r
1090         public static BigInteger operator &(BigInteger x, BigInteger y) {\r
1091             if (object.ReferenceEquals(x, null)) {\r
1092                 throw new ArgumentNullException("x");\r
1093             }\r
1094             if (object.ReferenceEquals(y, null)) {\r
1095                 throw new ArgumentNullException("y");\r
1096             }\r
1097             int xl = x.GetWordCount(), yl = y.GetWordCount();\r
1098             uint[] xd = x.data, yd = y.data;\r
1099 \r
1100             int zl = System.Math.Max(xl, yl);\r
1101             uint[] zd = new uint[zl];\r
1102 \r
1103             bool negx = x.sign == -1, negy = y.sign == -1;\r
1104             bool seenNonZeroX = false, seenNonZeroY = false;\r
1105             for (int i = 0; i < zl; i++) {\r
1106                 uint xu = getOne(negx, xd, i, ref seenNonZeroX);\r
1107                 uint yu = getOne(negy, yd, i, ref seenNonZeroY);\r
1108                 zd[i] = xu & yu;\r
1109             }\r
1110 \r
1111             if (negx && negy) {\r
1112 \r
1113                 return new BigInteger(-1, makeTwosComplement(zd));\r
1114             } else if (negx || negy) {\r
1115                 return new BigInteger(+1, zd);\r
1116             } else {\r
1117                 return new BigInteger(+1, zd);\r
1118             }\r
1119         }\r
1120 \r
1121         public static BigInteger BitwiseOr(BigInteger x, BigInteger y) {\r
1122             return x | y;\r
1123         }\r
1124 \r
1125         public static BigInteger operator |(BigInteger x, BigInteger y) {\r
1126             if (object.ReferenceEquals(x, null)) {\r
1127                 throw new ArgumentNullException("x");\r
1128             }\r
1129             if (object.ReferenceEquals(y, null)) {\r
1130                 throw new ArgumentNullException("y");\r
1131             }\r
1132             int xl = x.GetWordCount(), yl = y.GetWordCount();\r
1133             uint[] xd = x.data, yd = y.data;\r
1134 \r
1135             int zl = System.Math.Max(xl, yl);\r
1136             uint[] zd = new uint[zl];\r
1137 \r
1138             bool negx = x.sign == -1, negy = y.sign == -1;\r
1139             bool seenNonZeroX = false, seenNonZeroY = false;\r
1140             for (int i = 0; i < zl; i++) {\r
1141                 uint xu = getOne(negx, xd, i, ref seenNonZeroX);\r
1142                 uint yu = getOne(negy, yd, i, ref seenNonZeroY);\r
1143                 zd[i] = xu | yu;\r
1144             }\r
1145 \r
1146             if (negx && negy) {\r
1147                 return new BigInteger(-1, makeTwosComplement(zd));\r
1148             } else if (negx || negy) {\r
1149                 return new BigInteger(-1, makeTwosComplement(zd));\r
1150             } else {\r
1151                 return new BigInteger(+1, zd);\r
1152             }\r
1153         }\r
1154 \r
1155         public static BigInteger Xor(BigInteger x, BigInteger y) {\r
1156             return x ^ y;\r
1157         }\r
1158 \r
1159         public static BigInteger operator ^(BigInteger x, BigInteger y) {\r
1160             if (object.ReferenceEquals(x, null)) {\r
1161                 throw new ArgumentNullException("x");\r
1162             }\r
1163             if (object.ReferenceEquals(y, null)) {\r
1164                 throw new ArgumentNullException("y");\r
1165             }\r
1166             int xl = x.GetWordCount(), yl = y.GetWordCount();\r
1167             uint[] xd = x.data, yd = y.data;\r
1168 \r
1169             int zl = System.Math.Max(xl, yl);\r
1170             uint[] zd = new uint[zl];\r
1171 \r
1172             bool negx = x.sign == -1, negy = y.sign == -1;\r
1173             bool seenNonZeroX = false, seenNonZeroY = false;\r
1174             for (int i = 0; i < zl; i++) {\r
1175                 uint xu = getOne(negx, xd, i, ref seenNonZeroX);\r
1176                 uint yu = getOne(negy, yd, i, ref seenNonZeroY);\r
1177                 zd[i] = xu ^ yu;\r
1178             }\r
1179 \r
1180             if (negx && negy) {\r
1181                 return new BigInteger(+1, zd);\r
1182             } else if (negx || negy) {\r
1183                 return new BigInteger(-1, makeTwosComplement(zd));\r
1184             } else {\r
1185                 return new BigInteger(+1, zd);\r
1186             }\r
1187         }\r
1188 \r
1189         public static BigInteger LeftShift(BigInteger x, int shift) {\r
1190             return x << shift;\r
1191         }\r
1192 \r
1193         public static BigInteger operator <<(BigInteger x, int shift) {\r
1194             if (object.ReferenceEquals(x, null)) {\r
1195                 throw new ArgumentNullException("x");\r
1196             }\r
1197             if (shift == 0) return x;\r
1198             else if (shift < 0) return x >> -shift;\r
1199 \r
1200             int digitShift = shift / BitsPerDigit;\r
1201             int smallShift = shift - (digitShift * BitsPerDigit);\r
1202 \r
1203             int xl = x.GetWordCount();\r
1204             uint[] xd = x.data;\r
1205             int zl = xl + digitShift + 1;\r
1206             uint[] zd = new uint[zl];\r
1207 \r
1208             if (smallShift == 0) {\r
1209                 for (int i = 0; i < xl; i++) {\r
1210                     zd[i + digitShift] = xd[i];\r
1211                 }\r
1212             } else {\r
1213                 int carryShift = BitsPerDigit - smallShift;\r
1214                 uint carry = 0;\r
1215                 int i;\r
1216                 for (i = 0; i < xl; i++) {\r
1217                     uint rot = xd[i];\r
1218                     zd[i + digitShift] = rot << smallShift | carry;\r
1219                     carry = rot >> carryShift;\r
1220                 }\r
1221                 zd[i + digitShift] = carry;\r
1222             }\r
1223             return new BigInteger(x.sign, zd);\r
1224         }\r
1225 \r
1226         public static BigInteger RightShift(BigInteger x, int shift) {\r
1227             return x >> shift;\r
1228         }\r
1229 \r
1230         public static BigInteger operator >>(BigInteger x, int shift) {\r
1231             if (object.ReferenceEquals(x, null)) {\r
1232                 throw new ArgumentNullException("x");\r
1233             }\r
1234             if (shift == 0) return x;\r
1235             else if (shift < 0) return x << -shift;\r
1236 \r
1237             int digitShift = shift / BitsPerDigit;\r
1238             int smallShift = shift - (digitShift * BitsPerDigit);\r
1239 \r
1240             int xl = x.GetWordCount();\r
1241             uint[] xd = x.data;\r
1242             int zl = xl - digitShift;\r
1243             if (zl < 0) zl = 0;\r
1244             uint[] zd = new uint[zl];\r
1245 \r
1246             if (smallShift == 0) {\r
1247                 for (int i = xl - 1; i >= digitShift; i--) {\r
1248                     zd[i - digitShift] = xd[i];\r
1249                 }\r
1250             } else {\r
1251                 int carryShift = BitsPerDigit - smallShift;\r
1252                 uint carry = 0;\r
1253                 for (int i = xl - 1; i >= digitShift; i--) {\r
1254                     uint rot = xd[i];\r
1255                     zd[i - digitShift] = rot >> smallShift | carry;\r
1256                     carry = rot << carryShift;\r
1257                 }\r
1258             }\r
1259             return new BigInteger(x.sign, zd);\r
1260         }\r
1261 \r
1262         public static BigInteger Negate(BigInteger x) {\r
1263             return -x;\r
1264         }\r
1265 \r
1266         public static BigInteger operator -(BigInteger x) {\r
1267             if (object.ReferenceEquals(x, null)) {\r
1268                 throw new ArgumentNullException("x");\r
1269             }\r
1270             return new BigInteger(-x.sign, x.data);\r
1271         }\r
1272 \r
1273         public BigInteger OnesComplement() {\r
1274             return ~this;\r
1275         }\r
1276 \r
1277         public static BigInteger operator ~(BigInteger x) {\r
1278             if (object.ReferenceEquals(x, null)) {\r
1279                 throw new ArgumentNullException("x");\r
1280             }\r
1281             return -(x + One);\r
1282         }\r
1283 \r
1284         public BigInteger Abs() {\r
1285             if (this.sign == -1) return -this;\r
1286             else return this;\r
1287         }\r
1288 \r
1289         public BigInteger Power(int exp) {\r
1290             if (exp == 0) return One;\r
1291             if (exp < 0) {\r
1292                 throw new ArgumentOutOfRangeException("exp", "exp must be >= 0");\r
1293             }\r
1294             BigInteger factor = this;\r
1295             BigInteger result = One;\r
1296             while (exp != 0) {\r
1297                 if ((exp & 1) != 0) result = result * factor;\r
1298                 if (exp == 1) break;  // avoid costly factor.square()\r
1299                 factor = factor.Square();\r
1300                 exp >>= 1;\r
1301             }\r
1302             return result;\r
1303         }\r
1304 \r
1305         public BigInteger ModPow(int power, BigInteger mod) {\r
1306             if (object.ReferenceEquals(mod, null)) {\r
1307                 throw new ArgumentNullException("mod");\r
1308             }\r
1309 \r
1310             if (power < 0) {\r
1311                 throw new ArgumentOutOfRangeException("power", "power must be >= 0");\r
1312             }\r
1313             BigInteger factor = this;\r
1314             BigInteger result = One % mod; // Handle special case of power=0, mod=1\r
1315             while (power != 0) {\r
1316                 if ((power & 1) != 0) {\r
1317                     result = result * factor;\r
1318                     result = result % mod;\r
1319                 }\r
1320                 if (power == 1) break;  // avoid costly factor.Square()\r
1321                 factor = factor.Square();\r
1322                 factor = factor % mod;\r
1323                 power >>= 1;\r
1324             }\r
1325             return result;\r
1326         }\r
1327 \r
1328         public BigInteger ModPow(BigInteger power, BigInteger mod) {\r
1329             if (object.ReferenceEquals(power, null)) {\r
1330                 throw new ArgumentNullException("power");\r
1331             }\r
1332             if (object.ReferenceEquals(mod, null)) {\r
1333                 throw new ArgumentNullException("mod");\r
1334             }\r
1335 \r
1336             if (power < 0) {\r
1337                 throw new ArgumentOutOfRangeException("power", "power must be >= 0");\r
1338             }\r
1339 \r
1340             BigInteger factor = this;\r
1341             BigInteger result = One % mod;\r
1342             while (power != Zero) {\r
1343                 if (power.IsOdd()) {\r
1344                     result = result * factor;\r
1345                     result = result % mod;\r
1346                 }\r
1347                 if (power == One) break;  // avoid costly factor.Square()\r
1348                 factor = factor.Square();\r
1349                 factor = factor % mod;\r
1350                 power >>= 1;\r
1351             }\r
1352             return result;\r
1353         }\r
1354 \r
1355         public BigInteger Square() {\r
1356             return this * this;\r
1357         }\r
1358 \r
1359         public override string ToString() {\r
1360             return ToString(10);\r
1361         }\r
1362 \r
1363         // generated by scripts/radix_generator.py\r
1364         private static readonly uint[] maxCharsPerDigit = { 0, 0, 31, 20, 15, 13, 12, 11, 10, 10, 9, 9, 8, 8, 8, 8, 7, 7, 7, 7, 7, 7, 7, 7, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6 };\r
1365         private static readonly uint[] groupRadixValues = { 0, 0, 2147483648, 3486784401, 1073741824, 1220703125, 2176782336, 1977326743, 1073741824, 3486784401, 1000000000, 2357947691, 429981696, 815730721, 1475789056, 2562890625, 268435456, 410338673, 612220032, 893871739, 1280000000, 1801088541, 2494357888, 3404825447, 191102976, 244140625, 308915776, 387420489, 481890304, 594823321, 729000000, 887503681, 1073741824, 1291467969, 1544804416, 1838265625, 2176782336 };\r
1366 \r
1367         public static ArgumentOutOfRangeException MakeArgumentOutOfRangeException(string paramName, object actualValue, string message) {\r
1368                 return new ArgumentOutOfRangeException(paramName, string.Format("{0} (actual value is '{1}')", message, actualValue));\r
1369         }\r
1370         \r
1371         internal static string BigIntegerToString(uint[] d, int sign, int radix) {\r
1372             if (radix < 2) {\r
1373                     throw MakeArgumentOutOfRangeException("radix", radix, "radix must be >= 2");\r
1374             }\r
1375             if (radix > 36) {\r
1376                 throw MakeArgumentOutOfRangeException("radix", radix, "radix must be <= 36");\r
1377             }\r
1378 \r
1379             int dl = d.Length;\r
1380             if (dl == 0) {\r
1381                 return "0";\r
1382             }\r
1383 \r
1384             List<uint> digitGroups = new List<uint>();\r
1385 \r
1386             uint groupRadix = groupRadixValues[radix];\r
1387             while (dl > 0) {\r
1388                 uint rem = div(d, ref dl, groupRadix);\r
1389                 digitGroups.Add(rem);\r
1390             }\r
1391 \r
1392             StringBuilder ret = new StringBuilder();\r
1393             if (sign == -1) {\r
1394                 ret.Append("-");\r
1395             }\r
1396 \r
1397             int digitIndex = digitGroups.Count - 1;\r
1398 \r
1399             char[] tmpDigits = new char[maxCharsPerDigit[radix]];\r
1400 \r
1401             AppendRadix((uint)digitGroups[digitIndex--], (uint)radix, tmpDigits, ret, false);\r
1402             while (digitIndex >= 0) {\r
1403                 AppendRadix((uint)digitGroups[digitIndex--], (uint)radix, tmpDigits, ret, true);\r
1404             }\r
1405             return ret.Length == 0 ? "0" : ret.ToString();\r
1406         }\r
1407 \r
1408         private static uint div(uint[] n, ref int nl, uint d) {\r
1409             ulong rem = 0;\r
1410             int i = nl;\r
1411             bool seenNonZero = false;\r
1412             while (--i >= 0) {\r
1413                 rem <<= BitsPerDigit;\r
1414                 rem |= n[i];\r
1415                 uint v = (uint)(rem / d);\r
1416                 n[i] = v;\r
1417                 if (v == 0) {\r
1418                     if (!seenNonZero) nl--;\r
1419                 } else {\r
1420                     seenNonZero = true;\r
1421                 }\r
1422                 rem %= d;\r
1423             }\r
1424             return (uint)rem;\r
1425         }\r
1426 \r
1427         private static void AppendRadix(uint rem, uint radix, char[] tmp, StringBuilder buf, bool leadingZeros) {\r
1428             const string symbols = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";\r
1429 \r
1430             int digits = tmp.Length;\r
1431             int i = digits;\r
1432             while (i > 0 && (leadingZeros || rem != 0)) {\r
1433                 uint digit = rem % radix;\r
1434                 rem /= radix;\r
1435                 tmp[--i] = symbols[(int)digit];\r
1436             }\r
1437             if (leadingZeros) buf.Append(tmp);\r
1438             else buf.Append(tmp, i, digits - i);\r
1439         }\r
1440 \r
1441         public string ToString(int radix) {\r
1442             return BigIntegerToString(copy(data), sign, radix);\r
1443         }\r
1444 \r
1445         public override int GetHashCode() {\r
1446             // The Object.GetHashCode function needs to be consistent with the Object.Equals function.\r
1447             // Languages that build on top of this may have a more flexible equality function and \r
1448             // so may not be able to use this hash function directly.\r
1449             // For example, Python allows BigInteger(10) == int32(10), so hashing a BigInt over the Int32\r
1450             // domain should return the same value as a hash of the Int32.\r
1451 \r
1452             // If this is in the int32 range, this hash function returns the integer.\r
1453             if (data.Length == 0) {\r
1454                 return 0;\r
1455             }\r
1456 \r
1457             // Add up all uints. We want to incorporate all bits to get good hash distribution. \r
1458             uint total = 0;\r
1459             foreach (uint x in data) {\r
1460                 total = unchecked(total + x);\r
1461             }\r
1462 \r
1463             int hash = unchecked((int)total);\r
1464 \r
1465             // The sign is not part of the data array, so explicitly incorporate that.\r
1466             // This is also needed to ensure that hash(-x) == -x for int32.\r
1467             if (IsNegative()) {\r
1468                 return unchecked(-hash);\r
1469             } else {\r
1470                 return hash;\r
1471             }\r
1472         }\r
1473 \r
1474         public override bool Equals(object obj) {\r
1475             return Equals(obj as BigInteger);\r
1476         }\r
1477 \r
1478         public bool Equals(BigInteger other) {\r
1479             if (object.ReferenceEquals(other, null)) return false;\r
1480             return this == other;\r
1481         }\r
1482 \r
1483 \r
1484         public bool IsNegative() {\r
1485             return sign < 0;\r
1486         }\r
1487 \r
1488         public bool IsZero() {\r
1489             return sign == 0;\r
1490         }\r
1491 \r
1492         public bool IsPositive() {\r
1493             return sign > 0;\r
1494         }\r
1495 \r
1496         private bool IsOdd() {\r
1497             // must have the lowest-order bit set to 1\r
1498             return (data != null && data.Length > 0 && ((data[0] & 1) != 0));\r
1499         }\r
1500 \r
1501 \r
1502         public double Log(Double newBase) {\r
1503             if (IsNegative() || newBase == 1.0D || this == Zero || (newBase == 0.0D && this != One)) {\r
1504                 return Double.NaN;\r
1505             } else if (newBase == Double.PositiveInfinity) {\r
1506                 return this == One ? 0.0D : Double.NaN;\r
1507             }\r
1508 \r
1509             int length = GetLength(data) - 1;\r
1510             int bitCount = -1;\r
1511             for (int curBit = 31; curBit >= 0; curBit--) {\r
1512                 if ((data[length] & (1 << curBit)) != 0) {\r
1513                     bitCount = curBit + length * 32;\r
1514                     break;\r
1515                 }\r
1516             }\r
1517 \r
1518             long bitlen = bitCount;\r
1519             Double c = 0, d = 1;\r
1520 \r
1521             BigInteger testBit = BigInteger.One;\r
1522             long tempBitlen = bitlen;\r
1523             while (tempBitlen > Int32.MaxValue) {\r
1524                 testBit = testBit << Int32.MaxValue;\r
1525                 tempBitlen -= Int32.MaxValue;\r
1526             }\r
1527             testBit = testBit << (int)tempBitlen;\r
1528 \r
1529             for (long curbit = bitlen; curbit >= 0; --curbit) {\r
1530                 if ((this & testBit) != BigInteger.Zero)\r
1531                     c += d;\r
1532                 d *= 0.5;\r
1533                 testBit = testBit >> 1;\r
1534             }\r
1535             return (System.Math.Log(c) + System.Math.Log(2) * bitlen) / System.Math.Log(newBase);\r
1536         }\r
1537 \r
1538         /// <summary>\r
1539         /// Calculates the natural logarithm of the BigInteger.\r
1540         /// </summary>\r
1541         public double Log() {\r
1542             return Log(System.Math.E);\r
1543         }\r
1544 \r
1545         /// <summary>\r
1546         /// Calculates log base 10 of a BigInteger.\r
1547         /// </summary>\r
1548         public double Log10() {\r
1549             return Log(10);\r
1550         }\r
1551 \r
1552         #region IComparable Members\r
1553 \r
1554         public int CompareTo(object obj) {\r
1555             if (obj == null) {\r
1556                 return 1;\r
1557             }\r
1558             BigInteger o = obj as BigInteger;\r
1559             if (object.ReferenceEquals(o, null)) {\r
1560                 throw new ArgumentException("expected integer");\r
1561             }\r
1562             return Compare(this, o);\r
1563         }\r
1564 \r
1565         #endregion\r
1566 \r
1567         #region IConvertible Members\r
1568 \r
1569         public TypeCode GetTypeCode() {\r
1570             return TypeCode.Object;\r
1571         }\r
1572 \r
1573         public bool ToBoolean(IFormatProvider provider) {\r
1574             return this != Zero;\r
1575         }\r
1576 \r
1577         public byte ToByte(IFormatProvider provider) {\r
1578             uint ret;\r
1579             if (AsUInt32(out ret) && (ret & ~0xFF) == 0) {\r
1580                 return (byte)ret;\r
1581             }\r
1582             throw new OverflowException("big integer won't fit into byte");\r
1583         }\r
1584 \r
1585         /// <summary>\r
1586         /// Return the value of this BigInteger as a little-endian twos-complement\r
1587         /// byte array, using the fewest number of bytes possible. If the value is zero,\r
1588         /// return an array of one byte whose element is 0x00.\r
1589         /// </summary>\r
1590         public byte[] ToByteArray() {\r
1591             // We could probably make this more efficient by eliminating one of the passes.\r
1592             // The current code does one pass for uint array -> byte array conversion,\r
1593             // and then a another pass to remove unneeded bytes at the top of the array.\r
1594             if (0 == sign) return new byte[] { 0 };\r
1595 \r
1596             uint[] dwords;\r
1597             byte highByte;\r
1598 \r
1599             if (-1 == sign) {\r
1600                 dwords = (uint[])this.data.Clone();\r
1601                 makeTwosComplement(dwords);\r
1602                 highByte = 0xff;\r
1603             } else {\r
1604                 dwords = this.data;\r
1605                 highByte = 0x00;\r
1606             }\r
1607 \r
1608             byte[] bytes = new byte[4 * dwords.Length];\r
1609             int curByte = 0;\r
1610             uint dword;\r
1611             for (int i = 0; i < dwords.Length; i++) {\r
1612                 dword = dwords[i];\r
1613                 for (int j = 0; j < 4; j++) {\r
1614                     bytes[curByte++] = (byte)(dword & 0xff);\r
1615                     dword >>= 8;\r
1616                 }\r
1617             }\r
1618 \r
1619             // find highest significant byte\r
1620             int msb;\r
1621             for (msb = bytes.Length - 1; msb > 0; msb--) {\r
1622                 if (bytes[msb] != highByte) break;\r
1623             }\r
1624             // ensure high bit is 0 if positive, 1 if negative\r
1625             bool needExtraByte = (bytes[msb] & 0x80) != (highByte & 0x80);\r
1626 \r
1627             byte[] trimmedBytes = new byte[msb + 1 + (needExtraByte ? 1 : 0)];\r
1628             Array.Copy(bytes, trimmedBytes, msb + 1);\r
1629 \r
1630             if (needExtraByte) trimmedBytes[trimmedBytes.Length - 1] = highByte;\r
1631 \r
1632             return trimmedBytes;\r
1633         }\r
1634 \r
1635         public char ToChar(IFormatProvider provider) {\r
1636             int ret;\r
1637             if (AsInt32(out ret) && (ret <= Char.MaxValue) && (ret >= Char.MinValue)) {\r
1638                 return (char)ret;\r
1639             }\r
1640             throw new OverflowException("big integer won't fit into char");\r
1641         }\r
1642 \r
1643         public DateTime ToDateTime(IFormatProvider provider) {\r
1644             throw new NotImplementedException();\r
1645         }\r
1646 \r
1647         public decimal ToDecimal(IFormatProvider provider) {\r
1648             decimal ret;\r
1649             if (AsDecimal(out ret)) return ret;\r
1650             throw new OverflowException("big integer won't fit into decimal");\r
1651         }\r
1652 \r
1653         public double ToDouble(IFormatProvider provider) {\r
1654             return ToFloat64();\r
1655         }\r
1656 \r
1657         public short ToInt16(IFormatProvider provider) {\r
1658             int ret;\r
1659             if (AsInt32(out ret) && (ret <= short.MaxValue) && (ret >= short.MinValue)) {\r
1660                 return (short)ret;\r
1661             }\r
1662             throw new OverflowException("big integer won't fit into short");\r
1663         }\r
1664 \r
1665         public int ToInt32(IFormatProvider provider) {\r
1666             int ret;\r
1667             if (AsInt32(out ret)) {\r
1668                 return ret;\r
1669             }\r
1670             throw new OverflowException("big integer won't fit into int");\r
1671         }\r
1672 \r
1673         public long ToInt64(IFormatProvider provider) {\r
1674             long ret;\r
1675             if (AsInt64(out ret)) {\r
1676                 return ret;\r
1677             }\r
1678             throw new OverflowException("big integer won't fit into long");\r
1679         }\r
1680 \r
1681         [CLSCompliant(false)]\r
1682         public sbyte ToSByte(IFormatProvider provider) {\r
1683             int ret;\r
1684             if (AsInt32(out ret) && (ret <= sbyte.MaxValue) && (ret >= sbyte.MinValue)) {\r
1685                 return (sbyte)ret;\r
1686             }\r
1687             throw new OverflowException("big integer won't fit into sbyte");\r
1688         }\r
1689 \r
1690         public float ToSingle(IFormatProvider provider) {\r
1691             return checked((float)ToDouble(provider));\r
1692         }\r
1693 \r
1694         public string ToString(IFormatProvider provider) {\r
1695             return ToString();\r
1696         }\r
1697 \r
1698         public object ToType(Type conversionType, IFormatProvider provider) {\r
1699             if (conversionType == typeof(BigInteger)) {\r
1700                 return this;\r
1701             }\r
1702             throw new NotImplementedException();\r
1703         }\r
1704 \r
1705         [CLSCompliant(false)]\r
1706         public ushort ToUInt16(IFormatProvider provider) {\r
1707             uint ret;\r
1708             if (AsUInt32(out ret) && ret <= ushort.MaxValue) {\r
1709                 return (ushort)ret;\r
1710             }\r
1711             throw new OverflowException("big integer won't fit into ushort");\r
1712         }\r
1713 \r
1714         [CLSCompliant(false)]\r
1715         public uint ToUInt32(IFormatProvider provider) {\r
1716             uint ret;\r
1717             if (AsUInt32(out ret)) {\r
1718                 return ret;\r
1719             }\r
1720             throw new OverflowException("big integer won't fit into uint");\r
1721         }\r
1722 \r
1723         [CLSCompliant(false)]\r
1724         public ulong ToUInt64(IFormatProvider provider) {\r
1725             ulong ret;\r
1726             if (AsUInt64(out ret)) {\r
1727                 return ret;\r
1728             }\r
1729             throw new OverflowException("big integer won't fit into ulong");\r
1730         }\r
1731 \r
1732         #endregion\r
1733 \r
1734         #region IFormattable Members\r
1735 \r
1736         string IFormattable.ToString(string format, IFormatProvider formatProvider) {\r
1737             if (format == null) return this.ToString();\r
1738 \r
1739             switch (format[0]) {\r
1740                 case 'd':\r
1741                 case 'D':\r
1742                     if (format.Length > 1) {\r
1743                         int precision = Convert.ToInt32(format.Substring(1), CultureInfo.InvariantCulture.NumberFormat);\r
1744                         string baseStr = ToString(10);\r
1745                         if (baseStr.Length < precision) {\r
1746                             string additional = new String('0', precision - baseStr.Length);\r
1747                             if (baseStr[0] != '-') {\r
1748                                 return additional + baseStr;\r
1749                             } else {\r
1750                                 return "-" + additional + baseStr.Substring(1);\r
1751                             }\r
1752                         }\r
1753                         return baseStr;\r
1754                     }\r
1755                     return ToString(10);\r
1756                 case 'x':\r
1757                 case 'X':\r
1758                     StringBuilder res = new StringBuilder(ToString(16));\r
1759                     if (format[0] == 'x') {\r
1760                         for (int i = 0; i < res.Length; i++) {\r
1761                             if (res[i] >= 'A' && res[i] <= 'F') {\r
1762                                 res[i] = Char.ToLower(res[i], CultureInfo.InvariantCulture);\r
1763                             }\r
1764                         }\r
1765                     }\r
1766 \r
1767                     if (format.Length > 1) {\r
1768                         int precision = Convert.ToInt32(format.Substring(1), CultureInfo.InvariantCulture.NumberFormat);\r
1769                         if (res.Length < precision) {\r
1770                             string additional = new String('0', precision - res.Length);\r
1771                             if (res[0] != '-') {\r
1772                                 res.Insert(0, additional);\r
1773                             } else {\r
1774                                 res.Insert(1, additional);\r
1775                             }\r
1776                         }\r
1777                     }\r
1778 \r
1779                     return res.ToString();\r
1780                 default:\r
1781                     throw new NotImplementedException("format not implemented");\r
1782             }\r
1783         }\r
1784 \r
1785         #endregion        \r
1786     }\r
1787 }\r