BigIntX.cs

Variable Bit Width Big Unsigned or Signed Integer 32,64,128,256,512,1024,204,4096 Bit. (Experimental)

using System;
using System.Collections;
using System.Collections.Generic;
using System.ComponentModel;
using System.Diagnostics;
using System.Globalization;
using System.Numerics;
using System.Text;
[Serializable]
[TypeConverter(typeof(BigIntXConverter))]
[DebuggerDisplay("{DDisplay}")]
public struct BigIntX : IComparable<BigIntX>, IComparable, IEquatable<BigIntX>, IConvertible, IFormattable
{
    internal DigitsArray _digitsArray;
    public BigIntX(byte number) : this((ulong)number)
    {
    }
    public BigIntX(sbyte number) : this((long)number)
    {
    }
    public BigIntX(bool number) : this((ulong)(number ? 1 : 0))
    {
    }
    public BigIntX(char number) : this((ulong)number)
    {
    }
    public BigIntX(short number) : this((long)number)
    {
    }
    public BigIntX(ushort number) : this((ulong)number)
    {
    }
    public BigIntX(int number) : this((long)number)
    {
    }
    public BigIntX(uint number) : this((ulong)number)
    {
    }
    public BigIntX(BigDecimal number)
    {
        var array    = number.UnscaledValue.ToByteArray();
        var length   = array.Length;
        var offset   = 0;
        var estSize  = length / 4;
        var leftOver = length & 3;
        if (leftOver != 0)
            ++estSize;
        _digitsArray = new DigitsArray(estSize + 1, 0);
        for (int i = offset + length - 1, j = 0; i - offset >= 3; i -= 4, j++)
        {
            _digitsArray[j] = (uint)((array[i - 3] << 24) + (array[i - 2] << 16) + (array[i - 1] << 8) + array[i]);
            _digitsArray.DataUsed++;
        }
        uint accumulator = 0;
        for (var i = leftOver; i > 0; i--)
        {
            uint digit = array[offset + leftOver - i];
            digit       =  digit << ((i - 1) * 8);
            accumulator |= digit;
        }
        _digitsArray[_digitsArray.DataUsed] = accumulator;
        _digitsArray.ResetDataUsed();
    }
    public BigIntX(BigInteger number)
    {
        var array    = number.ToByteArray().Invert();
        var length   = array.Length;
        var offset   = 0;
        var estSize  = length / 4;
        var leftOver = length & 3;
        if (leftOver != 0)
            ++estSize;
        _digitsArray = new DigitsArray(estSize + 1, 0);
        for (int i = offset + length - 1, j = 0; i - offset >= 3; i -= 4, j++)
        {
            _digitsArray[j] = (uint)((array[i - 3] << 24) + (array[i - 2] << 16) + (array[i - 1] << 8) + array[i]);
            _digitsArray.DataUsed++;
        }
        uint accumulator = 0;
        for (var i = leftOver; i > 0; i--)
        {
            uint digit = array[offset + leftOver - i];
            digit       =  digit << ((i - 1) * 8);
            accumulator |= digit;
        }
        _digitsArray[_digitsArray.DataUsed] = accumulator;
        _digitsArray.ResetDataUsed();
    }
    public BigIntX(decimal number)
    {
        var bits   = decimal.GetBits(decimal.Truncate(number));
        var length = 3;
        while (length > 0 && bits[length - 1] == 0)
            --length;
        var IsNegative = (bits[3] & int.MinValue) != 0;
        _digitsArray = new DigitsArray(3, 0);
        if (length == 0)
        {
            ConstructFrom(new byte[] { 0 }, 0, 1);
            return;
        }
        if (length == 1)
        {
            if (!IsNegative)
            {
                _digitsArray.Data[0] = (uint)bits[0];
            }
            else
            {
                _digitsArray.Data[0] = DigitsArray.AllBits - (uint)bits[0] + 1;
                _digitsArray.Data[1] = DigitsArray.AllBits                 - (uint)bits[1];
                _digitsArray.Data[2] = DigitsArray.AllBits                 - (uint)bits[2];
                _digitsArray.Data[3] = DigitsArray.AllBits;
            }
            _digitsArray.ResetDataUsed();
            return;
        }
        if (length == 2)
        {
            if (!IsNegative)
            {
                _digitsArray.Data[0] = (uint)bits[0];
                _digitsArray.Data[1] = (uint)bits[1];
            }
            else
            {
                _digitsArray.Data[0] = DigitsArray.AllBits - (uint)bits[0] + 1;
                _digitsArray.Data[1] = DigitsArray.AllBits                 - (uint)bits[1];
                _digitsArray.Data[2] = DigitsArray.AllBits                 - (uint)bits[2];
                _digitsArray.Data[3] = DigitsArray.AllBits;
            }
            _digitsArray.ResetDataUsed();
            return;
        }
        if (length == 3)
        {
            if (!IsNegative)
            {
                _digitsArray.Data[0] = (uint)bits[0];
                _digitsArray.Data[1] = (uint)bits[1];
                _digitsArray.Data[2] = (uint)bits[2];
            }
            else
            {
                _digitsArray.Data[0] = DigitsArray.AllBits - (uint)bits[0] + 1;
                _digitsArray.Data[1] = DigitsArray.AllBits                 - (uint)bits[1];
                _digitsArray.Data[2] = DigitsArray.AllBits                 - (uint)bits[2];
                _digitsArray.Data[3] = DigitsArray.AllBits;
            }
            _digitsArray.ResetDataUsed();
        }
    }
    public BigIntX(double value) : this((decimal)value)
    {
    }
    public BigIntX(float value) : this((decimal)value)
    {
    }
    public BigIntX(Guid value) : this(value.ToByteArray())
    {
    }
    public BigIntX(long number)
    {
        _digitsArray = new DigitsArray(8 / DigitsArray.DataSizeOf + 1, 0);
        while (number != 0 && _digitsArray.DataUsed < _digitsArray.Count)
        {
            _digitsArray[_digitsArray.DataUsed] =   (uint)(number & DigitsArray.AllBits);
            number                              >>= DigitsArray.DataSizeBits;
            _digitsArray.DataUsed++;
        }
        _digitsArray.ResetDataUsed();
    }
    public BigIntX(ulong number)
    {
        _digitsArray = new DigitsArray(8 / DigitsArray.DataSizeOf + 1, 0);
        while (number != 0 && _digitsArray.DataUsed < _digitsArray.Count)
        {
            _digitsArray[_digitsArray.DataUsed] =   (uint)(number & DigitsArray.AllBits);
            number                              >>= DigitsArray.DataSizeBits;
            _digitsArray.DataUsed++;
        }
        _digitsArray.ResetDataUsed();
    }
    public BigIntX(byte[] array) : this(array, 0, array.Length)
    {
    }
    public BigIntX(byte[] array, int length) : this(array, 0, length)
    {
    }
    public BigIntX(byte[] array, int offset, int length)
    {
        var estSize  = length / 4;
        var leftOver = length & 3;
        if (leftOver != 0)
            ++estSize;
        _digitsArray = new DigitsArray(estSize + 1, 0);
        for (int i = offset + length - 1, j = 0; i - offset >= 3; i -= 4, j++)
        {
            _digitsArray[j] = (uint)((array[i - 3] << 24) + (array[i - 2] << 16) + (array[i - 1] << 8) + array[i]);
            _digitsArray.DataUsed++;
        }
        uint accumulator = 0;
        for (var i = leftOver; i > 0; i--)
        {
            uint digit = array[offset + leftOver - i];
            digit       =  digit << ((i - 1) * 8);
            accumulator |= digit;
        }
        _digitsArray[_digitsArray.DataUsed] = accumulator;
        _digitsArray.ResetDataUsed();
    }
    public BigIntX(string digits) : this(digits, 10)
    {
    }
    public BigIntX(string digits, int radix)
    {
        if (digits == null)
            throw new ArgumentNullException("digits");
        var multiplier = new BigIntX(1);
        var result     = new BigIntX();
        digits = digits.ToUpper(CultureInfo.CurrentCulture).Trim();
        var nDigits = digits[0] == '-' ? 1 : 0;
        for (var idx = digits.Length - 1; idx >= nDigits; idx--)
        {
            var d = (int)digits[idx];
            if (d >= '0' && d <= '9')
                d -= '0';
            else if (d >= 'A' && d <= 'Z')
                d = d - 'A' + 10;
            else
                throw new ArgumentOutOfRangeException("digits");
            if (d >= radix)
                throw new ArgumentOutOfRangeException("digits");
            result     += multiplier * d;
            multiplier *= radix;
        }
        if (digits[0] == '-')
            result = -result;
        _digitsArray = result._digitsArray;
    }
    private BigIntX(DigitsArray digits)
    {
        digits.ResetDataUsed();
        _digitsArray = digits;
    }
    public BigIntX(xIntX value) : this(value.ToByteArray().Invert(), 0, value.ToByteArray().Length)
    {
    }
    internal BigIntX(uint[] rgu)
    {
        _digitsArray      = new DigitsArray(1, 1);
        _digitsArray.Data = rgu;
        _digitsArray.ResetDataUsed();
    }
    [DebuggerBrowsable(DebuggerBrowsableState.Never)]
    private string DDisplay => ToString();
    public bool IsNegative => _digitsArray.IsNegative;
    public bool IsZero     => _digitsArray.IsZero;
    public int  Sign       => _digitsArray.Sign;
    public bool IsPowerOfTwo
    {
        get
        {
            if (Sign != 1)
                return false;
            var index = Length(_digitsArray.Data) - 1;
            if (((int)_digitsArray.Data[index] & ((int)_digitsArray.Data[index] - 1)) != 0)
                return false;
            while (--index >= 0)
                if (_digitsArray.Data[index] != 0U)
                    return false;
            return true;
        }
    }
    public bool IsOne  => this     == 1;
    public bool IsEven => this % 2 == 0;
    int IComparable.CompareTo(object obj)
    {
        return Compare(this, (BigIntX)obj);
    }
    public int CompareTo(BigIntX value)
    {
        return Compare(this, value);
    }
    TypeCode IConvertible.GetTypeCode()
    {
        return TypeCode.Object;
    }
    public object ToType(Type conversionType, IFormatProvider provider)
    {
        object value;
        if (TryConvert(conversionType, provider, out value))
            return value;
        throw new InvalidCastException();
    }
    bool IConvertible.ToBoolean(IFormatProvider provider)
    {
        return bool.Parse(ToString());
    }
    byte IConvertible.ToByte(IFormatProvider provider)
    {
        return byte.Parse(ToString());
    }
    char IConvertible.ToChar(IFormatProvider provider)
    {
        return char.Parse(ToString());
    }
    DateTime IConvertible.ToDateTime(IFormatProvider provider)
    {
        return DateTime.Parse(ToString());
    }
    decimal IConvertible.ToDecimal(IFormatProvider provider)
    {
        return decimal.Parse(ToString());
    }
    double IConvertible.ToDouble(IFormatProvider provider)
    {
        return double.Parse(ToString());
    }
    short IConvertible.ToInt16(IFormatProvider provider)
    {
        return short.Parse(ToString());
    }
    ushort IConvertible.ToUInt16(IFormatProvider provider)
    {
        return ushort.Parse(ToString());
    }
    int IConvertible.ToInt32(IFormatProvider provider)
    {
        return int.Parse(ToString());
    }
    uint IConvertible.ToUInt32(IFormatProvider provider)
    {
        return uint.Parse(ToString());
    }
    long IConvertible.ToInt64(IFormatProvider provider)
    {
        return long.Parse(ToString());
    }
    ulong IConvertible.ToUInt64(IFormatProvider provider)
    {
        return ulong.Parse(ToString());
    }
    sbyte IConvertible.ToSByte(IFormatProvider provider)
    {
        return sbyte.Parse(ToString());
    }
    float IConvertible.ToSingle(IFormatProvider provider)
    {
        return float.Parse(ToString());
    }
    string IConvertible.ToString(IFormatProvider provider)
    {
        return ToString(null, provider);
    }
    public bool Equals(BigIntX obj)
    {
        if (ReferenceEquals(obj, null))
            return false;
        if (ReferenceEquals(this, obj))
            return true;
        var c = obj;
        if (_digitsArray.DataUsed != c._digitsArray.DataUsed)
            return false;
        for (var idx = 0; idx < _digitsArray.DataUsed; idx++)
            if (_digitsArray[idx] != c._digitsArray[idx])
                return false;
        return true;
    }
    public string ToString(string format, IFormatProvider formatProvider)
    {
        if (formatProvider == null)
            formatProvider = CultureInfo.CurrentCulture;
        if (!string.IsNullOrEmpty(format))
        {
            var ch = format[0];
            if (ch == 'x' || ch == 'X')
                if (int.TryParse(format.Substring(1).Trim(), out var min))
                    return ToHexString();
            if (ch != 'G' && ch != 'g' && ch != 'D' && ch != 'd')
                throw new NotSupportedException("Not supported format: " + format);
        }
        return ToString(10);
    }
    public bool TryConvert(Type conversionType, IFormatProvider provider, out object value)
    {
        if (conversionType == typeof(bool))
        {
            value = bool.Parse(ToString());
            return true;
        }
        if (conversionType == typeof(byte))
        {
            value = byte.Parse(ToString());
            return true;
        }
        if (conversionType == typeof(char))
        {
            value = char.Parse(ToString());
            return true;
        }
        if (conversionType == typeof(decimal))
        {
            value = decimal.Parse(ToString());
            return true;
        }
        if (conversionType == typeof(double))
        {
            value = double.Parse(ToString());
            return true;
        }
        if (conversionType == typeof(short))
        {
            value = short.Parse(ToString());
            return true;
        }
        if (conversionType == typeof(int))
        {
            value = int.Parse(ToString());
            return true;
        }
        if (conversionType == typeof(long))
        {
            value = long.Parse(ToString());
            return true;
        }
        if (conversionType == typeof(sbyte))
        {
            value = sbyte.Parse(ToString());
            return true;
        }
        if (conversionType == typeof(float))
        {
            value = float.Parse(ToString());
            return true;
        }
        if (conversionType == typeof(string))
        {
            value = ToString(null, provider);
            return true;
        }
        if (conversionType == typeof(ushort))
        {
            value = ushort.Parse(ToString());
            return true;
        }
        if (conversionType == typeof(uint))
        {
            value = uint.Parse(ToString());
            return true;
        }
        if (conversionType == typeof(ulong))
        {
            value = ulong.Parse(ToString());
            return true;
        }
        if (conversionType == typeof(byte[]))
        {
            value = ToByteArray();
            return true;
        }
        if (conversionType == typeof(Guid))
        {
            value = new Guid(ToByteArray());
            return true;
        }
        value = null;
        return false;
    }
    private void ConstructFrom(byte[] array, int offset, int length)
    {
        if (array == null)
            throw new ArgumentNullException("Array is null");
        if (offset > array.Length || length > array.Length)
            throw new ArgumentOutOfRangeException("Offset exceeds length");
        if (length > array.Length || offset + length > array.Length)
            throw new ArgumentOutOfRangeException("Length exceeds array length");
        var estSize  = length / 4;
        var leftOver = length & 3;
        if (leftOver != 0)
            ++estSize;
        _digitsArray = new DigitsArray(estSize + 1, 0);
        for (int i = offset + length - 1, j = 0; i - offset >= 3; i -= 4, j++)
        {
            _digitsArray[j] = (uint)((array[i - 3] << 24) + (array[i - 2] << 16) + (array[i - 1] << 8) + array[i]);
            _digitsArray.DataUsed++;
        }
        uint accumulator = 0;
        for (var i = leftOver; i > 0; i--)
        {
            uint digit = array[offset + leftOver - i];
            digit       =  digit << ((i - 1) * 8);
            accumulator |= digit;
        }
        _digitsArray[_digitsArray.DataUsed] = accumulator;
        _digitsArray.ResetDataUsed();
    }
    private void Construct(string digits, int radix)
    {
        if (digits == null)
            throw new ArgumentNullException("digits");
        var multiplier = new BigIntX(1);
        var result     = new BigIntX();
        digits = digits.ToUpper(CultureInfo.CurrentCulture).Trim();
        var nDigits = digits[0] == '-' ? 1 : 0;
        for (var idx = digits.Length - 1; idx >= nDigits; idx--)
        {
            var d = (int)digits[idx];
            if (d >= '0' && d <= '9')
                d -= '0';
            else if (d >= 'A' && d <= 'Z')
                d = d - 'A' + 10;
            else
                throw new ArgumentOutOfRangeException("digits");
            if (d >= radix)
                throw new ArgumentOutOfRangeException("digits");
            result     += multiplier * d;
            multiplier *= radix;
        }
        if (digits[0] == '-')
            result = -result;
        _digitsArray = result._digitsArray;
    }
    public static bool TryParseNum(string digits, int radix, out BigIntX result)
    {
        result = new BigIntX();
        if (digits == null)
            return false;
        var multiplier = new BigIntX(1);
        digits = digits.ToUpper(CultureInfo.CurrentCulture).Trim();
        var nDigits = digits[0] == '-' ? 1 : 0;
        for (var idx = digits.Length - 1; idx >= nDigits; idx--)
        {
            var d = (int)digits[idx];
            if (d >= '0' && d <= '9')
                d -= '0';
            else if (d >= 'A' && d <= 'Z')
                d = d - 'A' + 10;
            else
                return false;
            if (d >= radix)
                return false;
            result     += multiplier * d;
            multiplier *= radix;
        }
        if (digits[0] == '-')
            result = -result;
        return true;
    }
    public static BigIntX Parse(string value)
    {
        return Parse(value, NumberStyles.Integer, NumberFormatInfo.CurrentInfo);
    }
    public static BigIntX Parse(string value, NumberStyles style)
    {
        return Parse(value, style, NumberFormatInfo.CurrentInfo);
    }
    public static BigIntX Parse(string value, IFormatProvider provider)
    {
        return Parse(value, NumberStyles.Integer, NumberFormatInfo.GetInstance(provider));
    }
    public static BigIntX Parse(string value, NumberStyles style, IFormatProvider provider)
    {
        if (!TryParse(value, style, provider, out var result))
            throw new Exception($"TryParse value {value} failure.");
        return result;
    }
    public static bool TryParse(string value, out BigIntX result)
    {
        return TryParse(value, NumberStyles.Integer, NumberFormatInfo.CurrentInfo, out result);
    }
    public static bool TryParse(string value, NumberStyles style, IFormatProvider provider, out BigIntX result)
    {
        result = new BigIntX();
        if (string.IsNullOrEmpty(value))
            return false;
        if (value.StartsWith("x", StringComparison.OrdinalIgnoreCase))
        {
            style |= NumberStyles.AllowHexSpecifier;
            value =  value.Substring(1);
        }
        else
        {
            if (value.StartsWith("0x", StringComparison.OrdinalIgnoreCase))
            {
                style |= NumberStyles.AllowHexSpecifier;
                value =  value.Substring(2);
            }
        }
        if ((style & NumberStyles.AllowHexSpecifier) == NumberStyles.AllowHexSpecifier)
            return TryParseNum(value, 16, out result);
        return TryParseNum(value, 10, out result);
    }
    public static implicit operator BigIntX(BigDecimal value)
    {
        return new BigIntX(value);
    }
    public static implicit operator BigIntX(BigInteger value)
    {
        return new BigIntX(value);
    }
    public static implicit operator BigIntX(xIntX value)
    {
        return new BigIntX(value);
    }
    public static implicit operator BigIntX(bool value)
    {
        return new BigIntX(value);
    }
    public static implicit operator BigIntX(byte value)
    {
        return new BigIntX(value);
    }
    public static implicit operator BigIntX(char value)
    {
        return new BigIntX(value);
    }
    public static explicit operator BigIntX(decimal value)
    {
        return new BigIntX(value);
    }
    public static explicit operator BigIntX(double value)
    {
        return new BigIntX(value);
    }
    public static explicit operator BigIntX(float value)
    {
        return new BigIntX(value);
    }
    public static implicit operator BigIntX(short value)
    {
        return new BigIntX(value);
    }
    public static implicit operator BigIntX(ushort value)
    {
        return new BigIntX(value);
    }
    public static implicit operator BigIntX(sbyte value)
    {
        return new BigIntX(value);
    }
    public static implicit operator BigIntX(long value)
    {
        return new BigIntX(value);
    }
    public static implicit operator BigIntX(ulong value)
    {
        return new BigIntX(value);
    }
    public static implicit operator BigIntX(int value)
    {
        return new BigIntX(value);
    }
    public static explicit operator byte(BigIntX value)
    {
        return checked((byte)(int)value);
    }
    public static explicit operator sbyte(BigIntX value)
    {
        return checked((sbyte)(int)value);
    }
    public static implicit operator BigIntX(uint value)
    {
        return new BigIntX((ulong)value);
    }
    public static explicit operator short(BigIntX value)
    {
        return checked((short)(int)value);
    }
    public static explicit operator ushort(BigIntX value)
    {
        return checked((ushort)(int)value);
    }
    public static explicit operator BigInteger(BigIntX value)
    {
        return new BigInteger(value.ToByteArray());
    }
    public static explicit operator xIntX(BigIntX value)
    {
        return new xIntX(value.ToByteArray());
    }
    public static explicit operator int(BigIntX value)
    {
        if (value.IsZero)
            return 0;
        if (value.Sign > 0)
            return checked((int)value._digitsArray.Data[0]);
        if (value > int.MaxValue)
            throw new OverflowException("int overflow.");
        return -(int)value._digitsArray.Data[0];
    }
    public static explicit operator uint(BigIntX value)
    {
        return value._digitsArray.Data[0];
    }
    public static explicit operator long(BigIntX value)
    {
        if (value > long.MaxValue)
            throw new OverflowException("long overflow.");
        var uu = value._digitsArray.Data.Length - 1 <= 1 ? value._digitsArray.Data[0] : ((ulong)value._digitsArray.Data[1] << 32) | value._digitsArray.Data[0];
        var ll = value.Sign                         > 0 ? (long)uu : -(long)uu;
        if (ll > 0L && value.Sign > 0 || ll < 0L && value.Sign < 0)
            return ll;
        throw new OverflowException("long overflow.");
    }
    public static explicit operator ulong(BigIntX value)
    {
        if (value > ulong.MaxValue)
            throw new OverflowException("ulong overflow.");
        if (value._digitsArray.Data.Length - 1 > 1)
            return ((ulong)value._digitsArray.Data[1] << 32) | value._digitsArray.Data[0];
        return value._digitsArray.Data[0];
    }
    public static decimal ToDecimal(BigIntX value)
    {
        var len = value._digitsArray.Data.Length - 1;
        if (len > 3)
            throw new OverflowException("Decimal overflow.");
        ;
        var lo  = 0;
        var mid = 0;
        var hi  = 0;
        if (len > 2)
            hi = (int)value._digitsArray.Data[2];
        if (len > 1)
            mid = (int)value._digitsArray.Data[1];
        if (len > 0)
            lo = (int)value._digitsArray.Data[0];
        return new decimal(lo, mid, hi, value.Sign < 0, 0);
    }
    public static explicit operator decimal(BigIntX value)
    {
        var len = value._digitsArray.Data.Length - 1;
        if (len > 3)
            throw new OverflowException("Decimal overflow.");
        ;
        var lo  = 0;
        var mid = 0;
        var hi  = 0;
        if (len > 2)
            hi = (int)value._digitsArray.Data[2];
        if (len > 1)
            mid = (int)value._digitsArray.Data[1];
        if (len > 0)
            lo = (int)value._digitsArray.Data[0];
        return new decimal(lo, mid, hi, value.Sign < 0, 0);
    }
    public static BigIntX operator +(BigIntX left, BigIntX right)
    {
        var  size  = Math.Max(left._digitsArray.DataUsed, right._digitsArray.DataUsed);
        var  da    = new DigitsArray(size + 1);
        long carry = 0;
        for (var i = 0; i < da.Count; i++)
        {
            var sum = left._digitsArray[i] + (long)right._digitsArray[i] + carry;
            carry = sum >> DigitsArray.DataSizeBits;
            da[i] = (uint)(sum & DigitsArray.AllBits);
        }
        return new BigIntX(da);
    }
    public static BigIntX Add(BigIntX left, BigIntX right)
    {
        return left + right;
    }
    public static BigIntX operator ++(BigIntX left)
    {
        return left + 1;
    }
    public static BigIntX Increment(BigIntX left)
    {
        return left + 1;
    }
    public static BigIntX operator -(BigIntX left, BigIntX right)
    {
        var  size  = Math.Max(left._digitsArray.DataUsed, right._digitsArray.DataUsed) + 1;
        var  da    = new DigitsArray(size);
        long carry = 0;
        for (var i = 0; i < da.Count; i++)
        {
            var diff = left._digitsArray[i] - (long)right._digitsArray[i] - carry;
            da[i] = (uint)(diff & DigitsArray.AllBits);
            da.DataUsed++;
            carry = diff < 0 ? 1 : 0;
        }
        return new BigIntX(da);
    }
    public static BigIntX Subtract(BigIntX left, BigIntX right)
    {
        return left - right;
    }
    public static BigIntX operator --(BigIntX left)
    {
        return left - 1;
    }
    public static BigIntX Decrement(BigIntX left)
    {
        return left - 1;
    }
    public static BigIntX operator -(BigIntX left)
    {
        if (ReferenceEquals(left, null))
            throw new ArgumentNullException("left");
        if (left.IsZero)
            return new BigIntX(0);
        var da = new DigitsArray(left._digitsArray.DataUsed + 1, left._digitsArray.DataUsed + 1);
        for (var i = 0; i < da.Count; i++)
            da[i] = ~left._digitsArray[i];
        var carry = true;
        var index = 0;
        while (carry && index < da.Count)
        {
            var val = (long)da[index] + 1;
            da[index] = (uint)(val & DigitsArray.AllBits);
            carry     = val >> DigitsArray.DataSizeBits > 0;
            index++;
        }
        return new BigIntX(da);
    }
    public BigIntX Negate()
    {
        return -this;
    }
    public static BigIntX Abs(BigIntX left)
    {
        if (ReferenceEquals(left, null))
            throw new ArgumentNullException("left");
        if (left.IsNegative)
            return -left;
        return left;
    }
    public static BigIntX operator *(BigIntX left, BigIntX right)
    {
        if (ReferenceEquals(left, null))
            throw new ArgumentNullException("left");
        if (ReferenceEquals(right, null))
            throw new ArgumentNullException("right");
        var leftSideNeg  = left.IsNegative;
        var rightSideNeg = right.IsNegative;
        left  = Abs(left);
        right = Abs(right);
        var da = new DigitsArray(left._digitsArray.DataUsed + right._digitsArray.DataUsed);
        da.DataUsed = da.Count;
        for (var i = 0; i < left._digitsArray.DataUsed; i++)
        {
            ulong carry = 0;
            for (int j = 0, k = i; j < right._digitsArray.DataUsed; j++, k++)
            {
                var val = left._digitsArray[i] * (ulong)right._digitsArray[j] + da[k] + carry;
                da[k] = (uint)(val & DigitsArray.AllBits);
                carry = val >> DigitsArray.DataSizeBits;
            }
            if (carry != 0)
                da[i + right._digitsArray.DataUsed] = (uint)carry;
        }
        var result = new BigIntX(da);
        return leftSideNeg != rightSideNeg ? -result : result;
    }
    public static BigIntX Multiply(BigIntX left, BigIntX right)
    {
        return left * right;
    }
    public static BigIntX operator /(BigIntX left, BigIntX right)
    {
        if (left == null)
            throw new ArgumentNullException("left");
        if (right == null)
            throw new ArgumentNullException("right");
        if (right.IsZero)
            throw new DivideByZeroException();
        var divisorNeg  = right.IsNegative;
        var dividendNeg = left.IsNegative;
        left  = Abs(left);
        right = Abs(right);
        if (left < right)
            return new BigIntX(0);
        Divide(left, right, out var quotient, out var remainder);
        return dividendNeg != divisorNeg ? -quotient : quotient;
    }
    public static BigIntX Divide(BigIntX left, BigIntX right)
    {
        return left / right;
    }
    private static void Divide(BigIntX left, BigIntX right, out BigIntX quotient, out BigIntX remainder)
    {
        if (left.IsZero)
        {
            quotient  = new BigIntX();
            remainder = new BigIntX();
            return;
        }
        if (right._digitsArray.DataUsed == 1)
            SingleDivide(left, right, out quotient, out remainder);
        else
            MultiDivide(left, right, out quotient, out remainder);
    }
    private static void MultiDivide(BigIntX left, BigIntX right, out BigIntX quotient, out BigIntX remainder)
    {
        if (right.IsZero)
            throw new DivideByZeroException();
        var val = right._digitsArray[right._digitsArray.DataUsed - 1];
        var d   = 0;
        for (var mask = DigitsArray.HiBitSet; mask != 0 && (val & mask) == 0; mask >>= 1)
            d++;
        var remainderLen = left._digitsArray.DataUsed + 1;
        var remainderDat = new uint[remainderLen];
        left._digitsArray.CopyTo(remainderDat, 0, left._digitsArray.DataUsed);
        DigitsArray.ShiftLeft(remainderDat, d);
        right = right << d;
        ulong firstDivisor  = right._digitsArray[right._digitsArray.DataUsed - 1];
        ulong secondDivisor = right._digitsArray.DataUsed < 2 ? 0 : right._digitsArray[right._digitsArray.DataUsed - 2];
        var   divisorLen    = right._digitsArray.DataUsed + 1;
        var   dividendPart  = new DigitsArray(divisorLen, divisorLen);
        var   result        = new uint[left._digitsArray.Count + 1];
        var   resultPos     = 0;
        var   carryBit      = (ulong)0x1 << DigitsArray.DataSizeBits;
        for (int j = remainderLen - right._digitsArray.DataUsed, pos = remainderLen - 1; j > 0; j--, pos--)
        {
            var dividend = ((ulong)remainderDat[pos] << DigitsArray.DataSizeBits) + remainderDat[pos - 1];
            var qHat     = dividend / firstDivisor;
            var rHat     = dividend % firstDivisor;
            while (pos >= 2)
            {
                if (qHat == carryBit || qHat * secondDivisor > (rHat << DigitsArray.DataSizeBits) + remainderDat[pos - 2])
                {
                    qHat--;
                    rHat += firstDivisor;
                    if (rHat < carryBit)
                        continue;
                }
                break;
            }
            for (var h = 0; h < divisorLen; h++)
                dividendPart[divisorLen - h - 1] = remainderDat[pos - h];
            var dTemp = new BigIntX(dividendPart);
            var rTemp = right * (long)qHat;
            while (rTemp > dTemp)
            {
                qHat--;
                rTemp -= right;
            }
            rTemp = dTemp - rTemp;
            for (var h = 0; h < divisorLen; h++)
                remainderDat[pos - h] = rTemp._digitsArray[right._digitsArray.DataUsed - h];
            result[resultPos++] = (uint)qHat;
        }
        Array.Reverse(result, 0, resultPos);
        quotient = new BigIntX(new DigitsArray(result));
        var n   = DigitsArray.ShiftRight(remainderDat, d);
        var rDA = new DigitsArray(n, n);
        rDA.CopyFrom(remainderDat, 0, 0, rDA.DataUsed);
        remainder = new BigIntX(rDA);
    }
    private static void SingleDivide(BigIntX left, BigIntX right, out BigIntX quotient, out BigIntX remainder)
    {
        if (right.IsZero)
            throw new DivideByZeroException();
        var remainderDigits = new DigitsArray(left._digitsArray);
        remainderDigits.ResetDataUsed();
        var pos      = remainderDigits.DataUsed - 1;
        var divisor  = (ulong)right._digitsArray[0];
        var dividend = (ulong)remainderDigits[pos];
        var result   = new uint[left._digitsArray.Count];
        left._digitsArray.CopyTo(result, 0, result.Length);
        var resultPos = 0;
        if (dividend >= divisor)
        {
            result[resultPos++]  = (uint)(dividend / divisor);
            remainderDigits[pos] = (uint)(dividend % divisor);
        }
        pos--;
        while (pos >= 0)
        {
            dividend                 = ((ulong)remainderDigits[pos + 1] << DigitsArray.DataSizeBits) + remainderDigits[pos];
            result[resultPos++]      = (uint)(dividend / divisor);
            remainderDigits[pos + 1] = 0;
            remainderDigits[pos--]   = (uint)(dividend % divisor);
        }
        remainder = new BigIntX(remainderDigits);
        var quotientDigits = new DigitsArray(resultPos + 1, resultPos);
        var j              = 0;
        for (var i = quotientDigits.DataUsed - 1; i >= 0; i--, j++)
            quotientDigits[j] = result[i];
        quotient = new BigIntX(quotientDigits);
    }
    public static BigIntX operator %(BigIntX left, BigIntX right)
    {
        if (left == null)
            throw new ArgumentNullException("left");
        if (right == null)
            throw new ArgumentNullException("right");
        if (right.IsZero)
            throw new DivideByZeroException();
        BigIntX quotient;
        BigIntX remainder;
        var     dividendNeg = left.IsNegative;
        left  = Abs(left);
        right = Abs(right);
        if (left < right)
            return left;
        Divide(left, right, out quotient, out remainder);
        return dividendNeg ? -remainder : remainder;
    }
    public static BigIntX Modulus(BigIntX left, BigIntX right)
    {
        return left % right;
    }
    public BigIntX Pow(BigIntX power)
    {
        return Pow(this, power);
    }
    public static BigIntX operator &(BigIntX left, BigIntX right)
    {
        var len = Math.Max(left._digitsArray.DataUsed, right._digitsArray.DataUsed);
        var da  = new DigitsArray(len, len);
        for (var idx = 0; idx < len; idx++)
            da[idx] = left._digitsArray[idx] & right._digitsArray[idx];
        return new BigIntX(da);
    }
    public static BigIntX BitwiseAnd(BigIntX left, BigIntX right)
    {
        return left & right;
    }
    public static BigIntX operator |(BigIntX left, BigIntX right)
    {
        var len = Math.Max(left._digitsArray.DataUsed, right._digitsArray.DataUsed);
        var da  = new DigitsArray(len, len);
        for (var idx = 0; idx < len; idx++)
            da[idx] = left._digitsArray[idx] | right._digitsArray[idx];
        return new BigIntX(da);
    }
    public static BigIntX BitwiseOr(BigIntX left, BigIntX right)
    {
        return left | right;
    }
    public static BigIntX operator ^(BigIntX left, BigIntX right)
    {
        var len = Math.Max(left._digitsArray.DataUsed, right._digitsArray.DataUsed);
        var da  = new DigitsArray(len, len);
        for (var idx = 0; idx < len; idx++)
            da[idx] = left._digitsArray[idx] ^ right._digitsArray[idx];
        return new BigIntX(da);
    }
    public static BigIntX Xor(BigIntX left, BigIntX right)
    {
        return left ^ right;
    }
    public static BigIntX operator ~(BigIntX left)
    {
        var da = new DigitsArray(left._digitsArray.Count);
        for (var idx = 0; idx < da.Count; idx++)
            da[idx] = ~left._digitsArray[idx];
        return new BigIntX(da);
    }
    public static BigIntX OnesComplement(BigIntX left)
    {
        return ~left;
    }
    public static BigIntX operator <<(BigIntX left, int shiftCount)
    {
        if (left == null)
            throw new ArgumentNullException("left");
        var da = new DigitsArray(left._digitsArray);
        da.DataUsed = da.ShiftLeftWithoutOverflow(shiftCount);
        return new BigIntX(da);
    }
    public static BigIntX LeftShift(BigIntX left, int shiftCount)
    {
        return left << shiftCount;
    }
    public static BigIntX operator >> (BigIntX left, int shiftCount)
    {
        if (left == null)
            throw new ArgumentNullException("left");
        var da = new DigitsArray(left._digitsArray);
        da.DataUsed = da.ShiftRight(shiftCount);
        if (left.IsNegative)
        {
            for (var i = da.Count - 1; i >= da.DataUsed; i--)
                da[i] = DigitsArray.AllBits;
            var mask = DigitsArray.HiBitSet;
            for (var i = 0; i < DigitsArray.DataSizeBits; i++)
            {
                if ((da[da.DataUsed - 1] & mask) == DigitsArray.HiBitSet)
                    break;
                da[da.DataUsed - 1] |=  mask;
                mask                >>= 1;
            }
            da.DataUsed = da.Count;
        }
        return new BigIntX(da);
    }
    public static BigIntX RightShift(BigIntX left, int shiftCount)
    {
        if (left == null)
            throw new ArgumentNullException("left");
        return left >> shiftCount;
    }
    public static int Compare(BigIntX left, BigIntX right)
    {
        if (ReferenceEquals(left, right))
            return 0;
        if (ReferenceEquals(left, null))
            throw new ArgumentNullException("left");
        if (ReferenceEquals(right, null))
            throw new ArgumentNullException("right");
        if (left > right) return 1;
        if (left == right) return 0;
        return -1;
    }
    public static bool operator ==(BigIntX left, BigIntX right)
    {
        if (ReferenceEquals(left, right))
            return true;
        if (ReferenceEquals(left, null) || ReferenceEquals(right, null))
            return false;
        if (left.IsNegative != right.IsNegative)
            return false;
        return left.Equals(right);
    }
    public static bool operator !=(BigIntX left, BigIntX right)
    {
        return !(left == right);
    }
    public static bool operator >(BigIntX left, BigIntX right)
    {
        if (ReferenceEquals(left, null))
            throw new ArgumentNullException("left");
        if (ReferenceEquals(right, null))
            throw new ArgumentNullException("right");
        if (left.IsNegative != right.IsNegative)
            return right.IsNegative;
        if (left._digitsArray.DataUsed != right._digitsArray.DataUsed)
            return left._digitsArray.DataUsed > right._digitsArray.DataUsed;
        for (var idx = left._digitsArray.DataUsed - 1; idx >= 0; idx--)
            if (left._digitsArray[idx] != right._digitsArray[idx])
                return left._digitsArray[idx] > right._digitsArray[idx];
        return false;
    }
    public static bool operator <(BigIntX left, BigIntX right)
    {
        if (ReferenceEquals(left, null))
            throw new ArgumentNullException("left");
        if (ReferenceEquals(right, null))
            throw new ArgumentNullException("right");
        if (left.IsNegative != right.IsNegative)
            return left.IsNegative;
        if (left._digitsArray.DataUsed != right._digitsArray.DataUsed)
            return left._digitsArray.DataUsed < right._digitsArray.DataUsed;
        for (var idx = left._digitsArray.DataUsed - 1; idx >= 0; idx--)
            if (left._digitsArray[idx] != right._digitsArray[idx])
                return left._digitsArray[idx] < right._digitsArray[idx];
        return false;
    }
    public static bool operator >=(BigIntX left, BigIntX right)
    {
        return Compare(left, right) >= 0;
    }
    public static bool operator <=(BigIntX left, BigIntX right)
    {
        return Compare(left, right) <= 0;
    }
    public override bool Equals(object obj)
    {
        if (ReferenceEquals(obj, null))
            return false;
        if (ReferenceEquals(this, obj))
            return true;
        var c = (BigIntX)obj;
        if (_digitsArray.DataUsed != c._digitsArray.DataUsed)
            return false;
        for (var idx = 0; idx < _digitsArray.DataUsed; idx++)
            if (_digitsArray[idx] != c._digitsArray[idx])
                return false;
        return true;
    }
    public override int GetHashCode()
    {
        var hash = 0x811c9dc5;
        for (var i = 0; i < _digitsArray.Data.Length; i++)
        {
            hash =  ((hash << 13) | (hash >> 19)) ^ _digitsArray.Data[i];
            hash *= 0x1000193;
        }
        return (int)hash;
    }
    public string GetDataAsString()
    {
        return _digitsArray.GetDataAsString();
    }
    public override string ToString()
    {
        return ToString(10);
    }
    public byte[] ToByteArray()
    {
        return _digitsArray.ToByteArray();
    }
    public uint[] ToUIn32Array()
    {
        return _digitsArray.ToUIn32Array();
    }
    public ulong[] ToUIn64Array()
    {
        return _digitsArray.ToUIn64Array();
    }
    public string ToString(int radix)
    {
        if (radix < 2 || radix > 36)
            throw new ArgumentOutOfRangeException("radix");
        if (IsZero)
            return "0";
        var a        = this;
        var negative = a.IsNegative;
        a = Abs(this);
        BigIntX      quotient;
        BigIntX      remainder;
        var          biRadix = new BigIntX(radix);
        const string charSet = "0123456789abcdefghijklmnopqrstuvwxyz";
        var          al      = new ArrayList();
        while (a._digitsArray.DataUsed > 1 || a._digitsArray.DataUsed == 1 && a._digitsArray[0] != 0)
        {
            Divide(a, biRadix, out quotient, out remainder);
            al.Insert(0, charSet[(int)remainder._digitsArray[0]]);
            a = quotient;
        }
        var result = new string((char[])al.ToArray(typeof(char)));
        if (radix == 10 && negative)
            return "-" + result;
        return result;
    }
    public string ToHexString()
    {
        var sb = new StringBuilder();
        sb.AppendFormat("{0:X}", _digitsArray[_digitsArray.DataUsed - 1]);
        var f = "{0:X" + 2 * DigitsArray.DataSizeOf + "}";
        for (var i = _digitsArray.DataUsed - 2; i >= 0; i--)
            sb.AppendFormat(f, _digitsArray[i]);
        return sb.ToString();
    }
    public string ToBinaryString()
    {
        var bytes  = ToByteArray();
        var index  = bytes.Length - 1;
        var base2  = new StringBuilder(bytes.Length * 8);
        var binary = Convert.ToString(bytes[index], 2);
        if (binary[0] != '0' && Sign == 1) base2.Append('0');
        base2.Append(binary);
        for (index--; index >= 0; index--)
            base2.Append(Convert.ToString(bytes[index], 2).PadLeft(8, '0'));
        return base2.ToString();
    }
    public string ToOctalString()
    {
        var bytes         = ToByteArray();
        var index         = bytes.Length - 1;
        var base8         = new StringBuilder((bytes.Length / 3 + 1) * 8);
        var rem           = bytes.Length % 3;
        if (rem == 0) rem = 3;
        var base0         = 0;
        while (rem != 0)
        {
            base0 <<= 8;
            base0 +=  bytes[index--];
            rem--;
        }
        var octal = Convert.ToString(base0, 8);
        if (octal[0] != '0' && Sign == 1) base8.Append('0');
        base8.Append(octal);
        while (index >= 0)
        {
            base0 = (bytes[index] << 16) + (bytes[index - 1] << 8) + bytes[index - 2];
            base8.Append(Convert.ToString(base0, 8).PadLeft(8, '0'));
            index -= 3;
        }
        return base8.ToString();
    }
    public static int ToInt16(BigIntX value)
    {
        if (ReferenceEquals(value, null))
            throw new ArgumentNullException("value");
        return short.Parse(value.ToString(), NumberStyles.Integer, CultureInfo.CurrentCulture);
    }
    public static uint ToUInt16(BigIntX value)
    {
        if (ReferenceEquals(value, null))
            throw new ArgumentNullException("value");
        return ushort.Parse(value.ToString(), NumberStyles.Integer, CultureInfo.CurrentCulture);
    }
    public static int ToInt32(BigIntX value)
    {
        if (ReferenceEquals(value, null))
            throw new ArgumentNullException("value");
        return int.Parse(value.ToString(), NumberStyles.Integer, CultureInfo.CurrentCulture);
    }
    public static uint ToUInt32(BigIntX value)
    {
        if (ReferenceEquals(value, null))
            throw new ArgumentNullException("value");
        return uint.Parse(value.ToString(), NumberStyles.Integer, CultureInfo.CurrentCulture);
    }
    public static long ToInt64(BigIntX value)
    {
        if (ReferenceEquals(value, null))
            throw new ArgumentNullException("value");
        return long.Parse(value.ToString(), NumberStyles.Integer, CultureInfo.CurrentCulture);
    }
    public static ulong ToUInt64(BigIntX value)
    {
        if (ReferenceEquals(value, null))
            throw new ArgumentNullException("value");
        return ulong.Parse(value.ToString(), NumberStyles.Integer, CultureInfo.CurrentCulture);
    }
    public static BigIntX Pow(BigIntX value, BigIntX exponent)
    {
        if (value == null)
            throw new ArgumentNullException("Value cannot be null");
        if (exponent == null)
            throw new ArgumentNullException("Exponent cannot be null");
        if (exponent < 0)
            throw new ArgumentOutOfRangeException("Exponent", "Exponent cannot be negative");
        BigIntX result = 1;
        while (exponent != 0)
        {
            if ((exponent & 1) != 0)
                result *= value;
            exponent >>= 1;
            value    *=  value;
        }
        return result;
    }
    public static BigIntX ModPow(BigIntX n, BigIntX e, BigInteger m)
    {
        var n1 = n;
        var e1 = e;
        var c  = 0;
        if (e1 == 0)
            return 1;
        if (e1 == 1)
            return n1 % m;
        if (e1 == 2)
            return n1 * n1 % m;
        BigIntX r;
        n1 %= m;
        r  =  1;
        if ((e1 & 1) == 1)
            r = n1;
        while (e1 > 1)
        {
            c++;
            e1 >>= 1;
            n1 =   n1 * n1 % m;
            if ((e1 & 1) == 1)
                r = r * n1 % m;
        }
        return r;
    }
    public static BigIntX Sqrt(BigIntX n)
    {
        var q = (BigIntX)1 << ((int)Log(n, 2) >> 1);
        var m = (BigIntX)0;
        while (Abs(q - m) >= 1)
        {
            m = q;
            q = (m + n / m) >> 1;
        }
        return q;
    }
    public static double Log(BigIntX value, double baseValue)
    {
        Array.Resize(ref value._digitsArray.Data, value._digitsArray.DataUsed);
        var c          = 0.0;
        var d          = 0.5;
        var dataLength = Length(value._digitsArray.Data);
        var topBits    = BitLengthOfUInt(value._digitsArray.Data[dataLength - 1]);
        var bitLength  = (dataLength - 1) * 32 + topBits;
        var bit        = (uint)(1 << (topBits - 1));
        for (var index = dataLength - 1; index >= 0; --index)
        {
            for (; bit != 0U; bit >>= 1)
            {
                if (((int)value._digitsArray.Data[index] & (int)bit) != 0)
                    c += d;
                d *= 0.5;
            }
            bit = 2147483648U;
        }
        return (Math.Log(c) + 0.693147180559945 * bitLength) / Math.Log(baseValue);
    }
    private static int BitLengthOfUInt(uint x)
    {
        var numBits = 0;
        while (x > 0)
        {
            x >>= 1;
            numBits++;
        }
        return numBits;
    }
    private static int Length(uint[] rgu)
    {
        var length = rgu.Length;
        return rgu[length - 1] != 0U ? length : length - 1;
    }
    public static List<BigIntX> GetFactors(BigIntX n)
    {
        var Factors = new List<BigIntX>();
        var s       = Sqrt(n);
        var a       = (BigIntX)3;
        while (a < s)
        {
            if (n % a == 0)
            {
                Factors.Add(a);
                if (a * a != n)
                    Factors.Add(n / a);
            }
            a += 2;
        }
        return Factors;
    }
    public static BigIntX Gcd(BigIntX a, BigIntX b)
    {
        while (b > 0)
        {
            var r = a % b;
            a = b;
            b = r;
        }
        return a;
    }
    public static BigIntX Lcm(BigIntX a, BigIntX b)
    {
        return a * b / a.Gcd(b);
    }
    public static int GetBitWidth(BigIntX value)
    {
        var bw = 1;
        var v  = value;
        while ((v >>= 1) > 0)
            bw++;
        if (bw < 8)
            bw = 8;
        return bw;
    }
    public static BigIntX GetMaxValueBitWidth(int bitLength)
    {
        return ((BigIntX)1 << bitLength) - 1;
    }
    public static BigIntX GetMaxValue(BigIntX value)
    {
        var bitLength = GetBitWidth(value);
        return ((BigIntX)1 << bitLength) - 1;
    }
    public static BigIntX Min(BigIntX left, BigIntX right)
    {
        if (left.CompareTo(right) <= 0)
            return left;
        return right;
    }
    public static BigIntX Max(BigIntX left, BigIntX right)
    {
        if (left.CompareTo(right) < 0)
            return right;
        return left;
    }
    public static double Log10(BigIntX value)
    {
        return Log(value, 10.0);
    }
    public static double LogN(BigIntX value)
    {
        return Log(value, 2.0);
    }
    private class BigIntXConverter : TypeConverter
    {
        public override bool CanConvertFrom(ITypeDescriptorContext context, Type sourceType)
        {
            return sourceType == typeof(string) || base.CanConvertFrom(context, sourceType);
        }
        public override object ConvertFrom(ITypeDescriptorContext context, CultureInfo culture, object value)
        {
            if (value != null)
                if (TryParse($"{value}", out var i))
                    return i;
            return new BigIntX();
        }
        public override bool CanConvertTo(ITypeDescriptorContext context, Type destinationType)
        {
            return destinationType == typeof(string) || base.CanConvertTo(context, destinationType);
        }
        public override object ConvertTo(ITypeDescriptorContext context, CultureInfo culture, object value, Type destinationType)
        {
            return destinationType == typeof(string) ? $"{value}" : base.ConvertTo(context, culture, value, destinationType);
        }
    }
}

One thought on “BigIntX.cs”

Leave a Reply

Your email address will not be published. Required fields are marked *