mcs/class/dlr/Runtime/Microsoft.Dynamic/Math/BigIntegerV4.cs

   1 /* ****************************************************************************
   2  *
   3  * Copyright (c) Microsoft Corporation.
   4  *
   5  * This source code is subject to terms and conditions of the Apache License, Version 2.0. A
   6  * copy of the license can be found in the License.html file at the root of this distribution. If
   7  * you cannot locate the  Apache License, Version 2.0, please send an email to
   8  * dlr@microsoft.com. By using this source code in any fashion, you are agreeing to be bound
   9  * by the terms of the Apache License, Version 2.0.
  10  *
  11  * You must not remove this notice, or any other, from this software.
  12  *
  13  *
  14  * ***************************************************************************/
  15 #if FEATURE_NUMERICS
  16
  17 using System;
  18 using System.Collections.Generic;
  19 using System.Diagnostics;
  20 using System.Diagnostics.CodeAnalysis;
  21 using System.Globalization;
  22 using System.Text;
  23 using Microsoft.Scripting.Utils;
  24 using BigInt = System.Numerics.BigInteger;
  25
  26 namespace Microsoft.Scripting.Math {
  27     /// <summary>
  28     /// arbitrary precision integers
  29     /// </summary>
  30     [Serializable]
  31     public sealed class BigInteger : IFormattable, IComparable, IEquatable<BigInteger> {
  32         internal readonly BigInt Value;
  33
  34         [SuppressMessage("Microsoft.Security", "CA2104:DoNotDeclareReadOnlyMutableReferenceTypes")]
  35         public static readonly BigInteger Zero = new BigInteger((BigInt)0);
  36         [SuppressMessage("Microsoft.Security", "CA2104:DoNotDeclareReadOnlyMutableReferenceTypes")]
  37         public static readonly BigInteger One = new BigInteger((BigInt)1);
  38
  39         public BigInteger(BigInt value) {
  40             Value = value;
  41         }
  42
  43         [CLSCompliant(false)]
  44         public static BigInteger Create(ulong v) {
  45             return new BigInteger(new BigInt(v));
  46         }
  47
  48         [CLSCompliant(false)]
  49         public static BigInteger Create(uint v) {
  50             return new BigInteger(new BigInt(v));
  51         }
  52
  53         public static BigInteger Create(long v) {
  54             return new BigInteger(new BigInt(v));
  55         }
  56
  57         public static BigInteger Create(int v) {
  58             return new BigInteger(new BigInt(v));
  59         }
  60
  61         public static BigInteger Create(decimal v) {
  62             return new BigInteger(new BigInt(v));
  63         }
  64
  65         public static BigInteger Create(byte[] v) {
  66             return new BigInteger(v);
  67         }
  68
  69         public static BigInteger Create(double v) {
  70             return new BigInteger(new BigInt(v));
  71         }
  72
  73         public static implicit operator BigInteger(byte i) {
  74             return new BigInteger((BigInt)i);
  75         }
  76
  77         [CLSCompliant(false)]
  78         public static implicit operator BigInteger(sbyte i) {
  79             return new BigInteger((BigInt)i);
  80         }
  81
  82         public static implicit operator BigInteger(short i) {
  83             return new BigInteger((BigInt)i);
  84         }
  85
  86         [CLSCompliant(false)]
  87         public static implicit operator BigInteger(ushort i) {
  88             return new BigInteger((BigInt)i);
  89         }
  90
  91         [CLSCompliant(false)]
  92         public static implicit operator BigInteger(uint i) {
  93             return new BigInteger((BigInt)i);
  94         }
  95
  96         public static implicit operator BigInteger(int i) {
  97             return new BigInteger((BigInt)i);
  98         }
  99
 100         [CLSCompliant(false)]
 101         public static implicit operator BigInteger(ulong i) {
 102             return new BigInteger((BigInt)i);
 103         }
 104
 105         public static implicit operator BigInteger(long i) {
 106             return new BigInteger((BigInt)i);
 107         }
 108
 109         public static implicit operator BigInteger(decimal self) {
 110             return new BigInteger((BigInt)self);
 111         }
 112
 113         public static explicit operator BigInteger(double self) {
 114             return new BigInteger((BigInt)self);
 115         }
 116
 117         public static explicit operator BigInteger(float self) {
 118             return new BigInteger((BigInt)self);
 119         }
 120
 121         public static explicit operator double(BigInteger self) {
 122             return (double)self.Value;
 123         }
 124
 125         public static explicit operator float(BigInteger self) {
 126             return (float)self.Value;
 127         }
 128
 129         public static explicit operator decimal(BigInteger self) {
 130             return (decimal)self.Value;
 131         }
 132
 133         public static explicit operator byte(BigInteger self) {
 134             return (byte)self.Value;
 135         }
 136
 137         [CLSCompliant(false)]
 138         public static explicit operator sbyte(BigInteger self) {
 139             return (sbyte)self.Value;
 140         }
 141
 142         [CLSCompliant(false)]
 143         public static explicit operator UInt16(BigInteger self) {
 144             return (UInt16)self.Value;
 145         }
 146
 147         public static explicit operator Int16(BigInteger self) {
 148             return (Int16)self.Value;
 149         }
 150
 151         [CLSCompliant(false)]
 152         public static explicit operator UInt32(BigInteger self) {
 153             return (UInt32)self.Value;
 154         }
 155
 156         public static explicit operator Int32(BigInteger self) {
 157             return (Int32)self.Value;
 158         }
 159
 160         public static explicit operator Int64(BigInteger self) {
 161             return (Int64)self.Value;
 162         }
 163
 164         [CLSCompliant(false)]
 165         public static explicit operator UInt64(BigInteger self) {
 166             return (UInt64)self.Value;
 167         }
 168
 169         public static implicit operator BigInteger(BigInt value) {
 170             return new BigInteger(value);
 171         }
 172
 173         public static implicit operator BigInt(BigInteger value) {
 174             return value.Value;
 175         }
 176
 177         public BigInteger(BigInteger copy) {
 178             if (object.ReferenceEquals(copy, null)) {
 179                 throw new ArgumentNullException("copy");
 180             }
 181             Value = copy.Value;
 182         }
 183
 184         public BigInteger(byte[] data) {
 185             ContractUtils.RequiresNotNull(data, "data");
 186
 187             Value = new BigInt(data);
 188         }
 189
 190         public BigInteger(int sign, byte[] data) {
 191             ContractUtils.RequiresNotNull(data, "data");
 192             ContractUtils.Requires(sign >= -1 && sign <= +1, "sign");
 193
 194             Value = new BigInt(data);
 195             if (sign < 0) {
 196                 Value = -Value;
 197             }
 198         }
 199
 200         [CLSCompliant(false)]
 201         public BigInteger(int sign, uint[] data) {
 202             ContractUtils.RequiresNotNull(data, "data");
 203             ContractUtils.Requires(sign >= -1 && sign <= +1, "sign");
 204             int length = GetLength(data);
 205             ContractUtils.Requires(length == 0 || sign != 0, "sign");
 206             if (length == 0) {
 207                 Value = 0;
 208                 return;
 209             }
 210
 211             bool highest = (data[length - 1] & 0x80000000) != 0;
 212             byte[] bytes = new byte[length * 4 + (highest ? 1 : 0)];
 213             int j = 0;
 214             for (int i = 0; i < length; i++) {
 215                 ulong w = data[i];
 216                 bytes[j++] = (byte)(w & 0xff);
 217                 bytes[j++] = (byte)((w >> 8) & 0xff);
 218                 bytes[j++] = (byte)((w >> 16) & 0xff);
 219                 bytes[j++] = (byte)((w >> 24) & 0xff);
 220             }
 221
 222             Value = new BigInt(bytes);
 223             if (sign < 0) {
 224                 Value = -Value;
 225             }
 226         }
 227
 228         [CLSCompliant(false)]
 229         public uint[] GetWords() {
 230             return Value.GetWords();
 231         }
 232
 233         public int GetBitCount() {
 234             return Value.GetBitCount();
 235         }
 236
 237         public int GetWordCount() {
 238             return Value.GetWordCount();
 239         }
 240
 241         public int GetByteCount() {
 242             return Value.GetByteCount();
 243         }
 244
 245         /// <summary>
 246         /// Return the sign of this BigInteger: -1, 0, or 1.
 247         /// </summary>
 248         public int Sign {
 249             get {
 250                 return Value.Sign;
 251             }
 252         }
 253
 254         public bool AsInt64(out long ret) {
 255             if (Value >= Int64.MinValue && Value <= Int64.MaxValue) {
 256                 ret = (long)Value;
 257                 return true;
 258             }
 259             ret = 0;
 260             return false;
 261         }
 262
 263         [CLSCompliant(false)]
 264         public bool AsUInt32(out uint ret) {
 265             if (Value >= UInt32.MinValue && Value <= UInt32.MaxValue) {
 266                 ret = (UInt32)Value;
 267                 return true;
 268             }
 269             ret = 0;
 270             return false;
 271         }
 272
 273         [CLSCompliant(false)]
 274         public bool AsUInt64(out ulong ret) {
 275             if (Value >= UInt64.MinValue && Value <= UInt64.MaxValue) {
 276                 ret = (UInt64)Value;
 277                 return true;
 278             }
 279             ret = 0;
 280             return false;
 281         }
 282
 283         public bool AsInt32(out int ret) {
 284             if (Value >= Int32.MinValue && Value <= Int32.MaxValue) {
 285                 ret = (Int32)Value;
 286                 return true;
 287             }
 288             ret = 0;
 289             return false;
 290         }
 291
 292         [CLSCompliant(false)]
 293         public uint ToUInt32() {
 294             return (uint)Value;
 295         }
 296
 297         public int ToInt32() {
 298             return (int)Value;
 299         }
 300
 301         public decimal ToDecimal() {
 302             return (decimal)Value;
 303         }
 304
 305         [CLSCompliant(false)]
 306         public ulong ToUInt64() {
 307             return (ulong)Value;
 308         }
 309
 310         public long ToInt64() {
 311             return (long)Value;
 312         }
 313
 314         private static int GetLength(uint[] data) {
 315             int ret = data.Length - 1;
 316             while (ret >= 0 && data[ret] == 0) ret--;
 317             return ret + 1;
 318         }
 319
 320         public static int Compare(BigInteger x, BigInteger y) {
 321             return BigInt.Compare(x.Value, y.Value);
 322         }
 323
 324         public static bool operator ==(BigInteger x, int y) {
 325             return x.Value == y;
 326         }
 327
 328         public static bool operator !=(BigInteger x, int y) {
 329             return x.Value != y;
 330         }
 331
 332         [System.Diagnostics.CodeAnalysis.SuppressMessage("Microsoft.Design", "CA1065:DoNotRaiseExceptionsInUnexpectedLocations")] // TODO: fix
 333         public static bool operator ==(BigInteger x, double y) {
 334             if (object.ReferenceEquals(x, null)) {
 335                 throw new ArgumentNullException("x");
 336             }
 337
 338             // we can hold all double values, but not all double values
 339             // can hold BigInteger values, and we may lose precision.  Convert
 340             // the double to a big int, then compare.
 341
 342             if ((y % 1) != 0) return false;  // not a whole number, can't be equal
 343
 344             return x.Value == (BigInt)y;
 345         }
 346
 347         public static bool operator ==(double x, BigInteger y) {
 348             return y == x;
 349         }
 350
 351         public static bool operator !=(BigInteger x, double y) {
 352             return !(x == y);
 353         }
 354
 355         public static bool operator !=(double x, BigInteger y) {
 356             return !(x == y);
 357         }
 358
 359
 360         public static bool operator ==(BigInteger x, BigInteger y) {
 361             return Compare(x, y) == 0;
 362         }
 363
 364         public static bool operator !=(BigInteger x, BigInteger y) {
 365             return Compare(x, y) != 0;
 366         }
 367         public static bool operator <(BigInteger x, BigInteger y) {
 368             return Compare(x, y) < 0;
 369         }
 370         public static bool operator <=(BigInteger x, BigInteger y) {
 371             return Compare(x, y) <= 0;
 372         }
 373         public static bool operator >(BigInteger x, BigInteger y) {
 374             return Compare(x, y) > 0;
 375         }
 376         public static bool operator >=(BigInteger x, BigInteger y) {
 377             return Compare(x, y) >= 0;
 378         }
 379
 380         public static BigInteger Add(BigInteger x, BigInteger y) {
 381             return x + y;
 382         }
 383
 384         public static BigInteger operator +(BigInteger x, BigInteger y) {
 385             return new BigInteger(x.Value + y.Value);
 386         }
 387
 388         public static BigInteger Subtract(BigInteger x, BigInteger y) {
 389             return x - y;
 390         }
 391
 392         public static BigInteger operator -(BigInteger x, BigInteger y) {
 393             return new BigInteger(x.Value - y.Value);
 394         }
 395
 396         public static BigInteger Multiply(BigInteger x, BigInteger y) {
 397             return x * y;
 398         }
 399
 400         public static BigInteger operator *(BigInteger x, BigInteger y) {
 401             return new BigInteger(x.Value * y.Value);
 402         }
 403
 404         public static BigInteger Divide(BigInteger x, BigInteger y) {
 405             return x / y;
 406         }
 407
 408         public static BigInteger operator /(BigInteger x, BigInteger y) {
 409             BigInteger dummy;
 410             return DivRem(x, y, out dummy);
 411         }
 412
 413         public static BigInteger Mod(BigInteger x, BigInteger y) {
 414             return x % y;
 415         }
 416
 417         public static BigInteger operator %(BigInteger x, BigInteger y) {
 418             BigInteger ret;
 419             DivRem(x, y, out ret);
 420             return ret;
 421         }
 422
 423         public static BigInteger DivRem(BigInteger x, BigInteger y, out BigInteger remainder) {
 424             BigInt rem;
 425             BigInt result = BigInt.DivRem(x.Value, y.Value, out rem);
 426             remainder = new BigInteger(rem);
 427             return new BigInteger(result);
 428         }
 429
 430         public static BigInteger BitwiseAnd(BigInteger x, BigInteger y) {
 431             return x & y;
 432         }
 433
 434         public static BigInteger operator &(BigInteger x, BigInteger y) {
 435             return new BigInteger(x.Value & y.Value);
 436         }
 437
 438         public static BigInteger BitwiseOr(BigInteger x, BigInteger y) {
 439             return x | y;
 440         }
 441
 442         public static BigInteger operator |(BigInteger x, BigInteger y) {
 443             return new BigInteger(x.Value | y.Value);
 444         }
 445
 446         public static BigInteger Xor(BigInteger x, BigInteger y) {
 447             return x ^ y;
 448         }
 449
 450         public static BigInteger operator ^(BigInteger x, BigInteger y) {
 451             return new BigInteger(x.Value ^ y.Value);
 452         }
 453
 454         public static BigInteger LeftShift(BigInteger x, int shift) {
 455             return x << shift;
 456         }
 457
 458         public static BigInteger operator <<(BigInteger x, int shift) {
 459             return new BigInteger(x.Value << shift);
 460         }
 461
 462         public static BigInteger RightShift(BigInteger x, int shift) {
 463             return x >> shift;
 464         }
 465
 466         public static BigInteger operator >>(BigInteger x, int shift) {
 467             return new BigInteger(x.Value >> shift);
 468         }
 469
 470         public static BigInteger Negate(BigInteger x) {
 471             return -x;
 472         }
 473
 474         public static BigInteger operator -(BigInteger x) {
 475             return new BigInteger(-x.Value);
 476         }
 477
 478         public BigInteger OnesComplement() {
 479             return ~this;
 480         }
 481
 482         public static BigInteger operator ~(BigInteger x) {
 483             return new BigInteger(~x.Value);
 484         }
 485
 486         public BigInteger Abs() {
 487             return new BigInteger(BigInt.Abs(Value));
 488         }
 489
 490         public BigInteger Power(int exp) {
 491             return new BigInteger(BigInt.Pow(Value, exp));
 492         }
 493
 494         public BigInteger ModPow(int power, BigInteger mod) {
 495             return new BigInteger(BigInt.ModPow(Value, power, mod.Value));
 496         }
 497
 498         public BigInteger ModPow(BigInteger power, BigInteger mod) {
 499             return new BigInteger(BigInt.ModPow(Value, power.Value, mod.Value));
 500         }
 501
 502         public BigInteger Square() {
 503             return this * this;
 504         }
 505
 506 #if !SILVERLIGHT
 507         public static BigInteger Parse(string str) {
 508             return new BigInteger(BigInt.Parse(str));
 509         }
 510 #endif
 511
 512         public override string ToString() {
 513             return ToString(10);
 514         }
 515
 516         public string ToString(int @base) {
 517             return MathUtils.BigIntegerToString(GetWords(), Sign, @base, false);
 518         }
 519
 520         public string ToString(string format) {
 521             return Value.ToString(format);
 522         }
 523
 524         public override int GetHashCode() {
 525             return Value.GetHashCode();
 526         }
 527
 528         public override bool Equals(object obj) {
 529             return Equals(obj as BigInteger);
 530         }
 531
 532         public bool Equals(BigInteger other) {
 533             if (object.ReferenceEquals(other, null)) return false;
 534             return this == other;
 535         }
 536
 537         public bool IsNegative() {
 538             return Value.Sign < 0;
 539         }
 540
 541         public bool IsZero() {
 542             return Value.Sign == 0;
 543         }
 544
 545         public bool IsPositive() {
 546             return Value.Sign > 0;
 547         }
 548
 549         public bool IsEven {
 550             get { return Value.IsEven; }
 551         }
 552
 553         public bool IsPowerOfTwo {
 554             get {
 555                 return Value.IsPowerOfTwo;
 556             }
 557         }
 558
 559         public double Log(Double newBase) {
 560             return BigInt.Log(Value, newBase);
 561         }
 562
 563         /// <summary>
 564         /// Calculates the natural logarithm of the BigInteger.
 565         /// </summary>
 566         public double Log() {
 567             return BigInt.Log(Value);
 568         }
 569
 570         /// <summary>
 571         /// Calculates log base 10 of a BigInteger.
 572         /// </summary>
 573         public double Log10() {
 574             return BigInt.Log10(Value);
 575         }
 576
 577 #region IComparable Members
 578
 579         public int CompareTo(object obj) {
 580             if (obj == null) {
 581                 return 1;
 582             }
 583             BigInteger o = obj as BigInteger;
 584             if (object.ReferenceEquals(o, null)) {
 585                 throw new ArgumentException("expected integer");
 586             }
 587             return Compare(this, o);
 588         }
 589
 590         #endregion
 591
 592         /// <summary>
 593         /// Return the value of this BigInteger as a little-endian twos-complement
 594         /// byte array, using the fewest number of bytes possible. If the value is zero,
 595         /// return an array of one byte whose element is 0x00.
 596         /// </summary>
 597         public byte[] ToByteArray() {
 598             return Value.ToByteArray();
 599         }
 600
 601         public string ToString(IFormatProvider provider) {
 602             return Value.ToString(provider);
 603         }
 604
 605 #region IFormattable Members
 606
 607         string IFormattable.ToString(string format, IFormatProvider formatProvider) {
 608             return Value.ToString(format, formatProvider);
 609         }
 610
 611         #endregion
 612     }
 613 }
 614 #endif