context: // Notes from Irony project coordinator (Roman Ivantsov)
  //  1. The code in this file is a copy of the file with the same name from Microsoft.Scripting distribution, 
  //     with a few minor changes made to be able to compile as part of Irony. 
  //     Waiting for MS to provide big integers as part of .NET core distribution - long promised
  //  2. I had to tweak a few static fields to make them readonly, to comply with security requirements 
  //     for SQL Server-imported assemblies. To find the modified fields, search for "RI:" token 
  
  
  /* ****************************************************************************
   *
   * Copyright (c) Microsoft Corporation. 
   *
   * This source code is subject to terms and conditions of the Microsoft Public License. A 
   * copy of the license can be found in the License.html file at the root of this distribution. If 
   * you cannot locate the  Microsoft Public License, please send an email to 
   * dlr@microsoft.com. By using this source code in any fashion, you are agreeing to be bound 
   * by the terms of the Microsoft Public License.
   *
   * You must not remove this notice, or any other, from this software.
   *
   *
   * ***************************************************************************/
  
  using System;
  using System.Text;
  using System.Collections;
  using System.Collections.Generic;
  using System.Globalization;
  using System.Diagnostics;
  using System.Diagnostics.CodeAnalysis;
  //using Microsoft.Scripting.Utils;
  
  namespace Microsoft.Scripting.Math {
    /// <summary>
    /// arbitrary precision integers
    /// </summary>
    [System.ComponentModel.TypeConverter(typeof(BigInteger.TypeConvertor))]
    public class BigInteger : IFormattable, IComparable, IConvertible {
  
      class TypeConvertor : System.ComponentModel.TypeConverter {
        public override bool CanConvertFrom(System.ComponentModel.ITypeDescriptorContext context, Type sourceType) {
          if (sourceType == typeof(BigInteger)) {
            return true;
          }
          switch (Type.GetTypeCode(sourceType)) {
            case TypeCode.Boolean:
            case TypeCode.DateTime:
            case TypeCode.DBNull:
            case TypeCode.Empty:
            case TypeCode.Object:
              return false;
            default:
              return true;
          }
        }
  
        public override object ConvertFrom(System.ComponentModel.ITypeDescriptorContext context, CultureInfo culture, object value) {
          if (value != null) {
            Type vt = value.GetType();
            if (vt == typeof(BigInteger)) {
              return value;
            }
            switch (Type.GetTypeCode(vt)) {
              case TypeCode.Byte:
                return BigInteger.Create((byte)value);
              case TypeCode.Char:
                return BigInteger.Create((char)value);
              case TypeCode.Int16:
                return BigInteger.Create((short)value);
              case TypeCode.Int32:
                return BigInteger.Create((int)value);
              case TypeCode.Int64:
                return BigInteger.Create((long)value);
              case TypeCode.SByte:
                return BigInteger.Create((sbyte)value);
              case TypeCode.UInt16:
                return BigInteger.Create((ushort)value);
              case TypeCode.UInt32:
                return BigInteger.Create((uint)value);
              case TypeCode.UInt64:
                return BigInteger.Create((ulong)value);
              case TypeCode.Decimal:
                return BigInteger.Create((decimal)value);
              case TypeCode.Single:
                return BigInteger.Create((float)value);
              case TypeCode.Double:
                return BigInteger.Create((double)value);
            }
          }
          return base.ConvertFrom(context, culture, value);
        }
  
        public override bool CanConvertTo(System.ComponentModel.ITypeDescriptorContext context, Type destinationType) {
          if (destinationType == typeof(BigInteger)) {
            return true;
          }
          switch (Type.GetTypeCode(destinationType)) {
            case TypeCode.Boolean:
            case TypeCode.DateTime:
            case TypeCode.DBNull:
            case TypeCode.Empty:
            case TypeCode.Object:
              return false;
            default:
              return true;
          }
        }
  
        public override object ConvertTo(System.ComponentModel.ITypeDescriptorContext context, CultureInfo culture, object value, Type destinationType) {
          if (value != null) {
            BigInteger bi = (BigInteger)value;
            Type vt = destinationType;
            if (vt == typeof(BigInteger)) {
              return value;
            }
            switch (Type.GetTypeCode(vt)) {
              case TypeCode.Byte:
                return bi.ToByte(null);
              case TypeCode.Char:
                return bi.ToChar(null);
              case TypeCode.Int16:
                return bi.ToInt16(null);
              case TypeCode.Int32:
                return bi.ToInt32(null);
              case TypeCode.Int64:
                return bi.ToInt64(null);
              case TypeCode.SByte:
                return bi.ToSByte(null);
              case TypeCode.UInt16:
                return bi.ToUInt16(null);
              case TypeCode.UInt32:
                return bi.ToUInt32(null);
              case TypeCode.UInt64:
                return bi.ToUInt64(null);
              case TypeCode.Decimal:
                return bi.ToDecimal(null);
              case TypeCode.Single:
                return bi.ToSingle(null);
              case TypeCode.Double:
                return bi.ToDouble(null);
            }
          }
          return base.ConvertTo(context, culture, value, destinationType);
        }
      }
  
      private const int BitsPerDigit = 32;
      private const ulong Base = 0x100000000;
  
      private readonly short sign;
      private readonly uint[] data;
  
      [SuppressMessage("Microsoft.Security", "CA2104:DoNotDeclareReadOnlyMutableReferenceTypes")]
      public static readonly BigInteger Zero = new BigInteger(0, new uint[0]);
      [SuppressMessage("Microsoft.Security", "CA2104:DoNotDeclareReadOnlyMutableReferenceTypes")]
      public static readonly BigInteger One = new BigInteger(+1, new uint[] { 1 });
  
      [CLSCompliant(false)]
      public static BigInteger Create(ulong v) {
        return new BigInteger(+1, (uint)v, (uint)(v >> BitsPerDigit));
      }
  
      [CLSCompliant(false)]
      public static BigInteger Create(uint v) {
        if (v == 0) return Zero;
        else if (v == 1) return One;
        else return new BigInteger(+1, v);
      }
  
      public static BigInteger Create(long v) {
        ulong x;
        int s = +1;
        if (v < 0) {
          x = (ulong)-v; s = -1;
        } else {
          x = (ulong)v;
        }
  
        //Console.WriteLine("{0}, {1}, {2}, {3}", v, x, (uint)x, (uint)(x >> BitsPerDigit));
        return new BigInteger(s, (uint)x, (uint)(x >> BitsPerDigit));
      }
  
      public static BigInteger Create(int v) {
        if (v == 0) return Zero;
        else if (v == 1) return One;
        else if (v < 0) return new BigInteger(-1, (uint)-v);
        else return new BigInteger(+1, (uint)v);
      }
  
      private const Int32 DecimalScaleFactorMask = 0x00FF0000;
      private const Int32 DecimalSignMask = unchecked((Int32)0x80000000);
  
      public static BigInteger Create(decimal v) {
        // First truncate to get scale to 0 and extract bits
        int[] bits = Decimal.GetBits(Decimal.Truncate(v));
  
        Debug.Assert(bits.Length == 4 && (bits[3] & DecimalScaleFactorMask) == 0);
  
        int size = 3;
        while (size > 0 && bits[size - 1] == 0) size--;
  
        if (size == 0) {
          return BigInteger.Zero;
        }
  
        UInt32[] array = new UInt32[size];
        array[0] = (UInt32)bits[0];
        if (size > 1) array[1] = (UInt32)bits[1];
        if (size > 2) array[2] = (UInt32)bits[2];
  
        return new BigInteger(((bits[3] & DecimalSignMask) != 0) ? -1 : +1, array);
      }
  
      /// <summary>
      /// Create a BigInteger from a little-endian twos-complement byte array
      /// (inverse of ToByteArray())
      /// </summary>
      public static BigInteger Create(byte[] v) {
        //Contract.RequiresNotNull(v, "v");
        if (v.Length == 0) return Create(0);
  
        int byteCount = v.Length;
        int unalignedBytes = byteCount % 4;
        int dwordCount = byteCount / 4 + (unalignedBytes == 0 ? 0 : 1);
        uint[] data = new uint[dwordCount];
  
        bool isNegative = (v[byteCount - 1] & 0x80) == 0x80;
  
        bool isZero = true;
  
        // Copy all dwords, except but don't do the last one if it's not a full four bytes
        int curDword, curByte, byteInDword;
        curByte = 3;
        for (curDword = 0; curDword < dwordCount - (unalignedBytes == 0 ? 0 : 1); curDword++) {
          byteInDword = 0;
          while (byteInDword < 4) {
            if (v[curByte] != 0x00) isZero = false;
            data[curDword] <<= 8;
            data[curDword] |= v[curByte];
            curByte--;
            byteInDword++;
          }
          curByte += 8;
        }
  
        // Copy the last dword specially if it's not aligned
        if (unalignedBytes != 0) {
          if (isNegative) data[dwordCount - 1] = 0xffffffff;
          for (curByte = byteCount - 1; curByte >= byteCount - unalignedBytes; curByte--) {
            if (v[curByte] != 0x00) isZero = false;
            data[curDword] <<= 8;
            data[curDword] |= v[curByte];
          }
        }
  
        if (isZero) return Zero;
  
        if (isNegative) {
          makeTwosComplement(data);
          return new BigInteger(-1, data);
        }
        return new BigInteger(1, data);
      }
  
  
      private static bool Negative(byte[] v) {
        return ((v[7] & 0x80) != 0);
      }
  
      private static ushort Exponent(byte[] v) {
        return (ushort)((((ushort)(v[7] & 0x7F)) << (ushort)4) | (((ushort)(v[6] & 0xF0)) >> 4));
      }
  
      private static ulong Mantissa(byte[] v) {
        uint i1 = ((uint)v[0] | ((uint)v[1] << 8) | ((uint)v[2] << 16) | ((uint)v[3] << 24));
        uint i2 = ((uint)v[4] | ((uint)v[5] << 8) | ((uint)(v[6] & 0xF) << 16));
  
        return (ulong)((ulong)i1 | ((ulong)i2 << 32));
      }
  
      private const int bias = 1075; //RI: changed from static field to const, to avoid security warning
      public static BigInteger Create(double v) {
        byte[] bytes = System.BitConverter.GetBytes(v);
        ulong mantissa = Mantissa(bytes);
        if (mantissa == 0) {
          // 1.0 * 2**exp, we have a power of 2
          int exponent = Exponent(bytes);
          if (exponent == 0) return Zero;
  
          BigInteger res = Negative(bytes) ? Negate(One) : One;
          res = res << (exponent - 0x3ff);
          return res;
        } else {
          // 1.mantissa * 2**exp
          int exponent = Exponent(bytes);
          mantissa |= 0x10000000000000ul;
          BigInteger res = BigInteger.Create(mantissa);
          res = exponent > bias ? res << (exponent - bias) : res >> (bias - exponent);
          return Negative(bytes) ? res * (-1) : res;
        }
      }
  
      public static implicit operator BigInteger(byte i) {
        return Create((uint)i);
      }
  
      [CLSCompliant(false)]
      public static implicit operator BigInteger(sbyte i) {
        return Create((int)i);
      }
  
      public static implicit operator BigInteger(short i) {
        return Create((int)i);
      }
  
      [CLSCompliant(false)]
      public static implicit operator BigInteger(ushort i) {
        return Create((uint)i);
      }
  
      [CLSCompliant(false)]
      public static implicit operator BigInteger(uint i) {
        return Create(i);
      }
  
      public static implicit operator BigInteger(int i) {
        return Create(i);
      }
  
      [CLSCompliant(false)]
      public static implicit operator BigInteger(ulong i) {
        return Create(i);
      }
  
      public static implicit operator BigInteger(long i) {
        return Create(i);
      }
  
      public static implicit operator BigInteger(decimal i) {
        return Create(i);
      }
  
      public static implicit operator double(BigInteger i) {
        if (object.ReferenceEquals(i, null)) {
          throw new ArgumentNullException("i");
        }
        return i.ToFloat64();
      }
  
      public static explicit operator byte(BigInteger self) {
        int tmp;
        if (self.AsInt32(out tmp)) {
          return checked((byte)tmp);
        }
        throw new OverflowException();
      }
  
      [CLSCompliant(false)]
      public static explicit operator sbyte(BigInteger self) {
        int tmp;
        if (self.AsInt32(out tmp)) {
          return checked((sbyte)tmp);
        }
        throw new OverflowException();
      }
  
      [CLSCompliant(false)]
      public static explicit operator UInt16(BigInteger self) {
        int tmp;
        if (self.AsInt32(out tmp)) {
          return checked((UInt16)tmp);
        }
        throw new OverflowException();
      }
  
      public static explicit operator Int16(BigInteger self) {
        int tmp;
        if (self.AsInt32(out tmp)) {
          return checked((Int16)tmp);
        }
        throw new OverflowException();
      }
  
      [CLSCompliant(false)]
      public static explicit operator UInt32(BigInteger self) {
        uint tmp;
        if (self.AsUInt32(out tmp)) {
          return tmp;
        }
        throw new OverflowException();
      }
  
      public static explicit operator Int32(BigInteger self) {
        int tmp;
        if (self.AsInt32(out tmp)) {
          return tmp;
        }
        throw new OverflowException();
      }
  
      public static explicit operator Int64(BigInteger self) {
        long tmp;
        if (self.AsInt64(out tmp)) {
          return tmp;
        }
        throw new OverflowException();
      }
  
      [CLSCompliant(false)]
      public static explicit operator UInt64(BigInteger self) {
        ulong tmp;
        if (self.AsUInt64(out tmp)) {
          return tmp;
        }
        throw new OverflowException();
      }
  
      public static explicit operator float(BigInteger self) {
        if (object.ReferenceEquals(self, null)) {
          throw new ArgumentNullException("self");
        }
        return checked((float)self.ToFloat64());
      }
  
      public static explicit operator decimal(BigInteger self) {
        decimal res;
        if (self.AsDecimal(out res)) {
          return res;
        }
        throw new OverflowException();
      }
  
      public BigInteger(BigInteger copy) {
        if (object.ReferenceEquals(copy, null)) {
          throw new ArgumentNullException("copy");
        }
        this.sign = copy.sign;
        this.data = copy.data;
      }
  
      [CLSCompliant(false)]
      public BigInteger(int sign, params uint[] data) {
        //Contract.RequiresNotNull(data, "data");
        if (sign != -1 && sign != 0 && sign != 1) throw new ArgumentException(MathResources.InvalidArgument, "sign");
        if (GetLength(data) != 0) {
          if (sign == 0) throw new ArgumentException(MathResources.InvalidArgument, "sign");
        } else sign = 0;
  
        this.data = data;
        this.sign = (short)sign;
      }
  
      /// <summary>
      /// Return the magnitude of this BigInteger as an array of zero or more uints.
      /// Element zero is the value of the least significant four bytes, element one is
      /// the value of the four next most significant bytes, etc.
      /// 
      /// The returned data is the unsigned magnitude of the number. To determine the sign,
      /// use GetSign().
      /// 
      /// It is guaranteed that the highest element of the returned array is never zero.
      /// This means that if the value of this BigInteger is zero, a zero-length array
      /// is returned.
      /// </summary>
      [CLSCompliant(false)]
      public uint[] GetBits() {
        if (sign == 0) return new uint[0];
        int mostSignificantNonZeroWord;
        for (
            mostSignificantNonZeroWord = data.Length - 1;
            mostSignificantNonZeroWord >= 0 && data[mostSignificantNonZeroWord] == 0;
            mostSignificantNonZeroWord--
        ) ;
        uint[] bits = new uint[mostSignificantNonZeroWord + 1];
        Array.Copy(data, bits, mostSignificantNonZeroWord + 1);
        return bits;
      }
  
      /// <summary>
      /// Return the sign of this BigInteger: -1, 0, or 1.
      /// </summary>
      public short Sign {
        get {
          return sign;
        }
      }
  
      public bool AsInt64(out long ret) {
        ret = 0;
        if (sign == 0) return true;
        if (Length > 2) return false;
        if (data.Length == 1) {
          ret = sign * (long)data[0];
          return true;
        }
        ulong tmp = (((ulong)data[1]) << 32 | (ulong)data[0]);
        if (tmp > 0x8000000000000000) return false;
        if (tmp == 0x8000000000000000 && sign == 1) return false;
        ret = ((long)tmp) * sign;
        return true;
      }
  
      [CLSCompliant(false)]
      public bool AsUInt32(out uint ret) {
        ret = 0;
        if (sign == 0) return true;
        if (sign < 0) return false;
        if (Length > 1) return false;
        ret = data[0];
        return true;
      }
  
      [CLSCompliant(false)]
      public bool AsUInt64(out ulong ret) {
        ret = 0;
        if (sign == 0) return true;
        if (sign < 0) return false;
        if (Length > 2) return false;
        ret = (ulong)data[0];
        if (data.Length > 1) {
          ret |= ((ulong)data[1]) << 32;
        }
        return true;
      }
  
      public bool AsInt32(out int ret) {
        ret = 0;
        if (sign == 0) return true;
        if (Length > 1) return false;
        if (data[0] > 0x80000000) return false;
        if (data[0] == 0x80000000 && sign == 1) return false;
        ret = (int)data[0];
        ret *= sign;
        return true;
      }
  
      public bool AsDecimal(out Decimal ret) {
        if (sign == 0) {
          ret = Decimal.Zero;
          return true;
        }
  
        BigInteger bi = this;
  
        int scale = 0;
        int length = Length;
        while (length > 3) {
          if (scale >= 28) {
            ret = default(decimal);
            return false;
          }
          bi = bi / 10;
          scale++;
  
          length = bi.Length;
        }
  
        int lo = 0, mi = 0, hi = 0;
        if (length > 2) hi = (Int32)bi.data[2];
        if (length > 1) mi = (Int32)bi.data[1];
        if (length > 0) lo = (Int32)bi.data[0];
  
        ret = new Decimal(lo, mi, hi, sign < 0, (byte)scale);
        return true;
      }
  
  
      [CLSCompliant(false)]
      public uint ToUInt32() {
        uint ret;
        if (AsUInt32(out ret)) return ret;
        throw new OverflowException(MathResources.BigIntWontFitUInt);
      }
  
      public int ToInt32() {
        int ret;
        if (AsInt32(out ret)) return ret;
        throw new OverflowException(MathResources.BigIntWontFitInt);
      }
  
      public decimal ToDecimal() {
        decimal ret;
        if (AsDecimal(out ret)) return ret;
        throw new OverflowException(MathResources.BigIntWontFitDecimal);
      }
  
      [CLSCompliant(false)]
      public ulong ToUInt64() {
        ulong ret;
        if (AsUInt64(out ret)) return ret;
        throw new OverflowException(MathResources.BigIntWontFitULong);
      }
  
      public long ToInt64() {
        long ret;
        if (AsInt64(out ret)) return ret;
        throw new OverflowException(MathResources.BigIntWontFitLong);
      }
  
      public bool TryToFloat64(out double result) {
        return double.TryParse(ToString(10),
            System.Globalization.NumberStyles.Number,
            System.Globalization.CultureInfo.InvariantCulture.NumberFormat,
            out result);
      }
  
      public double ToFloat64() {
        return double.Parse(
            ToString(10),
            System.Globalization.CultureInfo.InvariantCulture.NumberFormat
            );
      }
  
      public int Length {
        get {
          return GetLength(data);
        }
      }
  
      private static int GetLength(uint[] data) {
        int ret = data.Length - 1;
        while (ret >= 0 && data[ret] == 0) ret--;
        return ret + 1;
      }
  
  
      private static uint[] copy(uint[] v) {
        uint[] ret = new uint[v.Length];
        Array.Copy(v, ret, v.Length);
        return ret;
      }
  
      private static uint[] resize(uint[] v, int len) {
        if (v.Length == len) return v;
        uint[] ret = new uint[len];
        int n = System.Math.Min(v.Length, len);
        for (int i = 0; i < n; i++) {
          ret[i] = v[i];
        }
        return ret;
      }
  
      private static uint[] InternalAdd(uint[] x, int xl, uint[] y, int yl) {
        Debug.Assert(xl >= yl);
        uint[] z = new uint[xl];
  
        int i;
        ulong sum = 0;
        for (i = 0; i < yl; i++) {
          sum = sum + x[i] + y[i];
          z[i] = (uint)sum;
          sum >>= BitsPerDigit;
        }
  
        for (; i < xl && sum != 0; i++) {
          sum = sum + x[i];
          z[i] = (uint)sum;
          sum >>= BitsPerDigit;
        }
        if (sum != 0) {
          z = resize(z, xl + 1);
          z[i] = (uint)sum;
        } else {
          for (; i < xl; i++) {
            z[i] = x[i];
          }
        }
        return z;
      }
  
      private static uint[] sub(uint[] x, int xl, uint[] y, int yl) {
        Debug.Assert(xl >= yl);
        uint[] z = new uint[xl];
  
        int i;
        bool borrow = false;
        for (i = 0; i < yl; i++) {
          uint xi = x[i];
          uint yi = y[i];
          if (borrow) {
            if (xi == 0) {
              xi = 0xffffffff;
              borrow = true;
            } else {
              xi -= 1;
              borrow = false;
            }
          }
          if (yi > xi) borrow = true;
          z[i] = xi - yi;
        }
  
        if (borrow) {
          for (; i < xl; i++) {
            uint xi = x[i];
            z[i] = xi - 1;
            if (xi != 0) { i++; break; }
          }
        }
        for (; i < xl; i++) {
          z[i] = x[i];
        }
        return z;  // may have leading zeros
      }
  
      private static uint[] add0(uint[] x, int xl, uint[] y, int yl) {
        if (xl >= yl) return InternalAdd(x, xl, y, yl);
        else return InternalAdd(y, yl, x, xl);
      }
  
      public static int Compare(BigInteger x, BigInteger y) {
        if (object.ReferenceEquals(x, null)) {
          throw new ArgumentNullException("x");
        }
        if (object.ReferenceEquals(y, null)) {
          throw new ArgumentNullException("y");
        }
        if (x.sign == y.sign) {
          int xl = x.Length;
          int yl = y.Length;
          if (xl == yl) {
            for (int i = xl - 1; i >= 0; i--) {
              if (x.data[i] == y.data[i]) continue;
              return x.data[i] > y.data[i] ? x.sign : -x.sign;
            }
            return 0;
          } else {
            return xl > yl ? +x.sign : -x.sign;
          }
        } else {
          return x.sign > y.sign ? +1 : -1;
        }
      }
  
      public static bool operator ==(BigInteger x, int y) {
        return x == (BigInteger)y;
      }
  
      public static bool operator !=(BigInteger x, int y) {
        return !(x == y);
      }
  
      public static bool operator ==(BigInteger x, double y) {
        if (object.ReferenceEquals(x, null)) {
          throw new ArgumentNullException("x");
        }
  
        // we can hold all double values, but not all double values
        // can hold BigInteger values, and we may lose precision.  Convert
        // the double to a big int, then compare.
  
        if ((y % 1) != 0) return false;  // not a whole number, can't be equal
  
        return x == BigInteger.Create(y);
      }
  
      public static bool operator ==(double x, BigInteger y) {
        return y == x;
      }
  
      public static bool operator !=(BigInteger x, double y) {
        return !(x == y);
      }
  
      public static bool operator !=(double x, BigInteger y) {
        return !(x == y);
      }
  
  
      public static bool operator ==(BigInteger x, BigInteger y) {
        return Compare(x, y) == 0;
      }
  
      public static bool operator !=(BigInteger x, BigInteger y) {
        return Compare(x, y) != 0;
      }
      public static bool operator <(BigInteger x, BigInteger y) {
        return Compare(x, y) < 0;
      }
      public static bool operator <=(BigInteger x, BigInteger y) {
        return Compare(x, y) <= 0;
      }
      public static bool operator >(BigInteger x, BigInteger y) {
        return Compare(x, y) > 0;
      }
      public static bool operator >=(BigInteger x, BigInteger y) {
        return Compare(x, y) >= 0;
      }
  
      public static BigInteger Add(BigInteger x, BigInteger y) {
        return x + y;
      }
  
      public static BigInteger operator +(BigInteger x, BigInteger y) {
        if (object.ReferenceEquals(x, null)) {
          throw new ArgumentNullException("x");
        }
        if (object.ReferenceEquals(y, null)) {
          throw new ArgumentNullException("y");
        }
  
        if (x.sign == y.sign) {
          return new BigInteger(x.sign, add0(x.data, x.Length, y.data, y.Length));
        } else {
          return x - new BigInteger(-y.sign, y.data);  //??? performance issue
        }
      }
  
      public static BigInteger Subtract(BigInteger x, BigInteger y) {
        return x - y;
      }
  
      public static BigInteger operator -(BigInteger x, BigInteger y) {
        int c = Compare(x, y);
        if (c == 0) return Zero;
  
        if (x.sign == y.sign) {
          uint[] z;
          switch (c * x.sign) {
            case +1:
              z = sub(x.data, x.Length, y.data, y.Length);
              break;
            case -1:
              z = sub(y.data, y.Length, x.data, x.Length);
              break;
            default:
              return Zero;
          }
  
gt:         return new BigInteger(c, z);