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