FixedBigInteger.cs

Adjustable Fixed Bit Width Signed Integer 32,64,128,256,…

using System;
using System.Collections;
using System.Collections.Generic;
using System.ComponentModel;
using System.Diagnostics;
using System.Globalization;
using System.Numerics;
using System.Runtime.InteropServices;
using System.Runtime.Serialization;
using System.Text;
[Serializable]
[StructLayout(LayoutKind.Sequential, Pack = 1)]
[TypeConverter(typeof(FixedBigIntegerConverter))]
[DebuggerDisplay("{DDisplay}")]
public class FixedBigInteger : IComparable<FixedBigInteger>, IComparable, IEquatable<FixedBigInteger>, IConvertible, IFormattable, ISerializable
{
    private const          int               DataSize       = sizeof(uint);
    private const          int               DataShiftCount = 5;
    private const          uint              AllBits        = ~(uint) 0;
    private const          int               DataSizeBits   = sizeof(uint) * 8;
    private const          uint              HiNeg          = (uint) 1 << (DataSizeBits - 1);
    private static         int               DataBitWidth;
    private static         int               DataLength;
    public static readonly FixedBigInteger   One   = new FixedBigInteger(1,  DataBitWidth);
    public static readonly FixedBigInteger   Two   = new FixedBigInteger(2,  DataBitWidth);
    public static readonly FixedBigInteger   Zero  = new FixedBigInteger(0,  DataBitWidth);
    public static readonly FixedBigInteger   Ten   = new FixedBigInteger(10, DataBitWidth);
    public static readonly FixedBigInteger   Three = new FixedBigInteger(3,  DataBitWidth);
    private readonly       SerializationInfo SInfo;
    public                 uint[]            Data;
    public FixedBigInteger(FixedBigInteger value, int bitLength)
    {
        DataBitWidth = bitLength;
        DataLength   = DataBitWidth >> DataShiftCount;
        CalculateMinDataLength(value.Data.Length);
        Data = new uint[DataLength];
        value.Data.CopyTo(Data, 0);
    }
    public FixedBigInteger(string value, int bitLength)
    {
        DataBitWidth = bitLength;
        DataLength   = DataBitWidth >> DataShiftCount;
        if (!TryParse(value, out var result))
            throw new Exception("TryParse Failed.");
        CalculateMinDataLength(result.Data.Length);
        Data = new uint[DataLength];
        result.Data.CopyTo(Data, 0);
    }
    public FixedBigInteger(byte value, int bitLength)
    {
        if (bitLength < 32)
            bitLength = 32;
        DataBitWidth = bitLength;
        DataLength   = DataBitWidth >> DataShiftCount;
        Data         = new uint[DataLength];
        Data[0]      = value;
    }
    public FixedBigInteger(bool value, int bitLength)
    {
        if (bitLength < 32)
            bitLength = 32;
        DataBitWidth = bitLength;
        DataLength   = DataBitWidth >> DataShiftCount;
        Data         = new uint[DataLength];
        Data[0]      = (uint) (value ? 1 : 0);
    }
    public FixedBigInteger(char value, int bitLength)
    {
        if (bitLength < 32)
            bitLength = 32;
        DataBitWidth = bitLength;
        DataLength   = DataBitWidth >> DataShiftCount;
        Data         = new uint[DataLength];
        Data[0]      = value;
    }
    public FixedBigInteger(BigDecimal value, int bitLength)
    {
        var ba = value.WholePart.ToByteArray();
        DataBitWidth = bitLength;
        DataLength   = DataBitWidth >> DataShiftCount;
        var len = ba.Length / DataSize;
        CalculateMinDataLength(len);
        Data = new uint[DataLength];
        for (var i = 0; i < Data.Length; i++)
            Data[i] = BitConverter.ToUInt32(ba, i * DataSize);
    }
    public FixedBigInteger(decimal value, int bitLength)
    {
        DataBitWidth = bitLength;
        DataLength   = DataBitWidth >> DataShiftCount;
        CalculateMinDataLength(3);
        Data = new uint[DataLength];
        if (value < 0)
        {
            var n = -new FixedBigInteger(-value, DataBitWidth);
            n.Data.CopyTo(Data, 0);
            return;
        }
        var bits = decimal.GetBits(value);
        Data[2] = (uint) bits[2];
        Data[1] = (uint) bits[1];
        Data[0] = (uint) bits[0];
    }
    public FixedBigInteger(double value, int bitLength) : this((decimal) value, bitLength)
    {
    }
    public FixedBigInteger(float value, int bitLength) : this((decimal) value, bitLength)
    {
    }
    public FixedBigInteger(short value, int bitLength)
    {
        if (bitLength < 32)
            bitLength = 32;
        DataBitWidth = bitLength;
        DataLength   = DataBitWidth >> DataShiftCount;
        Data         = new uint[DataLength];
        if (value < 0)
        {
            var n = -new FixedBigInteger(-(value + 1), DataBitWidth) - 1;
            n.Data.CopyTo(Data, 0);
            return;
        }
        Data[0] = (uint) value;
    }
    public FixedBigInteger(int value, int bitLength)
    {
        if (bitLength < 32)
            bitLength = 32;
        DataBitWidth = bitLength;
        DataLength   = DataBitWidth >> DataShiftCount;
        Data         = new uint[DataLength];
        if (value < 0)
        {
            var n = -new FixedBigInteger(-(value + 1), DataBitWidth) - 1;
            n.Data.CopyTo(Data, 0);
            return;
        }
        Data[0] = (uint) value;
    }
    public FixedBigInteger(long value, int bitLength)
    {
        if (bitLength < 64)
            bitLength = 64;
        DataBitWidth = bitLength;
        DataLength   = DataBitWidth >> DataShiftCount;
        Data         = new uint[DataLength];
        if (value < 0)
        {
            var n = -new FixedBigInteger(-(value + 1), DataBitWidth) - 1;
            n.Data.CopyTo(Data, 0);
            return;
        }
        Data[1] = (uint) ((value >> 32) & 0xffffffff);
        Data[0] = (uint) (value         & 0xffffffff);
    }
    public FixedBigInteger(sbyte value, int bitLength)
    {
        if (bitLength < 32)
            bitLength = 32;
        DataBitWidth = bitLength;
        DataLength   = DataBitWidth >> DataShiftCount;
        Data         = new uint[DataLength];
        if (value < 0)
        {
            var n = -new FixedBigInteger(-(value + 1), DataBitWidth) - 1;
            n.Data.CopyTo(Data, 0);
            return;
        }
        Data[0] = (uint) value;
    }
    public FixedBigInteger(ushort value, int bitLength)
    {
        if (bitLength < 32)
            bitLength = 32;
        DataBitWidth = bitLength;
        DataLength   = DataBitWidth >> DataShiftCount;
        Data         = new uint[DataLength];
        Data[0]      = value;
    }
    public FixedBigInteger(uint value, int bitLength)
    {
        if (bitLength < 32)
            bitLength = 32;
        DataBitWidth = bitLength;
        DataLength   = DataBitWidth >> DataShiftCount;
        Data         = new uint[DataLength];
        Data[0]      = value;
    }
    public FixedBigInteger(ulong value, int bitLength)
    {
        if (bitLength < 96)
            bitLength = 96;
        DataBitWidth = bitLength;
        DataLength   = DataBitWidth >> DataShiftCount;
        Data         = new uint[DataLength];
        Data[1]      = (uint) ((value >> 32) & 0xffffffff);
        Data[0]      = (uint) (value         & 0xffffffff);
    }
    public FixedBigInteger(BigInteger value, int bitLength) : this(value.ToByteArray(), bitLength)
    {
    }
    public FixedBigInteger(Guid value, int bitLength) : this(value.ToByteArray(), bitLength)
    {
    }
    public FixedBigInteger(byte[] value, int bitLength)
    {
        var minSize = value.Length / DataSize;
        if (value == null)
            throw new ArgumentNullException("value");
        DataBitWidth = bitLength;
        DataLength   = DataBitWidth >> DataShiftCount;
        CalculateMinDataLength(minSize);
        var byteCount      = value.Length;
        var isNegative     = byteCount > 0 && (value[byteCount - 1] & 0x80) == 0x80;
        var unalignedBytes = byteCount % DataSize;
        var dwordCount     = byteCount / DataSize + (unalignedBytes == 0 ? 0 : 1);
        Data = new uint[Math.Max(dwordCount, DataLength)];
        if (byteCount == 0)
            return;
        int curDword, curByte, byteInDword;
        curByte = 3;
        for (curDword = 0; curDword < dwordCount - (unalignedBytes == 0 ? 0 : 1); curDword++)
        {
            byteInDword = 0;
            while (byteInDword < DataSize)
            {
                Data[curDword] <<= 8;
                Data[curDword] |=  value[curByte];
                curByte--;
                byteInDword++;
            }
            curByte += 8;
        }
        if (unalignedBytes != 0)
        {
            if (isNegative)
                Data[dwordCount - 1] = 0xffffffff;
            for (curByte = byteCount - 1; curByte >= byteCount - unalignedBytes; curByte--)
            {
                Data[curDword] <<= 8;
                Data[curDword] |=  value[curByte];
            }
        }
    }
    public FixedBigInteger(int sign, uint[] array, int bitLength)
    {
        if (array == null)
            throw new Exception("Array cannot be null.");
        DataBitWidth = bitLength;
        DataLength   = DataBitWidth >> DataShiftCount;
        CalculateMinDataLength(array.Length);
        if (array.Length != DataLength)
            Array.Resize(ref array, DataLength);
        Data = new uint[DataLength];
        var ba = new byte[DataSize];
        for (var i = 0; i < Data.Length; i++)
        {
            Array.Copy(BitConverter.GetBytes(array[i]), 0, ba, 0, DataSize);
            Data[i] = BitConverter.ToUInt32(ba, 0);
        }
        if (sign < 0)
            Data[DataLength - 1] |= HiNeg;
        else
            Data[DataLength - 1] &= ~HiNeg;
    }
    public FixedBigInteger(uint[] array, int bitLength)
    {
        if (array == null)
            throw new Exception("Array cannot be null.");
        DataBitWidth = bitLength;
        DataLength   = DataBitWidth >> DataShiftCount;
        if (array.Length != DataLength)
            Array.Resize(ref array, DataLength);
        Data = new uint[DataLength];
        var ba = new byte[DataSize];
        for (var i = 0; i < Data.Length; i++)
        {
            Array.Copy(BitConverter.GetBytes(array[i]), 0, ba, 0, DataSize);
            Data[i] = BitConverter.ToUInt32(ba, 0);
        }
    }
    protected FixedBigInteger(SerializationInfo info, StreamingContext context)
    {
        SInfo = info;
    }
    [DebuggerBrowsable(DebuggerBrowsableState.Never)]
    private string DDisplay => ToString();
    public FixedBigInteger MaxValue
    {
        get
        {
            var r = new FixedBigInteger(0, DataBitWidth);
            for (var i = 0; i < r.Data.Length; ++i)
                r.Data[i] = uint.MaxValue;
            r.Data[r.Data.Length - 1] = int.MaxValue;
            return r;
        }
    }
    public int BitWidth
    {
        get
        {
            FixedBigInteger bw = 1;
            var             v  = new FixedBigInteger(this, 0);
            while ((v >>= 1) > 0)
                bw++;
            if (bw < 8)
                bw = 8;
            while (bw % 8 != 0)
                bw++;
            return (int) bw;
        }
    }
    public int Sign
    {
        get
        {
            var allZero = true;
            var ba      = Data;
            for (var i = 0; i < ba.Length; i++)
                if (ba[i] != 0)
                {
                    allZero = false;
                    break;
                }
            if (allZero)
                return 0;
            return (Data[Data.Length - 1] & HiNeg) == 0 ? 1 : -1;
        }
    }
    public bool IsOne      => this       == 1;
    public bool IsEven     => (this & 1) == 0;
    public bool IsNegative => Sign       < 0;
    public bool IsZero
    {
        get
        {
            for (var i = 0; i < Data.Length; i++)
                if (Data[i] != 0)
                    return false;
            return true;
        }
    }
    public int DataUsed
    {
        get
        {
            var DataUsed = Data.Length;
            if (!IsNegative)
            {
                while (DataUsed > 1 && Data[DataUsed - 1] == 0)
                    --DataUsed;
                if (DataUsed == 0)
                    DataUsed = 1;
            }
            return DataUsed;
        }
    }
    int IComparable.CompareTo(object obj)
    {
        return Compare(this, obj);
    }
    public int CompareTo(FixedBigInteger value)
    {
        return Compare(this, value);
    }
    TypeCode IConvertible.GetTypeCode()
    {
        return TypeCode.Object;
    }
    bool IConvertible.ToBoolean(IFormatProvider provider)
    {
        return (bool) this;
    }
    byte IConvertible.ToByte(IFormatProvider provider)
    {
        return (byte) this;
    }
    char IConvertible.ToChar(IFormatProvider provider)
    {
        return (char) this;
    }
    DateTime IConvertible.ToDateTime(IFormatProvider provider)
    {
        throw new InvalidCastException();
    }
    decimal IConvertible.ToDecimal(IFormatProvider provider)
    {
        return (decimal) this;
    }
    double IConvertible.ToDouble(IFormatProvider provider)
    {
        return (double) this;
    }
    short IConvertible.ToInt16(IFormatProvider provider)
    {
        return (short) this;
    }
    int IConvertible.ToInt32(IFormatProvider provider)
    {
        return (int) this;
    }
    long IConvertible.ToInt64(IFormatProvider provider)
    {
        return (long) this;
    }
    sbyte IConvertible.ToSByte(IFormatProvider provider)
    {
        return (sbyte) this;
    }
    float IConvertible.ToSingle(IFormatProvider provider)
    {
        return (float) this;
    }
    string IConvertible.ToString(IFormatProvider provider)
    {
        return ToString(null, provider);
    }
    public object ToType(Type conversionType, IFormatProvider provider)
    {
        object value;
        if (TryConvert(conversionType, provider, out value))
            return value;
        throw new InvalidCastException();
    }
    ushort IConvertible.ToUInt16(IFormatProvider provider)
    {
        if (Data[1] != 0)
            throw new OverflowException();
        return Convert.ToUInt16(Data[0]);
    }
    uint IConvertible.ToUInt32(IFormatProvider provider)
    {
        if (Data[1] != 0)
            throw new OverflowException();
        return Convert.ToUInt32(Data[0]);
    }
    ulong IConvertible.ToUInt64(IFormatProvider provider)
    {
        if (Data[1] != 0)
            return ((ulong) Data[1] << 32) | Data[0];
        return Data[0];
    }
    public bool Equals(FixedBigInteger obj)
    {
        if (ReferenceEquals(obj, null))
            return false;
        if (ReferenceEquals(this, obj))
            return true;
        if (Data.Length != obj.Data.Length)
        {
            var len = Math.Max(Data.Length, obj.Data.Length);
            if (Data.Length < len)
            {
                var tData = new uint[len];
                Array.Copy(Data, 0, tData, 0, Data.Length);
                Data = tData;
            }
            if (obj.Data.Length < len)
                Resize(ref obj, len);
        }
        if (Sign != obj.Sign)
            return false;
        for (var i = 0; i < Data.Length; i++)
            if (Data[i] != obj.Data[i])
                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')
            {
                int.TryParse(format.Substring(1).Trim(), out var min);
                return ToHexString(ch == 'X');
            }
            if (ch != 'G' && ch != 'g' && ch != 'D' && ch != 'd')
                throw new NotSupportedException("Not supported format: " + format);
        }
        return ToString((NumberFormatInfo) formatProvider.GetFormat(typeof(NumberFormatInfo)), 10);
    }
    public void GetObjectData(SerializationInfo info, StreamingContext context)
    {
        info.AddValue("Bits", DataBitWidth);
        info.AddValue("Data", Data, typeof(uint[]));
    }
    private static void CalculateMinDataLength(int minSize)
    {
        if (minSize > DataLength)
        {
            DataBitWidth = 32 * minSize;
            DataLength   = minSize;
        }
    }
    public void OnDeserialization(object sender)
    {
        if (SInfo == null)
            return;
        DataBitWidth = SInfo.GetInt32("Bits");
        if (DataBitWidth != 0)
        {
            DataLength = DataBitWidth >> DataShiftCount;
            var array = (uint[]) SInfo.GetValue("Data", typeof(uint[]));
            if (array == null)
                throw new Exception("Array cannot be null.");
            if (array.Length != DataLength)
                Array.Resize(ref array, DataLength);
            Data = new uint[DataLength];
            var ba = new byte[4];
            for (var i = 0; i < DataLength; i++)
            {
                Array.Copy(BitConverter.GetBytes(array[i]), 0, ba, 0, DataSize);
                Data[i] = BitConverter.ToUInt32(ba, 0);
            }
        }
    }
    public static int GetSign(uint[] value)
    {
        var allZero = true;
        for (var i = 0; i < value.Length; i++)
            if (value[i] != 0)
            {
                allZero = false;
                break;
            }
        if (allZero)
            return 0;
        return (value[value.Length - 1] & HiNeg) == 0 ? 1 : -1;
    }
    private static int GetDataUsed(uint[] array)
    {
        var neg      = GetSign(array) < 0;
        var DataUsed = array.Length;
        if (!neg)
        {
            while (DataUsed > 1 && array[DataUsed - 1] == 0)
                --DataUsed;
            if (DataUsed == 0)
                DataUsed = 1;
        }
        return DataUsed;
    }
    public int GetDecimalPlaces()
    {
        var dPlaces = 0;
        if (Sign == 0)
            return 1;
        var a = new FixedBigInteger(this, 0);
        if (Sign < 0)
            try
            {
                a = -a;
            }
            catch (Exception ex)
            {
                return 0;
            }
        var biRadix = new FixedBigInteger(10, DataBitWidth);
        while (a > 0)
            try
            {
                Divide(a, biRadix, out var remainder, out var quotient);
                a = quotient;
                dPlaces++;
            }
            catch (Exception ex)
            {
                break;
            }
        return dPlaces;
    }
    private uint[] TwosComplement(uint[] d)
    {
        var  i = 0;
        uint v = 0;
        for (; i < d.Length; i++)
        {
            v    = ~d[i] + 1;
            d[i] = v;
            if (v != 0)
            {
                i++;
                break;
            }
        }
        if (v != 0)
        {
            for (; i < d.Length; i++)
                d[i] = ~d[i];
        }
        else
        {
            Array.Resize(ref d, d.Length + 1);
            d[d.Length - 1] = 1;
        }
        return d;
    }
    public void ConstructFromArray(byte[] array)
    {
        if (array == null)
            throw new ArgumentNullException("value");
        var byteCount      = array.Length;
        var isNegative     = byteCount > 0 && (array[byteCount - 1] & 0x80) == 0x80;
        var unalignedBytes = byteCount % DataSize;
        var dwordCount     = byteCount / DataSize + (unalignedBytes == 0 ? 0 : 1);
        Data = new uint[Math.Max(dwordCount, DataLength)];
        if (byteCount == 0)
            return;
        int curDword, curByte, byteInDword;
        curByte = 3;
        for (curDword = 0; curDword < dwordCount - (unalignedBytes == 0 ? 0 : 1); curDword++)
        {
            byteInDword = 0;
            while (byteInDword < DataSize)
            {
                Data[curDword] <<= 8;
                Data[curDword] |=  array[curByte];
                curByte--;
                byteInDword++;
            }
            curByte += 8;
        }
        if (unalignedBytes != 0)
        {
            if (isNegative)
                Data[dwordCount - 1] = 0xffffffff;
            for (curByte = byteCount - 1; curByte >= byteCount - unalignedBytes; curByte--)
            {
                Data[curDword] <<= 8;
                Data[curDword] |=  array[curByte];
            }
        }
    }
    private static byte[] ToByteArray(ulong[] value)
    {
        var ba = new byte[value.Length << 3];
        Buffer.BlockCopy(value, 0, ba, 0, value.Length << 3);
        return ba;
    }
    private static byte[] ToByteArray(uint[] value)
    {
        var ba = new byte[value.Length << 2];
        Buffer.BlockCopy(value, 0, ba, 0, value.Length << 2);
        return ba;
    }
    public override int GetHashCode()
    {
        var hash = 0x811c9dc5;
        for (var i = 0; i < Data.Length; i++)
        {
            hash ^= ((hash << 13) | (hash >> 19)) ^ Data[i];
            hash *= 0x1000193;
        }
        return (int) hash;
    }
    public override bool Equals(object obj)
    {
        return base.Equals(obj);
    }
    public override string ToString()
    {
        return ToString(null, null);
    }
    public string ToString(string format)
    {
        return ToString(format, null);
    }
    public string ToHexString(bool caps)
    {
        var bytes = ToByteArray().Invert();
        var sb    = new StringBuilder();
        var x     = caps ? "X" : "x";
        foreach (var b in bytes)
        {
            var hex = b.ToString($"{x}2");
            sb.Append(hex);
        }
        return sb.ToString();
    }
    private string ToString(NumberFormatInfo info, int radix)
    {
        if (radix < 2 || radix > 36)
            throw new ArgumentOutOfRangeException("radix");
        if (Sign == 0)
            return "0";
        var negative = Sign < 0;
        var a        = new FixedBigInteger(this, 0);
        if (negative)
            try
            {
                a = -a;
            }
            catch (Exception ex)
            {
            }
        var          biRadix = new FixedBigInteger(radix, DataBitWidth);
        const string charSet = "0123456789abcdefghijklmnopqrstuvwxyz";
        var          al      = new ArrayList();
        while (a > 0)
            try
            {
                Divide(a, biRadix, out var remainder, out var quotient);
                al.Insert(0, charSet[(int) remainder.Data[0]]);
                a = quotient;
            }
            catch (Exception ex)
            {
                break;
            }
        var result = new string((char[]) al.ToArray(typeof(char)));
        if (radix == 10 && negative)
            return "-" + result;
        return result;
    }
    public static FixedBigInteger Abs(FixedBigInteger value)
    {
        if (ReferenceEquals(value, null))
            throw new ArgumentNullException("value");
        if (value.Sign < 0)
            return -value;
        return value;
    }
    public bool TryConvert(Type conversionType, IFormatProvider provider, out object value)
    {
        if (conversionType == typeof(bool))
        {
            value = (bool) this;
            return true;
        }
        if (conversionType == typeof(byte))
        {
            value = (byte) this;
            return true;
        }
        if (conversionType == typeof(char))
        {
            value = (char) this;
            return true;
        }
        if (conversionType == typeof(decimal))
        {
            value = (decimal) this;
            return true;
        }
        if (conversionType == typeof(double))
        {
            value = (double) this;
            return true;
        }
        if (conversionType == typeof(short))
        {
            value = (short) this;
            return true;
        }
        if (conversionType == typeof(int))
        {
            value = (int) this;
            return true;
        }
        if (conversionType == typeof(long))
        {
            value = (long) this;
            return true;
        }
        if (conversionType == typeof(sbyte))
        {
            value = (sbyte) this;
            return true;
        }
        if (conversionType == typeof(float))
        {
            value = (float) this;
            return true;
        }
        if (conversionType == typeof(string))
        {
            value = ToString(null, provider);
            return true;
        }
        if (conversionType == typeof(ushort))
        {
            value = (ushort) this;
            return true;
        }
        if (conversionType == typeof(uint))
        {
            value = (uint) this;
            return true;
        }
        if (conversionType == typeof(ulong))
        {
            value = (ulong) this;
            return true;
        }
        if (conversionType == typeof(byte[]))
        {
            value = ToByteArray();
            return true;
        }
        if (conversionType == typeof(Guid))
        {
            value = new Guid(ToByteArray());
            return true;
        }
        value = null;
        return false;
    }
    public static FixedBigInteger Parse(string value)
    {
        return Parse(value, NumberStyles.Integer, NumberFormatInfo.CurrentInfo);
    }
    public static FixedBigInteger Parse(string value, NumberStyles style)
    {
        return Parse(value, style, NumberFormatInfo.CurrentInfo);
    }
    public static FixedBigInteger Parse(string value, IFormatProvider provider)
    {
        return Parse(value, NumberStyles.Integer, NumberFormatInfo.GetInstance(provider));
    }
    public static FixedBigInteger 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 FixedBigInteger result)
    {
        return TryParse(value, NumberStyles.Integer, NumberFormatInfo.CurrentInfo, out result);
    }
    public static bool TryParse(string value, NumberStyles style, IFormatProvider provider, out FixedBigInteger result)
    {
        result = 0;
        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 bool TryParseNum(string digits, int radix, out FixedBigInteger result)
    {
        result = new FixedBigInteger(0, DataBitWidth);
        if (digits == null)
            return false;
        var multiplier = new FixedBigInteger(1, DataBitWidth);
        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 int Compare(FixedBigInteger left, object right)
    {
        if (right is FixedBigInteger)
            return Compare(left, (FixedBigInteger) right);
        if (right is bool)
            return Compare(left, new FixedBigInteger((bool) right, DataBitWidth));
        if (right is byte)
            return Compare(left, new FixedBigInteger((byte) right, DataBitWidth));
        if (right is char)
            return Compare(left, new FixedBigInteger((char) right, DataBitWidth));
        if (right is decimal)
            return Compare(left, new FixedBigInteger((decimal) right, DataBitWidth));
        if (right is double)
            return Compare(left, new FixedBigInteger((double) right, DataBitWidth));
        if (right is short)
            return Compare(left, new FixedBigInteger((short) right, DataBitWidth));
        if (right is int)
            return Compare(left, new FixedBigInteger((int) right, DataBitWidth));
        if (right is long)
            return Compare(left, new FixedBigInteger((long) right, DataBitWidth));
        if (right is sbyte)
            return Compare(left, new FixedBigInteger((sbyte) right, DataBitWidth));
        if (right is float)
            return Compare(left, new FixedBigInteger((float) right, DataBitWidth));
        if (right is ushort)
            return Compare(left, new FixedBigInteger((ushort) right, DataBitWidth));
        if (right is uint)
            return Compare(left, new FixedBigInteger((uint) right, DataBitWidth));
        if (right is ulong)
            return Compare(left, new FixedBigInteger((ulong) right, DataBitWidth));
        var bytes = right as byte[];
        if (bytes != null)
            return Compare(left, new FixedBigInteger(bytes, DataBitWidth));
        if (right is Guid)
            return Compare(left, new FixedBigInteger((Guid) right, DataBitWidth));
        throw new ArgumentException();
    }
    public static int Compare(FixedBigInteger left, FixedBigInteger right)
    {
        MakeLikeLengths(ref left, ref right);
        if (ReferenceEquals(left, right))
            return 0;
        if (left.Sign >= 0 && right.Sign < 0)
            return 1;
        if (left.Sign < 0 && right.Sign >= 0)
            return -1;
        for (var i = left.Data.Length - 1; i > 0; i--)
            if (left.Data[i] != right.Data[i])
                return left.Data[i].CompareTo(right.Data[i]);
        return left.Data[0].CompareTo(right.Data[0]);
    }
    public static implicit operator FixedBigInteger(bool value)
    {
        return new FixedBigInteger(value, DataBitWidth);
    }
    public static implicit operator FixedBigInteger(byte value)
    {
        return new FixedBigInteger(value, DataBitWidth);
    }
    public static implicit operator FixedBigInteger(char value)
    {
        return new FixedBigInteger(value, DataBitWidth);
    }
    public static explicit operator FixedBigInteger(decimal value)
    {
        return new FixedBigInteger(value, DataBitWidth);
    }
    public static explicit operator FixedBigInteger(double value)
    {
        return new FixedBigInteger(value, DataBitWidth);
    }
    public static implicit operator FixedBigInteger(short value)
    {
        return new FixedBigInteger(value, DataBitWidth);
    }
    public static implicit operator FixedBigInteger(int value)
    {
        return new FixedBigInteger(value, DataBitWidth);
    }
    public static implicit operator FixedBigInteger(long value)
    {
        return new FixedBigInteger(value, DataBitWidth);
    }
    public static implicit operator FixedBigInteger(sbyte value)
    {
        return new FixedBigInteger(value, DataBitWidth);
    }
    public static explicit operator FixedBigInteger(float value)
    {
        return new FixedBigInteger(value, DataBitWidth);
    }
    public static implicit operator FixedBigInteger(ushort value)
    {
        return new FixedBigInteger(value, DataBitWidth);
    }
    public static implicit operator FixedBigInteger(uint value)
    {
        return new FixedBigInteger(value, DataBitWidth);
    }
    public static implicit operator FixedBigInteger(ulong value)
    {
        return new FixedBigInteger(value, DataBitWidth);
    }
    public static implicit operator FixedBigInteger(BigInteger value)
    {
        return new FixedBigInteger(value, DataBitWidth);
    }
    public static implicit operator FixedBigInteger(BigDecimal value)
    {
        return new FixedBigInteger(value, DataBitWidth);
    }
    public static explicit operator bool(FixedBigInteger value)
    {
        return (byte) value.Data[0] != 0;
    }
    public static explicit operator byte(FixedBigInteger value)
    {
        return (byte) value.Data[0];
    }
    public static explicit operator char(FixedBigInteger value)
    {
        return (char) (ushort) value.Data[0];
    }
    public static explicit operator decimal(FixedBigInteger value)
    {
        if (value.Sign == 0)
            return 0;
        if (value.Data.Length == 1)
            return new decimal((int) value.Data[0], 0, 0, value.Sign < 0, 0);
        if (value.Data.Length == 2)
            return new decimal((int) value.Data[0], (int) value.Data[1], 0, value.Sign < 0, 0);
        if (value.Data.Length == 3)
            return new decimal((int) value.Data[0], (int) value.Data[1], (int) value.Data[2], value.Sign < 0, 0);
        throw new ArgumentException("Value length exceeds decimal length.");
    }
    public static explicit operator double(FixedBigInteger value)
    {
        if (value.Sign == 0)
            return 0;
        var nfi = CultureInfo.InvariantCulture.NumberFormat;
        if (!double.TryParse(value.ToString(nfi, 10), NumberStyles.Number, nfi, out var d))
            throw new OverflowException();
        return d;
    }
    public static explicit operator float(FixedBigInteger value)
    {
        if (value.Sign == 0)
            return 0;
        var nfi = CultureInfo.InvariantCulture.NumberFormat;
        if (!float.TryParse(value.ToString(nfi, 10), NumberStyles.Number, nfi, out var f))
            throw new OverflowException();
        return f;
    }
    public static explicit operator short(FixedBigInteger value)
    {
        if (value.Data[0] > 0x8000)
            throw new OverflowException();
        if (value.Data[0] == 0x8000 && value.Sign > 0)
            throw new OverflowException();
        return (short) ((int) value.Data[0] * value.Sign);
    }
    public static explicit operator int(FixedBigInteger value)
    {
        if (value.Sign == 0)
            return 0;
        return (int) value.Data[0] * value.Sign;
    }
    public static explicit operator long(FixedBigInteger value)
    {
        if (value.Sign == 0)
            return 0;
        if (value.Data[0] > int.MaxValue)
            throw new OverflowException();
        if (value.Data.Length > 1)
            if (value.Data[1] != 0)
                return (long) (((ulong) value.Data[1] << 32) | value.Data[0]) * value.Sign;
        return value.Data[0] * value.Sign;
    }
    public static explicit operator uint(FixedBigInteger value)
    {
        if (value.Sign == 0)
            return 0;
        return value.Data[0];
    }
    public static explicit operator ushort(FixedBigInteger value)
    {
        if (value.Sign == 0)
            return 0;
        return (ushort) value.Data[0];
    }
    public static explicit operator ulong(FixedBigInteger value)
    {
        if (value.Data.Length > 1)
            if (value.Data[1] != 0)
                return ((ulong) value.Data[1] << 32) | value.Data[0];
        return value.Data[0];
    }
    public static explicit operator BigInteger(FixedBigInteger value)
    {
        return new BigInteger(value.ToByteArray());
    }
    public static bool operator >(FixedBigInteger left, FixedBigInteger right)
    {
        return left.CompareTo(right) > 0;
    }
    private static void MakeLikeLengths(ref FixedBigInteger left, ref FixedBigInteger right)
    {
        if (left.Data.Length != right.Data.Length)
        {
            var len = Math.Max(left.Data.Length, right.Data.Length);
            Resize(ref left,  len);
            Resize(ref right, len);
        }
    }
    private static void Resize(ref FixedBigInteger value, int newSize)
    {
        var IsNeg = value.IsNegative;
        var nData = new uint[newSize];
        var len   = value.Data.Length;
        for (var i = 0; i < len; i++)
        {
            nData[i] = value.Data[i];
            if (IsNeg && i == len - 1)
                nData[i] &= ~HiNeg;
        }
        if (IsNeg)
            nData[nData.Length - 1] |= HiNeg;
        value.Data = (uint[]) nData.Clone();
    }
    public static bool operator <(FixedBigInteger left, FixedBigInteger right)
    {
        return Compare(left, right) < 0;
    }
    public static bool operator >=(FixedBigInteger left, FixedBigInteger right)
    {
        return Compare(left, right) >= 0;
    }
    public static bool operator <=(FixedBigInteger left, FixedBigInteger right)
    {
        return Compare(left, right) <= 0;
    }
    public static bool operator !=(FixedBigInteger left, FixedBigInteger right)
    {
        return !left.Equals(right);
    }
    public static bool operator ==(FixedBigInteger left, FixedBigInteger right)
    {
        return left.Equals(right);
    }
    public static FixedBigInteger operator +(FixedBigInteger value)
    {
        return value;
    }
    public static FixedBigInteger operator ~(FixedBigInteger value)
    {
        var da = new uint[DataLength];
        for (var idx = 0; idx < DataLength; idx++)
            da[idx] = ~value.Data[idx];
        return new FixedBigInteger(da, DataBitWidth);
    }
    public static FixedBigInteger operator -(FixedBigInteger value)
    {
        if (ReferenceEquals(value, null))
            throw new ArgumentNullException("value");
        if (value.IsZero)
            return Zero;
        var da = new uint[DataLength];
        for (var i = 0; i < da.Length; i++)
            da[i] = ~value.Data[i];
        var carry = true;
        var index = 0;
        while (carry && index < da.Length)
        {
            var val = (long) da[index] + 1;
            da[index] = (uint) (val & AllBits);
            carry     = val >> DataSizeBits > 0;
            index++;
        }
        return new FixedBigInteger(da, DataBitWidth);
    }
    public static FixedBigInteger operator ++(FixedBigInteger value)
    {
        return value + 1;
    }
    public static FixedBigInteger operator --(FixedBigInteger value)
    {
        return value - 1;
    }
    public static FixedBigInteger Negate(FixedBigInteger value)
    {
        var ldata = (uint[]) value.Data.Clone();
        for (var i = 0; i < value.Data.Length; i++)
            ldata[i] = ~value.Data[i];
        return new FixedBigInteger(value.Sign, ldata, DataBitWidth);
    }
    public static FixedBigInteger operator +(FixedBigInteger left, FixedBigInteger right)
    {
        if (right.IsZero)
            return left;
        if (left.IsZero)
            return right;
        MakeLikeLengths(ref left, ref right);
        var  dl     = left.Data.Length > right.Data.Length ? left.Data.Length : right.Data.Length;
        var  result = new uint[dl];
        long carry  = 0;
        for (var i = 0; i < dl; i++)
        {
            var sum = left.Data[i] + (long) right.Data[i] + carry;
            carry     = sum >> 32;
            result[i] = (uint) (sum & 0xFFFFFFFF);
        }
        if (carry != 0)
        {
            var idx = 0;
            while (idx < result.Length - 1)
            {
                if (result[idx] == 0)
                    break;
                idx++;
            }
            result[idx] = (uint) carry;
        }
        return new FixedBigInteger(left.Sign * right.Sign, result, DataBitWidth);
    }
    public static FixedBigInteger operator -(FixedBigInteger left, FixedBigInteger right)
    {
        if (right.IsZero)
            return left;
        if (left.IsZero)
            return -right;
        MakeLikeLengths(ref left, ref right);
        var  da    = new uint[DataLength];
        long carry = 0;
        for (var i = 0; i < DataLength && i < left.Data.Length && i < right.Data.Length; i++)
        {
            var diff = left.Data[i] - (long) right.Data[i] - carry;
            da[i] = (uint) (diff & AllBits);
            carry = diff < 0 ? 1 : 0;
        }
        return new FixedBigInteger(da, DataBitWidth);
    }
    public static FixedBigInteger Add(FixedBigInteger left, FixedBigInteger right)
    {
        return left + right;
    }
    public static FixedBigInteger Subtract(FixedBigInteger left, FixedBigInteger right)
    {
        return left - right;
    }
    public static FixedBigInteger Divide(FixedBigInteger dividend, FixedBigInteger divisor)
    {
        if (divisor == 0)
            throw new DivideByZeroException();
        return DivRem(dividend, divisor, out var integer);
    }
    public static void Divide(FixedBigInteger dividend, FixedBigInteger divisor, out FixedBigInteger remainder, out FixedBigInteger quotient)
    {
        if (divisor == 0)
            throw new DivideByZeroException();
        DivRem(dividend.Data, divisor.Data, out var quo, out var rem);
        remainder = new FixedBigInteger(1,                            rem, DataBitWidth);
        quotient  = new FixedBigInteger(dividend.Sign * divisor.Sign, quo, DataBitWidth);
    }
    public static FixedBigInteger DivRem(FixedBigInteger dividend, FixedBigInteger divisor, out FixedBigInteger remainder)
    {
        if (divisor == 0)
            throw new DivideByZeroException();
        DivRem(dividend.Data, divisor.Data, out var quotient, out var rem);
        remainder = new FixedBigInteger(1, rem, DataBitWidth);
        return new FixedBigInteger(dividend.Sign * divisor.Sign, quotient, DataBitWidth);
    }
    private static void DivRem(uint[] dividend, uint[] divisor, out uint[] quotient, out uint[] remainder)
    {
        const ulong hiBit       = 0x100000000;
        var         divisorLen  = GetLength(divisor);
        var         dividendLen = GetLength(dividend);
        if (divisorLen <= 1)
        {
            ulong rem = 0;
            var   div = divisor[0];
            quotient  = new uint[dividendLen];
            remainder = new uint[1];
            for (var i = dividendLen - 1; i >= 0; i--)
            {
                rem *= hiBit;
                rem += dividend[i];
                var q = rem / div;
                rem         -= q * div;
                quotient[i] =  (uint) q;
            }
            remainder[0] = (uint) rem;
            return;
        }
        if (dividendLen >= divisorLen)
        {
            var shift        = GetNormalizeShift(divisor[divisorLen - 1]);
            var normDividend = new uint[dividendLen + 1];
            var normDivisor  = new uint[divisorLen];
            Normalize(dividend, dividendLen, normDividend, shift);
            Normalize(divisor,  divisorLen,  normDivisor,  shift);
            quotient = new uint[dividendLen - divisorLen + 1];
            for (var j = dividendLen - divisorLen; j >= 0; j--)
            {
                var dx = hiBit * normDividend[j + divisorLen] + normDividend[j + divisorLen - 1];
                var qj = dx / normDivisor[divisorLen                                        - 1];
                dx -= qj * normDivisor[divisorLen - 1];
                do
                {
                    if (qj < hiBit && qj * normDivisor[divisorLen - 2] <= dx * hiBit + normDividend[j + divisorLen - 2])
                        break;
                    qj -= 1L;
                    dx += normDivisor[divisorLen - 1];
                } while (dx < hiBit);
                ulong di = 0;
                ulong dj;
                var   index = 0;
                while (index < divisorLen)
                {
                    var dqj = normDivisor[index] * qj;
                    dj                      = normDividend[index + j] - (uint) dqj - di;
                    normDividend[index + j] = (uint) dj;
                    dqj                     = dqj >> 32;
                    dj                      = dj  >> 32;
                    di                      = dqj - dj;
                    index++;
                }
                dj                           = normDividend[j + divisorLen] - di;
                normDividend[j + divisorLen] = (uint) dj;
                quotient[j]                  = (uint) qj;
                if ((long) dj < 0)
                {
                    quotient[j]--;
                    ulong sum = 0;
                    for (index = 0; index < divisorLen; index++)
                    {
                        sum                     = normDivisor[index] + normDividend[j + index] + sum;
                        normDividend[j + index] = (uint) sum;
                        sum                     = sum >> 32;
                    }
                    sum += normDividend[j + divisorLen];
                    normDividend[j        + divisorLen] = (uint) sum;
                }
            }
            remainder = Unnormalize(normDividend, shift);
            return;
        }
        quotient  = new uint[1];
        remainder = dividend;
    }
    private static int GetLength(uint[] uints)
    {
        var index = uints.Length - 1;
        while (index >= 0 && uints[index] == 0)
            index--;
        return index + 1;
    }
    private static int GetNormalizeShift(uint ui)
    {
        var shift = 0;
        if ((ui & 0xffff0000) == 0)
        {
            ui    =  ui << 16;
            shift += 16;
        }
        if ((ui & 0xff000000) == 0)
        {
            ui    =  ui << 8;
            shift += 8;
        }
        if ((ui & 0xf0000000) == 0)
        {
            ui    =  ui << 4;
            shift += 4;
        }
        if ((ui & 0xc0000000) == 0)
        {
            ui    =  ui << 2;
            shift += 2;
        }
        if ((ui & 0x80000000) == 0)
            shift++;
        return shift;
    }
    private static uint[] Unnormalize(uint[] normalized, int shift)
    {
        var len          = GetLength(normalized);
        var unnormalized = new uint[len];
        if (shift > 0)
        {
            var  rshift = 32 - shift;
            uint r      = 0;
            for (var i = len - 1; i >= 0; i--)
            {
                unnormalized[i] = (normalized[i] >> shift) | r;
                r               = normalized[i] << rshift;
            }
        }
        else
        {
            for (var j = 0; j < len; j++)
                unnormalized[j] = normalized[j];
        }
        return unnormalized;
    }
    private static void Normalize(uint[] unormalized, int len, uint[] normalized, int shift)
    {
        int  i;
        uint n = 0;
        if (shift > 0)
        {
            var rShift = 32 - shift;
            for (i = 0; i < len; i++)
            {
                normalized[i] = (unormalized[i] << shift) | n;
                n             = unormalized[i] >> rShift;
            }
        }
        else
        {
            i = 0;
            while (i < len)
            {
                normalized[i] = unormalized[i];
                i++;
            }
        }
        while (i < normalized.Length)
            normalized[i++] = 0;
        if (n != 0)
            normalized[len] = n;
    }
    public static FixedBigInteger Remainder(FixedBigInteger dividend, FixedBigInteger divisor)
    {
        DivRem(dividend, divisor, out var remainder);
        return remainder;
    }
    public static FixedBigInteger Max(FixedBigInteger left, FixedBigInteger right)
    {
        return left.CompareTo(right) < 0 ? right : left;
    }
    public static FixedBigInteger Min(FixedBigInteger left, FixedBigInteger right)
    {
        return left.CompareTo(right) <= 0 ? left : right;
    }
    public static int GetBitWidth(FixedBigInteger n)
    {
        FixedBigInteger bw = 1;
        var             v  = n;
        while ((v >>= 1) > 0)
            bw++;
        if (bw < 8)
            bw = 8;
        while (bw % 8 != 0)
            bw++;
        return (int) bw;
    }
    public static int GetBitWidth<T>(T n)
    {
        ulong   bw = 1;
        dynamic v  = new FixedBigInteger((dynamic) n, 0);
        while ((v >>= 1) > 0)
            bw++;
        if (bw < 8)
            bw = 8;
        while (bw % 8 != 0)
            bw++;
        return (int) bw;
    }
    public static FixedBigInteger operator %(FixedBigInteger dividend, FixedBigInteger divisor)
    {
        return Remainder(dividend, divisor);
    }
    public static FixedBigInteger operator /(FixedBigInteger dividend, FixedBigInteger divisor)
    {
        return Divide(dividend, divisor);
    }
    public ulong[] ToUIn64Array()
    {
        var al = Data.Length >> 1;
        if (al * 2 != Data.Length)
            al++;
        var arr = new ulong[al];
        Buffer.BlockCopy(Data, 0, arr, 0, Data.Length << 2);
        return arr;
    }
    public uint[] ToUIn32Array()
    {
        return Data;
    }
    public byte[] ToByteArray()
    {
        var ba = new byte[DataUsed * DataSize];
        Buffer.BlockCopy(Data, 0, ba, 0, DataUsed * DataSize);
        return ba;
    }
    private void TrimToMsb()
    {
        var dataUsed = Data.Length;
        while (dataUsed > 1 && Data[dataUsed - 1] == 0)
            --dataUsed;
        if (dataUsed != Data.Length)
        {
            var tData = new uint[dataUsed];
            for (var i = 0; i < dataUsed; i++)
                tData[i] = Data[i];
            Data = (uint[]) tData.Clone();
        }
    }
    public static FixedBigInteger Multiply(FixedBigInteger left, FixedBigInteger right)
    {
        if (left == 0 || right == 0)
            return Zero;
        if (left == 1 && right != 1)
            return right;
        if (left != 1 && right == 1)
            return left;
        if (left == 1 && right == 1)
            return One;
        var xInts   = left.Data;
        var yInts   = right.Data;
        var mulInts = new uint[Math.Max(xInts.Length, yInts.Length) << 1];
        for (var i = 0; i < xInts.Length; i++)
        {
            var   index     = i;
            ulong remainder = 0;
            foreach (var yi in yInts)
            {
                remainder        = remainder + (ulong) xInts[i] * yi + mulInts[index];
                mulInts[index++] = (uint) remainder;
                remainder        = remainder >> 32;
            }
            while (remainder != 0)
            {
                remainder        += mulInts[index];
                mulInts[index++] =  (uint) remainder;
                remainder        =  remainder >> 32;
            }
        }
        var du = GetDataUsed(mulInts);
        Array.Resize(ref mulInts, du);
        return new FixedBigInteger(left.Sign * right.Sign, mulInts, 0);
    }
    public static FixedBigInteger operator *(FixedBigInteger left, FixedBigInteger right)
    {
        return Multiply(left, right);
    }
    public static FixedBigInteger operator >>(FixedBigInteger value, int shift)
    {
        if (shift == 0)
            return value;
        if (shift == int.MinValue)
            return value << int.MaxValue << 1;
        if (shift < 0)
            return value << -shift;
        var xd          = value.Data;
        var shiftAmount = 32;
        var invShift    = 0;
        var bufLen      = xd.Length;
        while (bufLen > 1 && xd[bufLen - 1] == 0)
            bufLen--;
        for (var count = shift; count > 0; count -= shiftAmount)
        {
            if (count < shiftAmount)
            {
                shiftAmount = count;
                invShift    = 32 - shiftAmount;
            }
            ulong carry = 0;
            for (var i = bufLen - 1; i >= 0; i--)
            {
                var val = (ulong) xd[i] >> shiftAmount;
                val   |= carry;
                carry =  (ulong) xd[i] << invShift;
                xd[i] =  (uint) val;
            }
        }
        return new FixedBigInteger(value.Sign, xd, DataBitWidth);
    }
    public static FixedBigInteger operator <<(FixedBigInteger value, int shift)
    {
        if (shift == 0)
            return value;
        if (shift == int.MinValue)
            return value >> int.MaxValue >> 1;
        if (shift < 0)
            return value >> -shift;
        var digitShift = shift / 32;
        var smallShift = shift - digitShift * 32;
        var xd         = value.Data;
        var xl         = xd.Length;
        var zd         = new uint[xl + digitShift + 1];
        if (smallShift == 0)
        {
            for (var index = 0; index < xl; ++index)
                zd[index + digitShift] = xd[index];
        }
        else
        {
            var  carryShift = 32 - smallShift;
            uint carry      = 0;
            int  index;
            for (index = 0; index < xl; ++index)
            {
                var rot = xd[index];
                zd[index + digitShift] = (rot << smallShift) | carry;
                carry                  = rot >> carryShift;
            }
            zd[index + digitShift] = carry;
        }
        return new FixedBigInteger(value.Sign, zd, DataBitWidth);
    }
    public static FixedBigInteger operator |(FixedBigInteger left, FixedBigInteger right)
    {
        if (left == 0)
            return right;
        if (right == 0)
            return left;
        var z    = new uint[Math.Max(left.Data.Length, right.Data.Length)];
        var lExt = left.Sign  < 0 ? uint.MaxValue : 0U;
        var rExt = right.Sign < 0 ? uint.MaxValue : 0U;
        for (var i = 0; i < z.Length; i++)
        {
            var xu = i < left.Data.Length ? left.Data[i] : lExt;
            var yu = i < right.Data.Length ? right.Data[i] : rExt;
            z[i] = xu | yu;
        }
        return new FixedBigInteger(left.Sign * right.Sign, z, DataBitWidth);
    }
    public static FixedBigInteger operator ^(FixedBigInteger left, FixedBigInteger right)
    {
        var z    = new uint[Math.Max(left.Data.Length, right.Data.Length)];
        var lExt = left.Sign  < 0 ? uint.MaxValue : 0U;
        var rExt = right.Sign < 0 ? uint.MaxValue : 0U;
        for (var i = 0; i < z.Length; i++)
        {
            var xu = i < left.Data.Length ? left.Data[i] : lExt;
            var yu = i < right.Data.Length ? right.Data[i] : rExt;
            z[i] = xu ^ yu;
        }
        return new FixedBigInteger(left.Sign * right.Sign, z, DataBitWidth);
    }
    public static FixedBigInteger operator &(FixedBigInteger left, FixedBigInteger right)
    {
        if (left == 0 || right == 0)
            return 0;
        var z    = new uint[Math.Max(left.Data.Length, right.Data.Length)];
        var lExt = left.Sign  < 0 ? uint.MaxValue : 0U;
        var rExt = right.Sign < 0 ? uint.MaxValue : 0U;
        for (var i = 0; i < z.Length; i++)
        {
            var xu = i < left.Data.Length ? left.Data[i] : lExt;
            var yu = i < right.Data.Length ? right.Data[i] : rExt;
            z[i] = xu & yu;
        }
        return new FixedBigInteger(left.Sign * right.Sign, z, DataBitWidth);
    }
    public FixedBigInteger Sqrt()
    {
        var n     = this;
        var q     = One << ((int) Math.Ceiling(Log(n, 2)) >> 1);
        var steps = 0;
        var m     = Zero;
        while (Abs(q - m) >= 1)
        {
            m = q;
            q = (m + n / m) >> 1;
            steps++;
        }
        return q;
    }
    public FixedBigInteger Pow(int e)
    {
        var ans = this;
        if (e == 1)
            return ans;
        if (e == 0)
            return 1;
        for (var i = 1; i != e; i++)
            ans *= this;
        return ans;
    }
    public static FixedBigInteger ModPow(FixedBigInteger n, FixedBigInteger e, FixedBigInteger m)
    {
        var n1 = new BigIntX(n);
        var e1 = new BigIntX(e);
        var m1 = new BigIntX(m);
        var r  = new BigIntX(1);
        while (e1 != 0)
        {
            if (e1 % 2 == 1)
                r = r * n1 % m1;
            e1 >>= 1;
            n1 =   n1 * n1 % m1;
        }
        return new FixedBigInteger(r.ToByteArray(), DataBitWidth);
    }
    public bool Fermat(FixedBigInteger candidate)
    {
        uint[] wits = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41};
        var    pmo  = candidate - 1;
        for (var i = 0; i < wits.Length; i++)
        {
            var r = ModPow(wits[i], pmo, candidate);
            if (r != One)
                return false;
        }
        return true;
    }
    public bool IsPrime()
    {
        return Fermat(this);
    }
    public static double Log(FixedBigInteger value, double baseValue)
    {
        var c          = 0.0;
        var d          = 0.5;
        var dataLength = Length(value.Data);
        var topBits    = BitLengthOfUInt(value.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.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<FixedBigInteger> GetFactors(FixedBigInteger n)
    {
        var Factors = new List<FixedBigInteger>();
        var s       = n.Sqrt();
        var a       = Three;
        while (a < s)
        {
            if (n % a == 0)
            {
                Factors.Add(a);
                if (a * a != n)
                    Factors.Add(n / a);
            }
            a += 2;
        }
        return Factors;
    }
    public static FixedBigInteger GreatestCommonDivisor(FixedBigInteger a, FixedBigInteger b)
    {
        while (b > 0)
        {
            var r = a % b;
            a = b;
            b = r;
        }
        return a;
    }
    public static FixedBigInteger LeastCommonMultiple(FixedBigInteger a, FixedBigInteger b)
    {
        return a * b / a.Gcd(b);
    }
    public static double Log10(FixedBigInteger value)
    {
        return Log(value, 10.0);
    }
    public static double LogN(FixedBigInteger value)
    {
        return Log(value, 2.0);
    }
    private class FixedBigIntegerConverter : 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 FixedBigInteger(0, DataBitWidth);
        }
        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);
        }
    }
}
public class FixedIntXComparer : IComparer<FixedBigInteger>
{
    public int Compare(FixedBigInteger left, FixedBigInteger right)
    {
        return left.CompareTo(right);
    }
    public bool Equals(FixedBigInteger left, FixedBigInteger right)
    {
        if (left == null || right == null)
            return false;
        return left.Equals(right);
    }
    public int GetHashCode(FixedBigInteger obj)
    {
        return obj.GetHashCode();
    }
}

Leave a Reply

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