Adjustable Fixed Bit Width Signed Integer 32,64,128,256,…
Jun-11,2021: Obsolete Use xIntX Instead.
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 DefaultDataBitWidth = 2048;
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 = 0)
{
if (bitLength == 0)
bitLength = DefaultDataBitWidth;
DataBitWidth = bitLength;
DataLength = DataBitWidth >> DataShiftCount;
CalculateMinDataLength(value.Data.Length);
Data = new uint[DataLength];
value.Data.CopyTo(Data, 0);
}
public FixedBigInteger(string value, int bitLength = 0)
{
if (bitLength == 0)
bitLength = DefaultDataBitWidth;
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 = 0)
{
if (bitLength == 0)
bitLength = DefaultDataBitWidth;
if (bitLength < 32)
bitLength = 32;
DataBitWidth = bitLength;
DataLength = DataBitWidth >> DataShiftCount;
Data = new uint[DataLength];
Data[0] = value;
}
public FixedBigInteger(bool value, int bitLength = 0)
{
if (bitLength == 0)
bitLength = DefaultDataBitWidth;
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 = 0)
{
if (bitLength == 0)
bitLength = DefaultDataBitWidth;
if (bitLength < 32)
bitLength = 32;
DataBitWidth = bitLength;
DataLength = DataBitWidth >> DataShiftCount;
Data = new uint[DataLength];
Data[0] = value;
}
public FixedBigInteger(BigDecimal value, int bitLength = 0)
{
if (bitLength == 0)
bitLength = DefaultDataBitWidth;
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 = 0)
{
if (bitLength == 0)
bitLength = DefaultDataBitWidth;
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 = 0) : this((decimal) value, bitLength)
{
}
public FixedBigInteger(float value, int bitLength = 0) : this((decimal) value, bitLength)
{
}
public FixedBigInteger(short value, int bitLength = 0)
{
if (bitLength == 0)
bitLength = DefaultDataBitWidth;
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()
{
DataBitWidth = DefaultDataBitWidth;
DataLength = DataBitWidth >> DataShiftCount;
Data = new uint[DataLength];
Data[0] = 0;
}
public FixedBigInteger(int value, int bitLength = 0)
{
if (bitLength == 0)
bitLength = DefaultDataBitWidth;
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 = 0)
{
if (bitLength == 0)
bitLength = DefaultDataBitWidth;
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 = 0)
{
if (bitLength == 0)
bitLength = DefaultDataBitWidth;
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 = 0)
{
if (bitLength == 0)
bitLength = DefaultDataBitWidth;
if (bitLength < 32)
bitLength = 32;
DataBitWidth = bitLength;
DataLength = DataBitWidth >> DataShiftCount;
Data = new uint[DataLength];
Data[0] = value;
}
public FixedBigInteger(uint value, int bitLength = 0)
{
if (bitLength == 0)
bitLength = DefaultDataBitWidth;
if (bitLength < 32)
bitLength = 32;
DataBitWidth = bitLength;
DataLength = DataBitWidth >> DataShiftCount;
Data = new uint[DataLength];
Data[0] = value;
}
public FixedBigInteger(ulong value, int bitLength = 0)
{
if (bitLength == 0)
bitLength = DefaultDataBitWidth;
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 = 0) : this(value.ToByteArray(), bitLength)
{
}
public FixedBigInteger(Guid value, int bitLength = 0) : this(value.ToByteArray(), bitLength)
{
}
public FixedBigInteger(byte[] value, int bitLength = 0)
{
if (bitLength == 0)
bitLength = DefaultDataBitWidth;
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 = 0)
{
if (array == null)
throw new Exception("Array cannot be null.");
if (bitLength == 0)
bitLength = DefaultDataBitWidth;
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 = 0)
{
if (array == null)
throw new Exception("Array cannot be null.");
if (bitLength == 0)
bitLength = DefaultDataBitWidth;
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);
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);
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);
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);
}
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;
}
private static bool MillerRabin(FixedBigInteger candidate)
{
uint[] w = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41};
var s = 0;
var d = candidate - One;
while ((d & 1) == 0)
{
d >>= 1;
++s;
}
if (s == 0)
return false;
var nmo = candidate - One;
for (var i = 0; i < w.Length; ++i)
{
var x = ModPow(w[i], nmo, candidate);
if (!(x == 1) && !(x == nmo))
{
for (var r = 1; r < s; ++r)
{
x = ModPow(x, 2, candidate);
if (x == 1)
return false;
if (x == nmo)
break;
}
if (!(x == nmo))
return false;
}
}
return true;
}
public bool IsPrime()
{
return MillerRabin(this);
}
public static double Log(FixedBigInteger value, double baseValue)
{
var c = 0.0;
var d = 0.5;
//var dataLength = Length(value.Data);
var dataLength = value.Data[value.Data.Length - 1] != 0U ? value.Data.Length : value.Data.Length - 1;
var topBits = 0; //BitLengthOfUInt(value.Data[dataLength - 1]);
var x = value.Data[dataLength - 1];
while (x > 0)
{
x >>= 1;
topBits++;
}
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.69314718055994530941723212145818 * bitLength) / Math.Log(baseValue);
}
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 FixedBigIntegerComparer : 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();
}
}